1. Problemstellung
Es geht um Zahlenfolgen für natürliche Zahlen n > 0, die so definiert sind:
- a = n
- wiederhole solange, bis a == 1 ist
- a = 3 * a + 1 falls a ungerade ist
- a = a / 2
Beispielfolge für n = 3:
3; 10; 5; 16; 8; 4; 2; 1
Die Collatz-Vermutung lautet nun, dass die Folge für alle natürlichen Zahlen n > 0 mit der 1 endet.
2. Untersuchung der Collatz-Folge im Restklassenring modulo 2^m
Dieser Abschnitt enthält keine Literaturverweise, da der Inhalt eigenständig entwickelt und programmiert wurde. Er stellt keinen Beweis der Collatz-Vermutung dar. Aber er könnte ein Baustein für einen solchen Beweis sein.
Fragestellung: Für welche Zahlen a1 enthält die Collatz-Folge mindestens ein Folgenglied ai, das kleiner als der Startwert a1 ist? Diese Bedingung wird im Folgenden als Kriterium bezeichnet.
2.1 Betrachtung im Restklassenring modulo 2^1
Alle geraden Zahlen erfüllen das Kriterium im zweiten Folgenglied:
| Element | Startwert | Endwert bei Kriterium |
|---|---|---|
| 0 | a1 = 2k + 0 | a2 = k + 0 |
| 1 | a1 = 2k + 1 | unbekannt |
| Anteil für Kriterium = 50% | ||
Somit erfüllen 50% der Elemente des Rings das Kriterium.
2.2 Betrachtung im Restklassenring modulo 2^2
Für Zahlen der Form 4k + 1 ergeben sich die Folgenglieder:
a1 = 4k + 1; a2 = 12k + 4; a3 = 6k + 2; a4 = 3k + 1
| Element | Startwert | Endwert bei Kriterium |
|---|---|---|
| 0 | a1 = 4k + 0 | a2 = 2k + 0 |
| 1 | a1 = 4k + 1 | a4 = 3k + 1 |
| 2 | a1 = 4k + 2 | a2 = 2k + 1 |
| 3 | a1 = 4k + 3 | unbekannt |
| Anteil für Kriterium = 75% | ||
Somit erfüllen 75% der Elemente des Rings das Kriterium.
2.3 Betrachtung im Restklassenring modulo 2^4
Für die Zahl 3 lauten die Folgenglieder:
a1 = 3; a2 = 10, a3 = 5; a4 = 16; a5 = 8; a6 = 4; a7 = 2
Es sind hier also vier Halbierungen notwendig. Daher muss der Restklassenring modulo 2^4 verwendet werden.
Für Zahlen der Form 16k + 3 ergeben sich die Folgenglieder:
a1 = 16k + 3; a2 = 48k + 10; a3 = 24k + 5; a4 = 72k + 16; a5 = 36k + 8; a6 = 18k + 4; a7 = 9k + 2
| Element | Startwert | Endwert bei Kriterium |
|---|---|---|
| 0 | a1 = 16k + 0 | a2 = 8k + 0 |
| 1 | a1 = 16k + 1 | a4 = 12k + 1 |
| 2 | a1 = 16k + 2 | a2 = 8k +1 |
| 3 | a1 = 16k + 3 | a7 = 9k + 2 |
| 4 | a1 = 16k + 4 | a2 = 8k +2 |
| 5 | a1 = 16k + 5 | a4 = 12k + 4 |
| 6 | a1 = 16k + 6 | a2 = 8k +3 |
| 7 | a1 = 16k + 7 | unbekannt |
| 8 | a1 = 16k + 8 | a2 = 8k +4 |
| 9 | a1 = 16k + 9 | a4 = 12k + 7 |
| 10 | a1 = 16k + 10 | a2 = 8k +5 |
| 11 | a1 = 16k + 11 | unbekannt |
| 12 | a1 = 16k + 12 | a2 = 8k +6 |
| 13 | a1 = 16k + 13 | a4 = 12k + 10 |
| 14 | a1 = 16k + 14 | a2 = 8k +7 |
| 15 | a1 = 16k + 15 | unbekannt |
| Anteil für Kriterium = 81,25% | ||
2.4 Betrachtung im Restklassenring modulo 2^5
Für die Zahl 11 lauten die Folgenglieder:
a1 = 11; a2 = 34; a3 = 17; a4 = 52; a5 = 26, a6 = 13, a7 = 40; a8 = 20; a9 = 10
Es sind hier also fünf Halbierungen notwendig. Daher muss der Restklassenring modulo 2^5 verwendet werden.
Für Zahlen der Form 32k + 11 ergeben sich die Folgenglieder:
a1 = 32k + 11; a2 = 96k + 34; a3 = 48k + 17; a4 = 144k + 52; a5 = 72k + 26; a6 = 36k + 13; a7 = 108k + 40, a8 = 54k + 20; a9 = 27k + 10
Auch für die Zahl 23 sind fünf Halbierungen notwendig:
a1 = 32k + 23; a2 = 96k + 70; a3 = 48k + 35; a4 = 144k + 106; a5 = 72k + 53, a6 = 216k + 160,a7 = 108k + 80; a8 = 54k + 40; a9 = 27k + 20
Für die drei Elemente 7, 11 und 15, die das Kriterium im Restklassenring modulo 2^4 nicht erfüllen, ergeben sind nun im Restklassenring modulo 2^5 folgende Veränderungen:
| Element | Startwert | Endwert bei Kriterium |
|---|---|---|
| 7 | a1 = 32k + 7 | unbekannt |
| 11 | a1 = 32k + 11 | a9 = 27k + 10 |
| 15 | a1 = 32k + 15 | unbekannt |
| 23 | a1 = 32k + 23 | a9 = 27k + 20 |
| 27 | a1 = 32k + 27 | unbekannt |
| 31 | a1 = 32k + 31 | unbekannt |
| Anteil für Kriterium = 87,5% | ||
2.5 Betrachtung im Restklassenring modulo 2^{40}
Für die Berechnung der Anzahl der Elemente im Restklassenring modulo 2^{40}, die das Kriterium erfüllen, müssen jetzt nur noch die Zahlen der Form 32k + 7, 32k + 15, 32k + 27 und 32k + 31 betrachtet werden. Dies wird in dem folgenden Pythonprogramm berücksichtigt. Auf einem PC mit vier Prozessoren erfolgt die Berechnung dieser vier Formen über den Pool-Mechanismus von Python automatisch in parallelen Prozessen. Dennoch dauert die Berechnung mit einem Intel i3-8100 ca. 32 Stunden.
# CollatzRestKlassenRing.py V1.6 für Python 3
# Jens Lippenberger 28.11.2020
from multiprocessing import Pool
def BerechneAnzahlHalbierungenInDerFolge( a1, exponent2 ):
ai = ( 3 * a1 + 1 ) >> 1
anzahl = 1
while anzahl <= exponent2:
if ai & 1: ai = 3 * ai + 1
ai >>= 1
anzahl += 1
if ai < a1: break
return anzahl
def BerechneAnzahlGeeigneterElementeImRingProzess( exponent2, start, potenz2, schritt ):
anzahl = 0
for a1 in range( start, potenz2, schritt ):
if BerechneAnzahlHalbierungenInDerFolge( a1, exponent2 ) <= exponent2:
anzahl += 1
return anzahl
def BerechneAnzahlGeeigneterElementeImRing( exponent2, potenz2 ):
parameter = ( ( exponent2, 7, potenz2, 32 ), ( exponent2, 15, potenz2, 32 ),
( exponent2, 27, potenz2, 32 ), ( exponent2, 31, potenz2, 32 ) )
ergebnisse = Pool().starmap( BerechneAnzahlGeeigneterElementeImRingProzess, parameter )
anzahl = 0
for ergebnis in ergebnisse: anzahl += ergebnis
return anzahl
def BerechneRestKlassenRing( exponent2 ):
anzahl = 28 * 2 ** ( exponent2 - 5 )
potenz2 = 32 * 2 ** ( exponent2 - 5 )
anzahl += BerechneAnzahlGeeigneterElementeImRing( exponent2, potenz2 )
print( "m =", exponent2, "; Anzahl =", anzahl, "; 2^m =", potenz2, "; Anteil ={0:8.5f}".format( anzahl / potenz2 ) )
def main():
BerechneRestKlassenRing( 40 )
if __name__ == '__main__':
main()Für die Restklassenringe modulo 2^1 bis 2^{40} ergeben sich folgenden Anteile:
| Ring 2^m | Anzahl Elemente mit Kriterium | Anzahl aller Elemente | Anteil |
|---|---|---|---|
| 1 | 1 | 2 | 50,000% |
| 2 | 3 | 4 | 75,000% |
| 4 | 13 | 16 | 81,250% |
| 5 | 28 | 32 | 87,500% |
| 7 | 115 | 128 | 89,844% |
| 8 | 237 | 256 | 92,578% |
| 10 | 960 | 1.024 | 93,750% |
| 12 | 3.870 | 4.096 | 94,520% |
| 13 | 7.825 | 8.192 | 95,520% |
| 15 | 31.473 | 32.768 | 96,048% |
| 16 | 63.422 | 65.536 | 96,774% |
| 18 | 254.649 | 262.144 | 97,141% |
| 20 | 1.021.248 | 1.048.576 | 97,394% |
| 21 | 2.050.541 | 2.097.152 | 97,777% |
| 23 | 8.219.801 | 8.388.608 | 97,988% |
| 24 | 16.490.635 | 16.777.216 | 98,292% |
| 26 | 66.071.490 | 67.108.864 | 98,454% |
| 27 | 132.455.435 | 134.217.728 | 98,687% |
| 29 | 530.485.275 | 536.870.912 | 98,811% |
| 31 | 2.123.841.570 | 2.147.483.648 | 98,899% |
| 32 | 4.253.619.813 | 4.294.967.296 | 99,037% |
| 34 | 17.027.951.548 | 17.179.869.184 | 99,116% |
| 35 | 34.095.896.991 | 34.359.738.368 | 99,232% |
| 37 | 136.471.574.881 | 137.438.953.472 | 99,296% |
| 39 | 546.144.278.026 | 549.755.813.888 | 99,343% |
| 40 | 1.093.108.792.776 | 1.099.511.627.776 | 99,418% |
Fazit: Im Restklassenring modulo 2^{40} haben 99,418% aller Elemente a1 in der Collatz-Folge mindestens ein Folgenglied ai, das kleiner als der Startwert a1 ist.