Vermoeden van Collatz

Het Vermoeden van Collatz is een vermoeden in de getaltheorie dat zegt dat een bepaalde iteratie in alle gevallen uitloopt op het getal 1, om het even welk getal $n$ als beginwaarde gekozen wordt.

Iteratie

Neem een willekeurig geheel getal $n$ als beginwaarde en bereken een volgend getal door de regels:

als $n$ even is, deel het door 2
als $n$ oneven is, vermenigvuldig het met 3 en tel er 1 bij op.

Het vermoeden is dat bij herhaalde toepassing van deze regels men uiteindelijk in eindig veel stappen bij het getal 1 uitkomt. Dit vermoeden is voor het eerst geformuleerd door Lothar Collatz in 1937. Tot op heden is het vermoeden nog niet bewezen of weerlegd.

In 1984 noemde Brian Hayes in de column Computer recreations in het tijdschrift Scientific American de getallen in een dergelijke rij hailstone numbers, hagelsteengetallen.

Wiskundige formulering

Laat $n > 0$ een willekeurig geheel getal zijn. Definieer de rij $(a_{i})$ door

a_{0} = n

a_{i + 1} = {\begin{matrix} a_{i} / 2 & als a_{i} even is \\ 3 a_{i} + 1 & als a_{i} oneven is \end{matrix}

Het vermoeden is dat bij iedere $a_{0}$ er een $N \in ℕ$ is waarvoor $a_{N} = 1$ .

Voorbeelden

Neem $n = 12$ ; de rij $a$ ziet er dan uit als: 12, 6, 3, 10, 5, 16, 8, 4, 2, 1.

Met de beginwaarde $n = 15$ ontstaat een langere rij: 15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Bij $n = 27$ duurt het 111 stappen, totdat (via een maximum boven 9000) de waarde 1 wordt bereikt: 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1.

De langste rij voor een startwaarde onder 1000, is 178 stappen lang voor de startwaarde 871.

De langste rij voor een startwaarde onder 1 miljoen, is 524 stappen lang voor de startwaarde 837.799.

De langste rij voor een startwaarde onder 1 miljard, is 986 stappen lang voor de startwaarde 670.617.279.

Optimaliseringen

De iteraties kunnen versneld worden door:

alle factoren 2 in de priemontbinding te verwijderen.
Immers, zolang $a_{i}$ een factor 2 heeft, is het een even getal en dient het door 2 gedeeld te worden.
bij oneven $a_{i}$ te vermenigvuldigen met 3/2 en er 1/2 bij op te tellen.
Immers een oneven getal vermenigvuldigd met 3 blijft oneven en door er 1 bij op te tellen ontstaat een even getal dat dus deelbaar is door 2.
Ook het vermoeden kan geoptimaliseerd worden. Er hoeft slechts bewezen te worden dat er bij iedere $n = a_{0} \in ℕ$ een getal $i \in ℕ$ is, waarvoor geldt $a_{i} < n$ . Als er namelijk bij $n$ zo'n getal $i$ voorkomt in de rij, dan zal er bij dit getal $i$ weer een getal $j$ voorkomen dat kleiner is dan $j$ , en zo verder, net zo lang totdat dit resulteert in 1.
De laatste uitspraak hoeft op zijn beurt slechts bewezen te worden voor getallen $n = 3 (\mod 4)$ . Voor getallen die Modulair_rekenen 4 gelijk zijn aan 0 of 2, is dit direct te zien, die worden namelijk in de eerste stap gedeeld door 2. Een getal $n$ dat modulo 4 gelijk is aan 1, wordt na de eerste stap $3 n + 1$ , dus modulo 4 gelijk aan 0, en dan dus deelbaar door 4, waarna na de volgende twee stappen $(3 n + 1) / 4 < n$ .
Door modulo een hogere macht van 2 te rekenen kunnen er meer getallen uitgesloten worden. Bijvoorbeeld $n = 3 (\mod 16)$ . Men krijgt $n = 3 (\mod 16), 3 n + 1 = 10 (\mod 16), 3 / 2 n + 1 / 2 = 5 (\mod 8), 9 / 2 n + 5 / 2 = 0 (\mod 8), 9 / 16 n + 5 / 16 < n$ . Modulo 1024 blijven er slechts 64 mogelijkheden over (dat is 6,25%). Modulo 1024² blijft slechts 2% over.
Bij het oneven getal $n = 2^{p} q - 1$ kan meteen doorgegaan worden naar $3^{p} q - 1$ . Door de bovengenoemde optimalisering bij oneven getallen toe te passen krijgt men namelijk: $2^{p} q - 1, 2^{p - 1} 3 q - 1, 2^{p - 2} 3^{2} q - 1, \dots, 3^{p} q - 1$ .

Aanwijzingen

Er zijn enkele aanwijzingen dat het Vermoeden van Collatz juist is.

Sinds 2020 is voor alle getallen onder $2^{68}$ gecontroleerd dat ze aan het vermoeden voldoen. Het probleem met het controleren is dat het alleen het vermoeden kan weerleggen. Als het vermoeden waar is, kan er geen bewijs voor gevonden worden op deze manier.

Daarnaast geldt dat als je naar alle oneven getallen kijkt, ieder getal gemiddeld 3/4 is van het getal ervoor, en als dat lang genoeg wordt herhaald, het getal dus steeds kleiner wordt.

Uitbreiding naar grotere domeinen

Iteraties over alle gehele getallen

Een logische uitbreiding is die naar alle gehele getallen, niet alleen de positieve. In dit geval zijn er 5 bekende cyclussen

Cyclus	Aantal oneven waardes	Volledige lengte
1 → 4 → 2 → 1 …	1	3
0 → 0 …	0	1
-1 → -2 → -1 …	1	2
-5 → -14 → -7 → -20 → -10 → -5 …	2	5
-17 → -50 → -25 → -74 → -37 → -110 → -55 → -164 → -82 → -41 → -122 → -61 → -182 → -91 → -272 → -136 → -68 → -34 → -17 …	7	18

Het gegeneraliseerde Vermoeden van Collatz is dat ieder geheel getal in een van deze 5 cyclussen terechtkomt

Opmerkelijkheden

Er zijn getallen $n$ te creëren die $p - 1$ keer door 2 gedeeld moeten worden en de $p$ -de keer met 3 vermenigvuldigd moeten worden en met 1 verhoogd moeten worden. Deze getallen zijn van de vorm $2^{p - 1}$ mod $2^{p}$ . Bij deling door 2 worden ze $2^{p - 2}$ mod $2^{p - 1}$ . Herhaal dit net zo lang tot ze $2^{0}$ mod $2^{1}$ worden.

Ook is mogelijk getallen te maken die $p - 1$ keer met 3 moeten worden vermenigvuldigd en 1 verhoogd. Na iedere keer maal 3 plus 1 moet natuurlijk gedeeld worden door 2.

$n = 2^{p - 1} - 1$ mod $2^{p}$ . Dit is een oneven getal.
Vermenigvuldigd met 3 wordt $2^{p - 1} - 3$ mod $2^{p}$ .
Plus 1: $2^{p - 1} - 2$ mod $2^{p}$ .
Gedeeld door 2: $2^{p - 2} - 1$ of $2^{p - 2} - 1 + 2^{p - 1} = 3 * 2^{p - 2} - 1$ mod $2^{p}$

Dit is gelijk aan $2^{p - 2} - 1$ mod $2^{p - 1}$ Waar eerst $p$ stond staat nu $p - 1$ . Blijf dit herhalen tot er 0 overblijft. Dan is $2^{0} - 1$ mod $2^{1}$ en dit betekent dat $p$ even is.

Met de computer

Voorbeeld in de programmeertaal PHP:

$n = 12;
print $n;
while($n!==1){($n&1) ? $n = ($n * 3) + 1 : $n /= 2;print ' '.$n;}

BOINC

Er is ook een Distributed Computing project dat probeert meer inzicht in het vermoeden te geven. Dit heet Collatz Conjecture en draait onder BOINC.

Externe link

Collatz Conjecture, de site van het Distributed Computing-project

Bronnen, noten en/of referenties

↑ On The 3x + 1 Problem. www.ericr.nl. Geraadpleegd op 27 juli 2020.

[1] On The 3x + 1 Problem. www.ericr.nl. Geraadpleegd op 27 juli 2020.