Vermoeden van Collatz

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Het vermoeden van Collatz is een vermoeden in de getaltheorie dat zegt dat de onderstaande iteratie uitloopt op het getal 1, om het even welk getal n als begin gekozen wordt.

Iteratie[bewerken]

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 als men dit proces vaak genoeg herhaalt, men uiteindelijk 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 bevestigd 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[bewerken]

Laat n>0 een willekeurig geheel getal zijn. Definieer de rij (a_i) door

a_0=n
a_{i+1} = 
\begin{cases} 
a_i/2 & \mbox{als  } a_i \mbox{ even is}\\
3a_i+1 & \mbox{als  } a_i \mbox{ oneven is}
\end{cases}

Het vermoeden is dat er een i \in \N is waarvoor a_i = 1.

Voorbeelden[bewerken]

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[bewerken]

De iteraties kunnen versneld worden door:

  • alle factoren 2 in de priemontbinding te verwijderen.
    Immers, zolang a_i een factor 2 heeft, is het even 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.
  • 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 zo lang 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 dus 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[bewerken]

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.

Uitbreiding naar grotere domeinen[bewerken]

Iteraties over alle gehele getallen[bewerken]

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[bewerken]

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.

Met de computer[bewerken]

Voorbeeld in de programmeertaal PHP:

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

BOINC[bewerken]

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[bewerken]