Het vermoeden van Collatz

Het vermoeden van Collatz is een van die beweringen in de getaltheorie die eenvoudig op te schrijven, maar moeilijk te bewijzen zijn. Het is uitvoerig getest met behulp van computers en nog nooit is een tegenvoorbeeld gevonden. Weinig mensen twijfelen er dan ook aan dat het bewijs ooit eens geleverd zal worden. In tussentijd zoekt men naarstig naar patronen in de relevante getalreeksen. Soms wordt er iets gevonden.

Definitie

Het vermoeden van Collatz is een eenvoudige bewering over bepaalde reeksen van getallen. Het betreft reeksen die beginnen met een willekeurig positief getal n (dus 1 of hoger) en waarbij elk volgend getal wordt berekend door toepassing van de volgende regel.

• als n even is, deel het door 2 en als n oneven is vermenigvuldig het met 3 en tel er 1 bij op

Iets formeler:

• n -> n/2, als n deelbaar is door 2
• n -> 3n + 1, als n niet deelbaar is door 2

Voorbeelden

Neem als begingetal 13. Door toepassing van de zojuist gegeven regel leidt dit tot de reeks:

• 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...

Deze reeks eindigt op de cyclus 4, 2, 1, 4, 2, 1, 4, 2, 1, enzovoort.

Neem nu 19 als begingetal. Dit levert de volgende reeks op.

• 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, ..

Omdat voor het laatste getal 13 dat voor deze reeks is opgeschreven al is laten zien hoe de reeks eindigt, eindigt ook deze reeks met de cyclus 4, 2, 1, 4, 2, 1,....

Met behulp van computers zijn zo enorm veel reeksen berekend. Steeds blijkt dat ze op dezelfde cyclus eindigen. Ook wanneer de begingetallen heel groot zijn.

Het vermoeden van Collatz stelt dat alle mogelijke reeksen op deze cyclus eindigen. Een bewijs voor dit vermoeden ontbreekt. Het is al in 1937 wereldkundig gemaakt door Lothar Collatz en sindsdien is er tevergeefs gezocht naar een bewijs. Nog steeds is het mogelijk dat er een heel groot getal bestaat dat niet met deze cyclus eindigt. Of zo’n getal eindigt in een andere cyclus of dat de reeks naar oneindig gaat, dat weet niemand.

Een andere formulering

Als n oneven is, dan is het volgende getal gelijk aan 3n + 1. Maar dit getal is altijd even (omdat 3n altijd oneven is) en dus moet het in de volgende stap gedeeld worden door 2. Daarom kan de regel 3n + 1 vervangen worden door de regel (3n + 1)/2. Hierin zijn beide stappen tezamen genomen en in een enkele formule gezet. Dit leidt tot de volgende herformulering van de regels van Collatz:

• n -> n/2 als n deelbaar is door 2
• n -> (3n + 1)/2 als n niet deelbaar is door 2

Het eerste deel van de regel van Collatz noemen we de even regel en het tweede deel de oneven regel.

Als extra regel wordt er vaak nog genomen dat een reeks stopt bij 1. Dat is enkel voor het gemak. Immers, zodra de 1 bereikt is, ontstaat immers de cyclus 4, 2, 1,... Het heeft geen zin om dit steeds volledig uit te schrijven. In deze iets gewijzigde vorm komt het vermoeden van Collatz er op neer dat elke reeks die met de regel van Collatz wordt gebouwd zal eindigen op 1.

De voorbeeldreeksen uit de vorige sectie zullen er met deze gewijzigde regel ook iets anders uit zien. Het begingetal 13 leidt nu tot de volgende reeks:

• 13, 20, 10, 5, 8, 4, 2, 1

Het begingetal 19 leidt tot:

• 19, 29, 44, 22, 11, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1

Deze reeksen worden hier Collatz-reeksen genoemd.

Even en oneven getallen

De gewijzigde formulering van het vermoeden van Collatz maakt duidelijk waarom het eigenlijk een merkwaardig vermoeden is. De oneven regel maakt dat het volgende getal - (3n + 1)/2 - groter is dan n zelf. Het verschil tussen beide is gelijk aan:

• (3n + 1)/2 - n = (n + 1)/2

De even regel daarentegen leidt tot n/2 en dat is kleiner dan n. Het verschil is:

• n-n/2=n/2

Met andere woorden: de sprongen omhoog zijn groter dan de sprongen omlaag. Wanneer de verdeling van de even en oneven getallen in de reeks “om-en-om” zou zijn, dus als na een even getal telkens een oneven getal volgt en omgekeerd, dan mogen we verwachten dat de reeks naar oneindig zal gaan. Dat dat niet zo is, betekent dat de regels “iets doen” met de verdeling van even en oneven getallen om deze explosie te voorkomen. Ergens in die verdeling van even en oneven getallen zit het geheim van het vermoeden van Collatz verborgen.

Het punt is natuurlijk dat zowel de even als de oneven regel niet “om-en-om” gebruikt worden, maar regelmatig meerdere keren herhaald moeten worden. Dat kan er toe leiden dat de reeks van getallen, op den duur, toch kleiner worden. Immers als we starten met n en daar de oneven regel op toepassen, krijgen we (3n + 1)/2. Dit is groter dan n zodat ook een reductie via de even regel groter zal zijn dan voor n. Deze is nu gelijk aan:

