Vermoeden van Collatz

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

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

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}n &\mbox{als } i = 0 \\ f(a_{i-1}) &\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[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]

  • 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, 3n blijft nu oneven. Tel 1 bij 3n op, nu wordt 3n+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[bewerken]

Er zijn 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 gegeneralizeerde 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.

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

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]