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

Iteratie
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 
Laat  een willekeurig geheel getal zijn. Definieer de rij  door

Het vermoeden is dat bij iedere  er een  is waarvoor .

Voorbeelden 

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 
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 
Er zijn enkele aanwijzingen dat het vermoeden van Collatz juist is.

Sinds 2020 is voor alle getallen onder  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

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

Opmerkelijkheden 
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 
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

Getaltheorie
Collatz