• (3n + 1)/2 - n = (n + 1)/2

Dat is precies gelijk aan de vermeerdering van een getal na een enkele toepassing van de oneven regel. En wanneer de oneven regel twee maal toegepast wordt en pas daarna de even regel, dan leert een beetje algebra ons dat de reductie dan gelijk is aan:

• (5n + 5 )/4

En dat is uiteraard groter dan (n + 1)/2.

Dus: juist omdat de reductie (de even regel) toegepast wordt op een getal groter dan n en daardoor tot een grotere reductie leidt, kan er een dalende reeks van getallen ontstaan.

Als gezegd: het is de verdeling van even en oneven getallen die er voor zorgt dat de reeks niet explodeert. Deze verdeling is ten nauwste gekoppeld aan de sequentie waarmee de even en de oneven regels moeten worden toegepast. Maar hoe de eenvoudige regels van Collatz dat precies voor elkaar krijgen, is een raadsel.

Priemfactoren en de regels van Collatz

Het is een fundamentele stelling in de getaltheorie dat elk getal op een unieke manier geschreven kan worden als het product van priemgetallen. Een getal als 28 bijvoorbeeld kan geschreven worden als 2 * 2 * 7. Er is geen andere ontbinding in priemgetallen mogelijk (afgezien dan van de volgorde waarin ze met elkaar vermenigvuldigd worden). De priemgetallen in zo’n ontbinding worden de priemfactoren genoemd.

Op 28 moet dus twee maal achtereen de even-regel toegepast worden omdat er twee machten van 2 in de priemontbinding zitten. Wanneer alleen de machten van 2 (dus alle getallen van de vorm 2^n met n een positief geheel getal) bekeken worden, dan is onmiddellijk duidelijk dat wanneer in een Collatz reeks zo’n macht voorkomt dat dan het vermoeden van Collatz geldig is. Het enige dat nodig is, is het n maal door 2 delen om op 1 uit te komen. In feite stelt het vermoeden van Collatz dat in elke Collatz reeks een macht van 2 voorkomt.

Een oorzaak voor de moeilijke bewijsbaarheid van het vermoeden van Collatz ligt in de oneven regel. Deze verandert de priemontbinding van getallen op een onvoorspelbare manier. Dat ligt niet aan de vermenigvuldiging met 3. Die zal daarin niet echt veel veranderen; al wat we hoeven doen is een extra 3 toevoegen aan de ontbinding. Maar zodra er een 1 bij opgeteld wordt, verandert de ontbinding in priemfactoren in de regel dramatisch. Een getal als 9 kan ontbonden worden in 3 * 3 terwijl 9 + 1 = 10 leidt tot 2 * 5; iets heel anders. Nog een voorbeeld: 147 is gelijk aan 3 * 7 * 7 terwijl 148 = 2 * 2 * 37. Alweer een totale metamorfose. Er lijkt geen enkele regelmaat in te zitten. En toch moet er een regelmaat in zitten. Het moet immers zo zijn dat er op gezette (en juiste) tijden een 2 in de priemontbinding voorkomt want anders explodeert een reeks naar oneindig.

Graden

Een manier om te laten zien dat er toch iets van een regelmaat in de opeenvolgende priemontbindingen zit, is door het begrip graad te introduceren. De graad van een getal is het aantal malen dat dezelfde regel (de even of de oneven regel) erop toegepast moet worden. Zo is de graad van het getal 7 gelijk aan 3 omdat pas na drie toepassingen van de oneven regel het getal 26 wordt bereikt. Dat is even en daarna moet de even regel toegepast worden. De graad van een even getal is vanzelfsprekend gelijk aan het aantal machten van 2 in de priemontbinding. De graad van 8 is dus ook drie omdat het geschreven kan worden als 2 * 2 * 2.

Nu is er met die graden iets aardigs aan de hand. Het kan aangetoond worden dat de graad van een even getal n precies gelijk is aan de graad van het oneven getal n - 1. Het bewijs daarvoor staat in figuur 1. Maar het patroon is nog iets verfijnder. Zoals figuur 2 laat zien, is het niet alleen zo dat de graad van een even getal gelijk is aan het voorgaande oneven getal, maar ook dat de graden wel heel fraai verdeeld zijn. Het middelste getal in zo'n band van getallen heeft de hoogste graad (afgezien van de graad van de hoogste macht van 2). De rest volgt een keurig regelmatig patroon van stijgen en dalen die volledig wordt bepaald door de even getallen.

Slotwoord

Het vermoeden van Collatz is een van die vermoedens die heel eenvoudig op te schrijven zijn maar die toch een enorme complexiteit herbergen. Dat nodigt uit tot het vinden van patronen om de zaak beter te kunnen begrijpen. Een van die fascinerende patronen is hier gepresenteerd. Aan de hand van het begrip graad blijkt dat er in de priemontbindingen van opeenvolgende getallen toch een regelmaat zit. Na een aantal toepassingen van de oneven regel van Collatz moet er op een precies te voorspellen moment een factor 2 in de priemontbinding voorkomen. Precies dat moet ervoor zorgen dat een Collatz-reeks niet naar oneindig explodeert. Het is een van de weinige regelmatigheden die in de priemontbindingen van getallen te vinden is waarbij de optelling van 1 een rol speelt. Alleen al daarom is een studie van het vermoeden van Collatz zeer de moeite waard.