3x+1

1.Introductie

Voor ieder geheel positief getal N definiëren we een rij getallen als volgt:
Het eerste getal in de rij noemen we S₀ en S₀=N.
De volgende getallen in de rij noemen we achtereen volgens S_1, S₂,S₃, S₄ ......etc.
Ieder getal S_i in deze rij wordt berekend met behulp van zijn voorganger S_i-1 met behulp van de volgende regel:

(zie voor gebruik van kleur bij letters: variabelen)

Voorbeeld 1:

We kiezen N = 13, dus:
S₀ = 13, S₁ = 40, S₂ = 20, S₃ = 10, S₄ = 5, S₅ = 16, S₆ = 8, S₇ = 4, S₈ = 2, S₉ = 1, S₁₀ = 4, S₁₁ = 2, S₁₂ = 1, S₁₃ =4 ,S₁₄ = 2, S₁₅ = 1, S₁₆ = 4.............

We zien een dan weer stijgende en dan weer dalende rij tot dat bij S₉ het getal 1 bereikt wordt. Vervolgens komt het proces in een "loop": de getallen 4,2,1 herhalen zich .

Voorbeeld 2:

We kiezen N = 18, dus:
S₀ = 18, S₁ = 9, S₂ = 28, S₃ = 14, S₄ = 7, S₅ = 22, S₆ = 11, S₇ = 34, S₈ = 17, S₉ = 52, S₁₀ = 26, S₁₁= 13 en de rij gaat verder als in voorbeeld 1.

In beide voorbeelden komt de rij S_N in de loop 4,2,1,4,2,1..... terecht.
De centrale vraag in dit zogenaamde 3x+1 probleem (Collatz probleem, Syracuse probleem) is: is dit altijd zo? of anders geformuleerd:

Bestaat er voor iedere N een getal i zodat S_i = 1

Het is niet vanzelfsprekend dat het getal 1 bereikt wordt:
Andere mogelijkheden voor het gedrag van de rij S_N :

• Het is voorstelbaar dat er een getal N bestaat, zodat de bijbehorende rij S_N meer stijgt dan daalt, zodat de termen in de rij op den duur steeds groter en groter worden. In dit geval noemen we N divergent.
• Het is theoretisch ook mogelijk dat de rij in een andere loop dan de loop 4,2,1 terecht komt. Dus voor zekere N zijn er i en j, ij421 en S_i = S_j . In dit geval noemen we N cyclisch.

Tot nog toe is er nog nooit een voorbeeld van een divergent of van een cyclisch getal gevonden. Iedere tot nu toe gecontroleerde N bleek convergent, dus kwam de bijbehorende rij in de loop 4 ,2,1 terecht. Er is echter geen bewijs dat dit altijd het geval is.

Stand van zaken (november 2007):

Met veel computer rekenkracht en slimme computerprogramma's zijn alle getallen tot 40 * 2⁵⁰ (en dit is ± 607 * 10 ¹⁵) gecontrôleerd.

De belangrijkste theoretische resultaten ( de bewijzen hiervan zijn bepaald niet simpel) zijn:

• Als er andere "loops" zijn, dan is het aantal in ieder geval eindig
• Een dergelijke loop bevat heel veel getallen, gecombineerd met resultaten uit de onderzoekingen waar we het hierna over zullen hebben, in ieder geval ..........

De lengte van de rij S_N

Voorbeeld 3:

Kies N=7 en construeer de bijbehorende rij S₇:
7, 22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,
We stoppen voordat we de eerste keer het getal 1 hebben bereikt en tellen het aantal termen in de rij. Dit getal noemen we de lengte van de rij S₇ en noteren hem met L(S₇) .
L(S₇) =16

Definitie 1

Het aantal termen in een rij S_N tot aan de eerste term, die gelijk is aan 1, noemen we de lengte van de rij S_N en we noteren deze als L( S_N )

n.b. Dit getal kunnen we ook definiëren als de index i, waarvoor S_i voor de eerste keer gelijk is aan 1

Stelling 1

Ieder getal l komt voor als de lengte van een rij S_N

Bewijs

kies voor l als startgetal N=S₀= 2^l. Je moet dan l maal door twee delen om op 1 te komen. Het aantal termen is dus l .

3.Klassen

Voorbeeld 4

Bij N=14 en N=15 hebben we dezelfde rijlengte, namelijk 17

Definitie 2

We kunnen alle waarden van N met eenzelfde rijlengte L( S_N )=l in een verzameling stoppen, die we de klasse l zullen noemen en aangeven met K_l. Omdat iedere N tot een klasse behoort kunnen we het ook hebben over de klasse van N. We geven dat aan met K(N)

Iedere klasse K_l is dus een verzameling gehele positieve getallen en zal dus een kleinste getal bevatten

Definitie 3

Het kleinste getal in een klasse K_l noemen we een klasserecord

De waarden van N met een * zijn klasserecords.

Wanneer je een tabel maakt, beginnende met N=2, van de lengtes van de bijbehorende S_N kom je vanzelf de klasserecords tegen: zodra je een lengte vindt, die nog niet in de tabel voorkomt heb je een klasserecord. Het is dan namelijk de kleinste waarde van N met die lengte.
Bij kleine waarden van N komen klasserecords veelvuldig voor, maar hoe groter N des te sporadischer. Momenteel zijn er ruim 2000 bekend. Er wordt nog steeds gezocht naar klasserecords. Meer info hierover staat onderaan deze bladzijde.

Voorbeeld 4:

Neem N= 2⁴ . S_N=S₁₆={16,8,4,2,1} en de lengte L( S_N )=L(S₁₆)=4 en 16 ligt dus in de klasse K_4. Grotere waarden van N zullen in een klasse liggen met een hogere index omdat de bijbehorende rij S_N nooit zo snel op 2 terecht kan komen.

Algemeen:

N=2^l is het grootste getal in K_l

We kennen dus de volledige klasse K_l zodra we de tabel hierboven hebben uitgebreid tot N=2^l
Uit de tabel kunnen we dus al zien dat:

K₁={2} K₂={4} K₃={8} K₄={16} K₅={5,....,32}

Voor grotere indices van de klassen zullen het aantal elementen in een klasse snel toenemen. Mij zijn geen gegevens over aantallen elementen in een klasse bekend. (Misschien een idee om hier onderzoek naar te doen). Wel blijken de elementen in een klasse in groepen voor te komen van ongeveer even grote getallen. Deze groepen liggen dan weer een factor 6 uit elkaar.

Een heldere, uitgebreide introductie over het 3x+1 probleem en de huidige stand van zaken vind u op de site van Eric Roosendaal. Hij geeft ook de mogelijkheid om mee te rekenen aan het vinden van o.a nieuwe klasserecords. De site is in het Engels en wiskunde op min of meer middelbare school niveau lijkt mij noodzakelijk.

externe link: Eric Roosendaal, on the 3x+1 problem

naar begin pagina