Vermoeden van Collatz

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen

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 als beginwaarde gekozen wordt.

Iteratie[bewerken]

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

  • als even is, deel het door 2
  • als 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[bewerken]

Laat een willekeurig geheel getal zijn. Definieer de rij door

Het vermoeden is dat er een is waarvoor .

Voorbeelden[bewerken]

Grafiek van de stappen beginnend bij n=27

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

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

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

De iteraties kunnen versneld worden door:

  • alle factoren 2 in de priemontbinding te verwijderen.
    Immers, zolang een factor 2 heeft, is het een even getal en dient het door 2 gedeeld te worden.
  • bij oneven 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 een getal is, waarvoor geldt . Als er namelijk bij zo'n getal voorkomt in de rij, dan zal er bij dit getal weer een getal voorkomen dat kleiner is dan , en zo verder, net zo lang totdat dit resulteert in 1.
  • De laatste uitspraak hoeft op zijn beurt slechts bewezen te worden voor getallen . Voor getallen die modulo 4 gelijk zijn aan 0 of 2, is dit direct te zien, die worden namelijk in de eerste stap gedeeld door 2. Een getal dat modulo 4 gelijk is aan 1, wordt na de eerste stap , dus modulo 4 gelijk aan 0, en dan dus deelbaar door 4, waarna na de volgende twee stappen .
  • Door modulo een hogere macht van 2 te rekenen kunnen er meer getallen uitgesloten worden. Bijvoorbeeld . Men krijgt . Modulo 1024 blijven er slechts 64 mogelijkheden over (dat is 6,25%). Modulo 10242 blijft slechts 2% over.
  • Bij het oneven getal kan meteen doorgegaan worden naar . Door de bovengenoemde optimalisering bij oneven getallen toe te passen krijgt men namelijk: .

Aanwijzingen[bewerken]

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

Voor alle getallen onder 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 te creëren die keer door 2 gedeeld moeten worden en de -de keer met 3 vermenigvuldigd moeten worden en met 1 verhoogd moeten worden. Deze getallen zijn van de vorm mod . Bij deling door 2 worden ze mod . Herhaal dit net zo lang tot ze mod worden.

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

  • mod . Dit is een oneven getal.
  • Vermenigvuldigd met 3 wordt mod .
  • Plus 1: mod .
  • Gedeeld door 2: of mod

Dit is gelijk aan mod Waar eerst stond staat nu . Blijf dit herhalen tot er 0 overblijft. Dan is mod en dit betekent dat 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]