Collatz-Folge

Die bisherigen Aufgaben sind eines Computers nicht würdig. Dafür würde auch ein wissenschaftlicher Taschenrechner reichen.
Daher werden wir uns nun einem Problem zuwenden, das sehr viele Berechnungen innerhalb möglichst kurzer Zeit erfordert.
Das ist eine typische Aufgabe für schnelle Rechner.
 

Bekannt ist die folgende Aufgabenstellung unter dem Namen Collatz-Problem oder 3n+1-Folge. Was verbirgt sich dahinter?
Im Jahre 1937 behauptete Herr Collatz, dass eine Folge, die dadurch entsteht, dass man gerade Zahlen halbiert und ungerade Zahlen mit drei multipliziert und eins addiert, immer auf dem Zyklus 4 - 2 - 1 - 4 - 2 - 1 - ... endet.

Diese Behauptung ist bis heute weder bewiesen noch widerlegt.
Sie können also Mathematik-Geschichte schreiben.
Falls Sie es mit einzelnen Zahlen probieren wollen:

Wichtige Links:
http://de.wikipedia.org/wiki/Collatz-Problem

Also wie war das noch mal? Nehmen wir die Zahl 7.
Das ergibt diese Folge: 7 - 22 - 11 - 34 - 17 - 52 - 26 - 13 - 40 - 20 - 10 - 5 - 16 - 8 - 4 - 2 - 1
Die Elementanzahl H(n) ist 17. Man kann auch die Schritte zählen. Dies nennt man dann z.B. Delay(n) = H(n) -1.
Delay(n) = Odd(n) + Even(n).

Der Kern des Programms könnte also wie folgt aussehen:

Aufbauend auf dieser Prüfung kann man eine if/else-Kontrollstruktur aufbauen.  

Dann fehlt noch eine Schleife (hier mit while), denn wir wollen die Folge vom Ausgangswert bis zum Zyklus 4 - 2 - 1 berechnen und die einzelnen Werte ausgeben. Eine zweite äußere Schleife (hier mit for) erlaubt die Berechnung mehrerer Folgen.

Wenn man eine Schleife erzeugt, benutzt man einfach nur eine Variable zahl, ansonsten müsste man noch die Zuweisung zahl = nächste_zahl einfügen. Das gesamte Programm sieht im ersten Schritt wie folgt aus:
 

// Berechnung der "Collatz-Folge" #include <iostream>  #include <limits> using namespace std; void wait() {   cin.clear();   cin.ignore(numeric_limits<streamsize>::max(), '\n');   cin.get(); } int main() {   unsigned long start ;               // Beginn der Berechnung bei 'start'   unsigned long end ;                 // Ende der Berechnung bei 'end'   /**************************** Eingabebereich ****************************/   cout << "Erste Zahl:  " ;   cin  >> start ;   cout << "Letzte Zahl: " ;   cin  >> end ;   /**************************** Eingabebereich ****************************/   unsigned long zahl ;  // Element der Folge    unsigned long i ;     // Zählvariable für die Folgenlänge   for( unsigned long j = start; j < end+1; ++j )   {     zahl = j ;      i = 1 ;     cout << "\n" <<  j << " " ; // Ausgangswert     while( zahl != 1 ) // Prüfung auf Zyklus 4-2-1      {         if( zahl % 2 == 0 )              zahl /=  2 ;           // Collatz-Folge         else             zahl = 3 * zahl + 1 ;  // Collatz-Folge         cout << zahl << " "; // Element der Folge          ++i ;      }     if( zahl == 1 )         cout << "\tH(n): "  <<  i << endl ; // H(n) Länge der Folge   }   wait(); }

Gibt man hier die Ausgangswerte 1 bis 10 ein erhält man diesen Bildschirmausdruck:

Das Programm ist bereits so ausgerüstet, dass man auch bei längeren Folgen noch den Überblick behält:

Nachdem wir uns überzeugt haben, dass unser Programm richtig arbeitet, wollen wir nun Zahlen auf die Richtigkeit der Behauptung von Herrn Collatz "checken". Wie machen wir das? Wir nehmen einfach die Ausgabe der einzelnen Elemente und einen Zeilenumbruch aus dem Programm:
 

