Stand: 28.11.2021
Es gibt so mathematische Spielereien, mit denen sich hochbezahlte Köpfe Ihr Leben lang beschäftigen ohne zum Ende zu kommen. Weil es angeblich spannende Fragen sind. Weil die Fragen nicht gelöst werden können, lobt man dafür sogar Belohnungen aus. Eins der Probleme schauen wir uns kurz an und lösen dann mal auf:
Lösung: Das 3n+1 Problem
Die Funktion um die es heute geht ist ein Algorithmus, weniger eine Funktion: f(x)=3x+1 ? x/2
In Worten: Wenn x ungerade ist, gilt x=3x+1. Wenn x gerade ist, dann gilt x = x/2 .
Die Behauptung:
Für alle Ganzzahlen n>0 gilt, daß am Ende des Algorithmusses eine Zahlenschleifen von 4,2,1 rauskommt. Es gibt keine anderen Schleifen. Was zu beweisen ist.
Beispiele:
Ausgabeformat: Anfangszahl: X-Wert big = größte Zahl in der Kette
1: x=4 big=4
1: x=2 big=4
1: x=1 big=4
1: x=4 big=4
1: x=2 big=4
1: x=1 big=4
Erklärt:
1 ist ungerade => 1*3+1 = 4
4 ist gerade => 4/2 = 2
2 ist gerade => 2/2 = 1
Man sieht, daß hier eine Schleife 4,2,1 rauskommt, weil bei x=1 das Ergebnis wieder 4 ist. In der Programmierung ist das eine Endlosschleife, weil die Abbruchbedingung fehlt. Deswegen stoppen alle nachfolgenden Ausgaben auch bei 1.
Anfangszahl 2:
2: x=1 big=1
Da muß man nicht viel erklären, weil steht oben schon 😉
3: x=10 big=10
3: x=5 big=10
3: x=16 big=16
3: x=8 big=16
3: x=4 big=16
3: x=2 big=16
3: x=1 big=16
Auch hier 4,2,1
4: x=2 big=2
4: x=1 big=2
Oh.. eine 4.. wie in 4,2,1.. ähm ja. siehe oben
5: x=16 big=16
5: x=8 big=16
5: x=4 big=16
5: x=2 big=16
5: x=1 big=16
6: x=3 big=3
6: x=10 big=10
6: x=5 big=10
6: x=16 big=16
6: x=8 big=16
6: x=4 big=16
6: x=2 big=16
6: x=1 big=16
7: x=22 big=22
7: x=11 big=22
7: x=34 big=34
7: x=17 big=34
7: x=52 big=52
7: x=26 big=52
7: x=13 big=52
7: x=40 big=52
7: x=20 big=52
7: x=10 big=52
7: x=5 big=52
7: x=16 big=52
7: x=8 big=52
7: x=4 big=52
7: x=2 big=52
7: x=1 big=52
8: x=4 big=4
8: x=2 big=4
8: x=1 big=4
9: x=28 big=28
9: x=14 big=28
9: x=7 big=28
9: x=22 big=28
9: x=11 big=28
9: x=34 big=34
9: x=17 big=34
9: x=52 big=52
9: x=26 big=52
9: x=13 big=52
9: x=40 big=52
9: x=20 big=52
9: x=10 big=52
9: x=5 big=52
9: x=16 big=52
9: x=8 big=52
9: x=4 big=52
9: x=2 big=52
9: x=1 big=52
Das läßt sich beliebig für jede Ganzzahl n > 0 wiederholen.
Diese Auflistungen hier zeigen schon den Grund für das Verhalten und das ist wenig mystisch und noch weniger unerklärlich.
Die Auflösung:
Die Frage war: Wieso kommt am Ende immer eine Schleife mit ( 4,2,1 ) raus?
Das ist ganz leicht, weil 3x+1 für jedes Start-x irgendwann auf 2^n trifft. 2^n ist die folgende Operation : 2*2*2*2*2*2*2….*2 . Das ist genau das Gegenteil von der Berechnung für gerade Zahlen in dem Algorithmus ( x=x/2 ) . Wenn ich also z.b. 2^6 treffe, was 64 ist, und dies ständig durch 2 teile, kommt am Ende ohne Zweifel 1 raus. Es ist egal wie groß n ist, das gilt immer. Der Algorithmus endet also immer in der Sequenz ( 2^n , 2^(n-1) … 2^(n-n) und 2^(0) = 1 . Da 1*3+1 = 2^2 ist, terminiert der Algorithmus nicht und es kommt zur Endlosschleife.
Das ist absolut kein Wunder.
Die nächste Behauptung ist: es gibt keine anderen Schleifen.
Da 3x+1 ausschließlich bei ungeraden Zahlen angewendet wird und bei der Berechnung garantiert immer eine gerade Zahl herauskommt und nicht jede gerade Zahl eine Potenz von 2 ist, kann es keine anderen Schleifen geben, da bei jedem Schritt nach einer ungeraden Zahl die Teilung durch 2 solange stattfindet, bis wieder eine ungerade Zahl kommt.
Da es für jede Potenz 2^n für n > 1 eine ungerade Zahlen x gibt, die x = (2^n -1) / 3 erfüllt, kann es keine andere Schleife geben, denn jede gerade Zahl geteilt durch 2 trifft am Ende der Teilung gerader Zahlen immer auf eine ungerade Zahl und sobald diese ungerade Zahl 1 ist, ist die Schleifenbedingung erfüllt. Da eine ungerade Zahl verdreifacht wird(+1), aber eine gerade Zahl nur halbiert, wächst x über die Zeit im Schnitt an, bis x = 2^n ist, also eine 2er Potenz getroffen wird. QED.
Negative Startwerte
Bei negativen Startwerten kommt es ganz schnell zu Zahlenschleifen. Das liegt nach Analyse des Algorithmuses an einem BUG. Wenn das ein Programm wäre, würde ich dafür eine 6 vergeben und es dem Entwickler um die Ohren hauen 😉
Die Formel ist ja „3x+1“. Diese Formel kann für einige Ganzzahlen keine 2er Potenzen im negativen Zahlenstrahl finden. Der „Bug“ liegt im „+“ Zeichen, daß im negativen Zahlenraum zum „Fehlerfall“ führt. Es müßte nämlich eigentlich „3x-1“ lauten. Damit erreicht man im negativen Zahlenbereich eine exakte Spiegelung des positiven Zahlenraumes, weil alle oben genannten Bedingungen dann erfüllt sind.
Das liegt an der Verletzung der Gleichungsregel, daß wenn ich auf der einen Seite der Gleichung etwas abziehe, ich es zum Ausgleich auf der anderen Seite hinzufügen muß:
2 = 5-3 => 2+3 = 5
Der Algorithmus „verletzt“ dies beim Übergang von positiven zu negativen Startzahlen. Das ist sprach-mathematisch natürlich inkorrekt, beschreibt aber das Problem sehr gut.
Beispiel:
x = -21
x = -63 / 3
x*3 = -63 = -62 -1
x*3+1 = -62
Wenn man das jetzt für +21 macht, gilt:
21*3+1 = 64
64 = 2^6 also durch 2 bis zur 1 teilbar. Für -62 gilt das nicht, da kommt bei unserem Algorithmus -31 raus, statt -32 wie es nötig wäre um zu terminieren.
Fazit
Das der Algorithmus im Negativen Zahlenbereich „mysteriöse Schleifen“ bildet, im positiven Bereich aber nicht, ist also ein Fehler im Algorithmus und nicht „mysteriös“, wie einige Youtuber das andeuten. Er ist einfach schlecht gemacht worden 😀
Kommentare sind erlaubt, also tobt Euch aus 😉
Wieviel Zeit und Energie in das angebliche Problem eines defekten Algorithmuses verplempert wird und wurde, könnt Ihr hier nachlesen:
https://en.wikipedia.org/wiki/Collatz_conjecture#Iterating_on_all_integers
oder lasst es Euch hier „erklären“:
Ich kann mich den Matheprofs nur anschließen: Verplempert keine Zeit damit, es ist einfach nur ein kaputter Algorithmus.
Nicht „3x+1“ ist das Problem, sondern der Algorithmus an sich ist defekt. Wie man sich daran so aufgeilen kann wie im obigen Beitrag ist mir persönlich ein Rätsel. Solche Fehler kommen in der Programmierung laufend vor, weil einer bei der Umsetzung oder der Planung geschlafen hat.
Hier ein kleines Programm für Java, das bei evtl. doch stattfindenden Versuchen hilfreich sein kann. Der BUG ist darin aber schon behoben worden 😉
public class ThreeXPlusOne {
static public void main(String[] args) {
long x = 0;
long max = 99;
for(long n=-max;n<max;n++) { x = n; long big = 0; if ( n != 0 ) do { if ( (x/2)*2 == x ) { x = x/2; } else { if ( n > 0 ) {
x = 3*x+1;
} else x = 3*x-1; // Korrektur für n<0 weil, mit +1 kann man nie 2^n treffen } if ( n > 0 && x > big ) big = x;
if ( n < 0 && x < big ) big = x; if ( args.length > 0 ) System.out.println( n+": x="+x+" big="+big);
} while ( x != -1 && x != 1 && x!=n );
if ( args.length == 0 ) System.out.println( n+": x="+x+" big="+big);
}
}
}
Ihr werdet den Code noch einem Beautyfier übergeben müssen, weil WordPress den unbedingt umformatieren muß ( und ich keine Lust habe, deswegen in der WordPressdatenbank den Code direkt einzutragen ).
