Vermoeden van Collatz

Het vermoeden van Collatz is een vermoeden uit de getaltheorie dat de volgende iteratie bestudeert die ook wel de hagelsteenreeks wordt genoemd:

Neem een willekeurig geheel getal $n$.

• Als $n$ even is
  • Deel $n$ door 2
• Als $n$ oneven is
  • Vermenigvuldig $n$ met 3
  • Tel er 1 bij op

Het vermoeden van Collatz zegt nu dat welk natuurlijk getal je ook kiest, als je dit proces maar lang genoeg herhaalt, $n$ uiteindelijk altijd 1 wordt. Dit vermoeden is voor het eerst geformuleerd door Lothar Collatz in 1937. Tot op heden is het vermoeden nog niet bevestigd of weerlegd.

Wiskundige notatie

De wiskundige notatie is als volgt:

Begin met het definiëren van een functie:

$f(n) = \left\{\begin{matrix} n/2 &\mbox{als } n \equiv 0 \\ 3n+1 &\mbox{als } n\equiv 1 \end{matrix}\right. \pmod{2}$

Maak een rij a waarin de functie f steeds wordt herhaald. In wiskundige notatie ziet dit er als volgt uit:

$a_{i} = \left\{\begin{matrix}f(a_{i-1}) &\mbox{als } i > 0 \\ n &\mbox{als } i = 0\end{matrix}\right.$

Nu is het vermoeden als volgt:

$(\forall\ n \in \mathbb{N}, \exists\ i \in \mathbb{N})(a_0 = n, a_i = 1)$

Voorbeelden

Grafiek van de stappen beginnend bij n=27

Als voorbeeld neem n = 12, de rij $a$ ziet er nu als volgt uit: 12, 6, 3, 10, 5, 16, 8, 4, 2, 1.

Neem n = 15, dan ontstaat een veel 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 9.000) 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

• Als $n$ deelbaar is door 4 deel dan $n$ door 4.

Verklaring:$n$ is even. Deel $n$ door 2 en hij is weer even. Deel dan $n$ weer door 2.

• Algemener: Alle factoren 2 in de priemontbinding kunnen verwijderd worden.

Verklaring:Zolang $n$ een factor 2 heeft, is het even en dient het door 2 gedeeld te worden. Hierdoor wordt het aantal factoren 2 één minder.

• Als $n$ oneven is, vermenigvuldig dan met 3/2 en tel er 1/2 bij op.

Verklaring:$n$ is oneven. vermenigvuldig $n$ met 3, 3$n$ blijft nu oneven. Tel 1 bij 3$n$ op, nu wordt 3$n$+1 even en dus deel door 2.

• We hoeven alleen te bewijzen dat $(\forall\ n \in \mathbb{N}, \exists\ i \in \mathbb{N})(a_0 = n, a_i < n)$

Verklaring: Als bewezen kan worden dat er voor elke $n$ een getal $p$ voorkomt in de rij waarvoor geldt $p < n$, dan zal er een getal $q$ voorkomen dat kleiner is dan $p$, en weer een getal kleiner dan $q$, net zolang totdat dit resulteert in 1.

• Dit hoeft alleen bewezen te worden voor getallen 3 mod 4.

Verklaring: Getallen 0 of 2 mod 4 worden meteen kleiner: omdat door 2 gedeeld wordt. Getallen 1 mod 4 worden na 3n+1 0 mod 4 en ze zijn nu deelbaar door 4. 3/4n+1/4 < n (voor n > 1)

• Bij hogere modulo's vallen er meer getallen uit, zoals n = 3 mod 16.

Verklaring: n = 3 mod 16, 3n+1 = 10 mod 16, 3/2n+1/2 = 5 mod 8, 9/2n+5/2 = 0 mod 8 9/16n+5/16 < n. Voor n mod 1024 blijven er slechts 64 mogelijkheden over. (Dit is 6.25%) voor n mod $1024^2$ blijft er slechts 2% over.

• Bij het oneven getal n=2^p*q-1, kan je meteen door naar 3^p*q-1.

Verklaring: f(n) = 2^p*q-1, f(n+1) = 2^p*3*q-2, f(n+2) = 2^(p-1)*3*q-1 → ... → f(n+2*p) = 3^p*q-1.

Aanwijzingen

Er is een aantal aanwijzingen dat het vermoeden van Collatz waar is.

Voor alle getallen onder $5,76 * 10^{18}$ is inmiddels (18 januari 2009) 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.

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 je natuurlijk door 2 delen.

• $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.

Het opmerkelijkste hieraan is dat deze getallen slechts 1 uit elkaar liggen.

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 links

• Het vermoeden van Collatz Het vermoeden van Collatz op je Ti-84/Ti-83
• Collatz Conjecture, de site van het Distributed Computing-project