... for( unsigned long j = start; j < end+1; ++j )   {        zahl = j ;         i = 1 ;        cout << /*"\n" <<*/ j << " " ; // Ausgangswert        while( zahl != 1 ) // Prüfung auf Zyklus 4-2-1         {             if( zahl % 2 == 0 )                  zahl /=  2 ;           // Collatz-Folge             else                 zahl = 3 * zahl + 1 ;  // Collatz-Folge    // cout << zahl << " "; // Element der Folge              ++i ;         }        if( zahl == 1 ) cout << "\tH(n): "  <<  i << endl ; // H(n) Länge der Folge   } ...

Hier ein Beispiel für die Zahlen von von 100 bis 120:

Lassen Sie nun eine Zahlenkolonne von 1 bis 100000 an Ihnen vorbei rollen. Was ist hier so langsam?
Ganz einfach: die Ausgabe in unserer Konsole!

Da müssen wir etwas unternehmen. Wir brauchen eine Begrenzung der Ausgabe. Da wir nur an riesigen Folgen interessiert sind, die irgendwie Probleme machen, setzen wir den Ausgabewert für H(n) einfach so hoch, dass wir nur die Extreme als Ausdruck erhalten.
Zum Experimentieren schaffen wir hier also eine zusätzliche Eingabe eines "Ausgabe-Limits":
 

// Berechnung der "Collatz-Folge" #include <iostream>  #include <limits> using namespace std; void wait(){...} int main() {   unsigned long start ;               // Beginn der Berechnung bei 'start'   unsigned long end ;                 // Ende der Berechnung bei 'end'   unsigned long ausgabe_limit ;       // Ausgabe ab H(n) > 'ausgabe_limit'    /**************************** Eingabebereich ****************************/   cout << "Erste Zahl:  " ;   cin  >> start ;   cout << "Letzte Zahl: " ;   cin  >> end ;   cout << "H(n) ab:     " ;   cin  >> ausgabe_limit ;   /**************************** Eingabebereich ****************************/   unsigned long zahl ;  // Element der Folge    unsigned long i ;     // Zählvariable für die Folgenlänge   for( unsigned long j = start; j < end+1; j++ )   {     zahl = j ;      i = 1 ;     while( zahl != 1 ) // Prüfung auf Zyklus 4-2-1      {       if( zahl % 2 == 0 )  zahl /= 2 ;        else                 zahl = 3 * zahl + 1 ;        i++ ;      }     if( ( zahl == 1 ) && ( i >= ausgabe_limit ) )      {       cout << j ; // Ausgangswert       cout << "\tH(n): "  <<  i << endl ; // H(n) Länge der Folge     }   }   wait(); }

Jetzt geht das alles ganz fix! Wenn wir die Folgen für die Ausgangszahlen von 1 bis 100000 berechnen lassen und hierbei die Ausgabegrenze für H(n) auf 320 setzen, dann benötigt das Programm nur noch einen Sekundenbruchteil. 

Wir testen noch einen weiteren Fall mit den Zahlen bis 10.000.000 mit H(n)>500. Zeitverbrauch: < 1 Minute.

Interessant ist auch der Geschwindigkeitsvergleich der beiden Möglichkeiten im Sourcecode:

     if( zahl % 2 == 0 )  zahl /= 2 ;            // Collatz-Folge
     else                 zahl = 3 * zahl + 1 ;  // Variante 1

     ( zahl % 2 == 0 ) ? zahl /= 2 : zahl = 3 * zahl + 1 ; // Collatz-Folge Variante 2

In beiden Fällen benötigt das kompilierte Programm die gleiche Zeit. Das können wir also abhaken.
Wir behalten hier die if/else-Schreibweise bei, da diese verständlicher ist.

Jetzt können wir die Milliarde innerhalb einer Stunde schaffen, insbesondere mit den heute üblichen Prozessoren der Gigahertz-Klasse.

Wer eine Klasse höher mitmischen will, sollte unsigned long long ( 2 hoch 64 = 18.446.744.073.709.551.616 ) einsetzen.
Nachfolgend ein rudimentäres Beispiel für das Testen des Zahlenbereiches zwischen 10^15 und 2*10^15:
 

//Version für Compiler mit dem 64 Bit Integer unsigned long long: // Berechnung der "3n+1"-Folge (Collatz-Folge) #include <iostream> #include <limits> using namespace std; void wait(){...} int main() {   /*********************************************************** Eingabebereich ****************************/   const unsigned long long element_limit       =             1000000 ; // Maximum H(n)   const unsigned long long element_print_limit =                 500 ; // Ausgabe nur, wenn H(n) > element_print_limit   const unsigned long long start               =    1000000000000000 ; // Beginn der Berechnung bei start   const unsigned long long end                 =    2000000000000000 ; // Ende der Berechnung bei end   /*********************************************************** Eingabebereich ****************************/   for( unsigned long long j = start; j < end; j++ )   {        unsigned long long zahl = j ;        unsigned long long    i = 1 ;        while( ( zahl != 1 ) && ( i <= element_limit ) )        {             if( zahl % 2 == 0 )                 zahl /= 2 ;             else                 zahl = 3 * zahl + 1 ;             i++ ;        }        if( zahl == 1 )        {             if( i > element_print_limit )             {                 cout << "Startzahl: " << j;                 cout << "\tAnzahl: "  << i << endl;             }        }        else        {            cout << "Startzahl: " << j;              cout << "kein Resultat (Anzahl-Limit erhoehen)" << endl;        }        if( i > element_limit ) cerr << "Anzahl zu hoch" << endl;   }        wait(); }

Konsolen sind für solche "blutleeren" Anwendungen ideal, wie Sie sehen. Viel Spaß damit!

Diese Grenze von 18.446.744.073.709.551.616 ist allerdings störend vor allem wegen des unberechenbaren 3n+1, das ab 1 Trillion schnell diese Grenze überspringt, daher benötigt man eine spezielle Bibliothek für wirklich große Zahlen.

Hier eine einfache Bibliothek als Einstiegsbeispiel:

http://mattmccutchen.net/bigint/  C++ Big Integer Library von Matt McCutchen.

... und hier ein dazu passendes Programm, mit dem man nun in unerforschtem Gebiet analysieren kann, allerdings nur mit deutlich eingeschränkter Geschwindigkeit:

Zurück zum Start