kop

Home Basics Origami Fractalen Getaltheorie Betegelingen Woordenboek Links Mijn boeken ster Contact

home>getaltheorie>3x+1 english soon

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 S0 en S0=N.
De volgende getallen in de rij noemen we achtereen volgens S1, S2,S3, S4 ......etc.
Ieder getal Si in deze rij wordt berekend met behulp van zijn voorganger Si-1 met behulp van de volgende regel:

S1 = Si-1 /2 als Si-1 even is
S1 = Si-1 * 3 + 1 als Si-1 oneven is

(zie voor gebruik van kleur bij letters:variabelen)

 

Voorbeeld 1:

We kiezen N = 13, dus:
S0 = 13, S1 = 40, S2 = 20, S3 = 10, S4 = 5, S5 = 16, S6 = 8, S7 = 4, S8 = 2, S9 = 1, S10 = 4, S11 = 2, S12 = 1, S13 =4 ,S14 = 2, S15 = 1, S16 = 4.............

We zien een dan weer stijgende en dan weer dalende rij tot dat bij S9 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:
S0 = 18, S1 = 9, S2 = 28, S3 = 14, S4 = 7, S5 = 22, S6 = 11, S7 = 34, S8 = 17, S9 = 52, S10 = 26, S11= 13 en de rij gaat verder als in voorbeeld 1.

In beide voorbeelden komt de rij SN 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 Si = 1

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

  • Het is voorstelbaar dat er een getal N bestaat, zodat de bijbehorende rij SN 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 Si = Sj . 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 * 250 (en dit is ± 607 * 10 15) 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 SN

Voorbeeld 3:

Kies N=7 en construeer de bijbehorende rij S7:
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 S7 en noteren hem met L(S7) .
L(S7) =16

Definitie 1

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

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

Stelling 1

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

Bewijs

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

3.Klassen

Voorbeeld 4

N SN L( SN )
14 14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
17
15 15,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1
17

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

Definitie 2

We kunnen alle waarden van N met eenzelfde rijlengte L( SN )=l in een verzameling stoppen, die we de klasse l zullen noemen en aangeven met Kl. 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 Kl is dus een verzameling gehele positieve getallen en zal dus een kleinste getal bevatten

Definitie 3

Het kleinste getal in een klasse Kl noemen we een klasserecord

N   L( SN) in K
2* 2,1 1 1
3* 3,10,5,16,8,4,2,1 7 7
4* 4,2,1 2 2
5* 5,16,8,4,2,1 5 5
6* 6,3,10,5,16,8,4,2,1 8 8
7* 7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1 16 16
8* 8,4,2,1 3 3
9* 9,28,14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1 19 19
10* 10,5,16,8,4,2,1 6 6
11* 11,34,17,52,26,13,40,20,10,5,16,8,4,2,1 14 14
12* 12,6,3,10,5,16,8,4,2,1 9 9
13 13,40,20,10,5,16,8,4,2,1 9 9
14* 14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1 17 17
15 15,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1 17 17
16* 16,8,4,2,1 4 4
17* 17,52,26,13,40,20,10,5,16,8,4,2,1 12 12
18* 18,9,28,14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1 20 20
19 19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1 20 20
20 20,10,5,16,8,4,2,1 7 7
21 21,64,32,16,8,4,2,1 7 7
22 22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1 15 15
23     15
24 24,12,6,3,10,5,16,8,4,2,1 10 10
25 25,76,38,19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1   23
26     10
      111
      18
      18
      18
      106
      5
      26

De waarden van N met een * zijn klasserecords.

Wanneer je een tabel maakt, beginnende met N=2, van de lengtes van de bijbehorende SN 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= 24 . SN=S16={16,8,4,2,1} en de lengte L( SN )=L(S16)=4 en 16 ligt dus in de klasse K4. Grotere waarden van N zullen in een klasse liggen met een hogere index omdat de bijbehorende rij SN nooit zo snel op 2 terecht kan komen.

Algemeen:

N=2l is het grootste getal in Kl

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

K1={2} K2={4} K3={8} K4={16} K5={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

©jos hendriks, 2008-2016