Problem 14: Längste Collatz Sequenz

Gesucht wird die Startnummer (unter einer Million) mit der längsten Collatz-Kette! [das englische Original]

Grundsätzlich ist die Lösung dieses Problems leicht zu finden – dachte ich mir 😉 Die Lösungsvorschrift ist ja gegeben und somit auch das Programm leicht entwickelt. In diesem Fall liegt die Herausforderung allerdings in der Laufzeit. Würde man für jede Startnummer die Collatz-Kette komplett durchlaufen, bräuchte selbst ein leistungsstarke Rechner mehr als 20 Minuten.

Offensichtlich ist jedoch, dass die einzelnen Ketten irgendwann immer wieder auf bereits bekannte Zahlen treffen, so dass man hier die bekannte Anzahl von Elementen wieder verwenden kann:

private int getCount( long num ) {
   int count = 0;
   ArrayList< Long > mem = new ArrayList< Long >();

   while( num > 1 ) {
      if( cache.containsKey( num ) ) {
         count += cache.get( num );
         num = 1;
      } else {
         count++;
         mem.add( num );
         num = ( num%2 == 0 ) ? num/2 : 3*num+1;
      }
   }

   for( int i=0; i<mem.size(); i++ ) {
      cache.put( mem.get( i ), count-i );
   }

   return count;
}

Der Versuch einer rekursiven Lösung schlug bei mir allerdings fehl, da der Stack bereits bei der 40. Rekursionsstufe überläuft. Ebenfalls erfolglos war der Versuch, ausschließlich im Bereich von Integer zu bleiben.

Die o.g. Methode muss nun nur noch für die gewünschten Startnummern aufgerufen werden, um die Lösung zu finden:

public String solve() {
   int cur, num = 1, max = 1;
   for( int i=2; i<1000000; i++ ) {
      cur = getCount( i );
      if( cur >= max ) {
         IO.debugln( "found new max for " + i + " -> " + cur );
         max = cur;
         num = i;
      }
   }

   return IO.i2s( num );
}

Den vollständigen Quellcode der Klasse für die Lösung des Problems 14 kann man sich hier anschauen!

<< Problem 13 Übersicht Problem 15 >>

Kommentar verfassen

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: