Sie sind hier: Collatz-Problem für Dummies» Beweis für Praktiker

Beweis für Praktiker

Bisher wurden mittels "brute force" alle Zahlen bis 268 durchprobiert, ohne eine einzige zu finden, für die die Collatz-Vermutung nicht zutrifft.

Auf Grundlage dieser Tatsache wird fast jeder praktisch denkende Mensch zum Schluss kommen, dass die Vermutung hinreichend sicher bewiesen ist.

Man kann aber auch noch den Trend der Entwicklung der Pfadlänge `bb "P"_H(n)` untersuchen und extrapolieren, um abzuschätzen, in welche Richtung sich diese bewegt. Wie schon in einem früheren Abschnitt erwähnt, ist die Pfadlänge `bb "P"_H(n)` die Anzahl der Iterationen der `bb "H"`-Funktion bis zum erstmaligen Erreichen der Zahl 1. Falls die Folge über alle Grenzen wächst oder falls sie in einen Zyklus ohne die 1 gerät, gilt also `bb "P"_H(n) = oo`.

Wenn man nun eine Reihe ungerader Zahlen und deren Pfadlänge `bb "P"_H(n)` betrachtet und vielleicht in ein Diagramm einzeichnet (wie im vorigen Abschnitt getan) erkennt man, dass diese Reihe für eine größere Zahl schlecht zu extrapolieren ist. Es ist auch wenig sinnvoll, Energie zu verpulvern, um die Folgen von immer größeren Zahlen zu berechnen. Zumal das ja immer nur ein winziger Bruchteil aller Zahlen sein kann.

Wie machen es andere Leute, wenn sie mehr Tests durchführen müssen, als Ressourcen vorhanden sind? Und wenn davon auszugehen ist, dass das Ergebnis der meisten Tests negativ ist und nur das Ergebnis von wenigen oder keinen Tests positiv? So war es zum Beispiel vor einem reichlichen Jahr beim Beginn der Corona-Pandemie. Manche Labore haben dann einfach einen Teil von mehreren Proben zusammen gemischt und diese Mischung untersucht. War sie negativ, war alles ok, war sie positiv, mussten die einzelnen Proben doch noch untersucht werden, um die positive(n) Probe(n) zu identifizieren. Es wurde also erst mal der Mittelwert mehrerer Proben gebildet.

So machen wir es auch. Allerdings ist es entscheidend, die Größe der Zahlenbereiche, von deren Pfadlänge `bb "P"_H(n)` Mittelwerte gebildet werden sollen, sinnvoll festzulegen.

Fasst man zum Beispiel `bb "P"_H(n)` für immer 1000 fortlaufende ungerade Zahlen zusammen und bildet dafür den Mittelwert `bb bar "P"_H(n)`, so entsteht eine Wertereihe, deren Verlauf kaum weniger stochastisch aussieht als der ursprüngliche Verlauf von `bb "P"_H(n)`.

Die Lösung besteht darin, keine gleich großen Zahlenblöcke zu bilden, über die gemittelt wird. Da oft gilt `bb "P"_H(n) = bb "P"_H(2n + 1)`, legen wir einfach die 2er-Potenzen als Bereichsgrenzen fest.

Es entsteht folgende Tabelle:

`x` `2^x` `n_min` `n_max` `a` `s` `m(x)`
1 2 3 3 1 2 2
2 4 5 7 2 6 3
3 8 9 15 4 17 4,25
4 16 17 31 8 106 13,25
5 32 33 63 16 240 15
6 64 65 127 32 589 18,40625
7 128 129 255 64 1326 20,71875
8 256 257 511 128 2803 21,8984375
9 512 513 1023 256 6284 24,546875
10 1024 1025 2047 512 14064 27,46875
11 2048 2049 4095 1024 30861 30,1376953125
12 4096 4097 8191 2048 66061 32,25634765625
13 8192 8193 16383 4096 140076 34,1982421875
14 16384 16385 32767 8192 297125 36,2701416015625
15 32768 32769 65535 16384 636005 38,8186645507812
16 65536 65537 131071 32768 1355579 41,3689880371094
17 131072 131073 262143 65536 2869444 43,7842407226563
18 262144 262145 524287 131072 6054704 46,1937255859375
19 524288 524289 1048575 262144 12720264 48,5239562988281
20 1048576 1048577 2097151 524288 26695392 50,9174194335938
21 2097152 2097153 4194303 1048576 55918743 53,3282690048218
22 4194304 4194305 8388607 2097152 116846879 55,7169337272644
23 8388608 8388609 16777215 4194304 243827113 58,1329138278961
24 16777216 16777217 33554431 8388608 507891910 60,5454337596893
25 33554432 33554433 67108863 16777216 1056081284 62,9473497867584
26 67108864 67108865 134217727 33554432 2193314958 65,3658794760704
27 134217728 134217729 268435455 67108864 4548270861 67,7745172530413
28 268435456 268435457 536870911 134217728 9419543020 70,1810644567013
29 536870912 536870913 1073741823 268435456 19485982261 72,5909406729043
30 1073741824 1073741825 2147483647 536870912 40264966142 74,999343868345
31 2147483648 2147483649 4294967295 1073741824 83115162770 77,407027380541
32 4294967296 4294967297 8589934591 2147483648 171404736417 79,816550210584
33 8589934592 8589934593 17179869183 4294967296 353159635993 82,2263853608165

 

Die Tabelle enthält folgende Spalten:

Spalte Wert Bedeutung
2 `2^x` Beginn des Zahlenbereichs
3 `n_min` kleinste ungerade Zahl  des Zahlenbereichs
4 `n_max` größte ungerade Zahl  des Zahlenbereichs
5 `a` Anzahl der ungeraden Zahlen im Zahlenbereich: `a=2^(x-1)`
6 `s` Summe der Pfadlängen für alle ungerade Zahlen im Zahlenbereich: `s = sum_(i=n_min)^(n_max) bb "P"_H(i)`
7 `m(x)` Mittelwert der Pfadlängen für alle ungerade Zahlen im Zahlenbereich: `m(x) =  s/a`

 

Nun zeichnen wir die berechneten Mittelwerte in ein Diagramm:

Mittelwerte

Das sieht doch schon mal gut aus. Der Mittelwert steigt stetig an. Aber kann er auf unendlich steigen, bevor x unendlich wird?
Eine Analyse der Differenzen benachbarter Mittelwerte (also im Prinzip die erste Ableitung) bringt uns weiter:

`Delta m(x) = m(x) - m(x-1)`

Differenz der Mittelwerte

`Delta m(x)` pegelt sich bei etwa 2,41 ein. Auch wenn man diese Kurve beliebig extrapoliert, ändert sich daran nichts.
Zur Kontrolle bilden wir von den Differenzen benachbarter Werte nochmals die Differenz (das entspricht der 2. Ableitung):

`Delta Delta m(x) = Delta m(x) - Delta m(x-1)`

Abweichung der Differenzen

`Delta Delta m(x)`  geht sehr stark gegen 0. Auch wenn man diese Kurve beliebig extrapoliert, ändert sich daran nichts.

Aus diesen Kurvenverläufen kann man folgern, dass die Collatz-Vermutung wahr ist.

Beweis 

Angenommen, die Collatz-Vermutung sei falsch.

Dann sei `y` die kleinste Zahl, für welche die `bb "H"`-Funktion nicht bei 1 endet. Es gilt gilt also `bb "P"_H(y) = oo`.

Weiter sei `z` die Anzahl der Stellen von `y` im Dualsystem. Dann müsste auch der zugehörige Mittelwert `m(z)` unendlich sein.

Dann müsste auch die Differenz `m(z) - m(z-1)` unendlich sein.

Und schließlich müsste dann auch `Delta Delta m(z)` unendlich sein.

Das alles lässt sich mit dem Verlauf der Kurven nicht vereinbaren, zumal es ja im Bereich der natürlichen Zahlen auch oberhalb von `2^68` keine Singularitäten bezüglich der Grundrechenarten gibt.