I får endnu et af de matematiske spørgsmål, som er lette at forstå, men indtil videre ikke har kunnet besvares.

Collatz-formodningen.

David Eisenbud forklarer Collatzformodningen. Endnu en rigtig fin video – fra Numberphile.

Collatzformodningen siger, at uanset hvilket helt positivt tal, man starter med, så ender man på et tidspunkt med tallet 1, hvis man følger proceduren og bliver ved:

Hvis n er lige, så divider med 2:  n ->n/2.

Hvis n er ulige, så gang med 3 og læg 1 til: n-> 3n+1

Forfra med det nye tal.

Eksempler: Begynd med n=1. Så får man 1, 4, 2, 1. Altså tilbage igen i et lille loop.

Begynd med 9. Så får man 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Alle de 20 tal, vi passerede for at nå fra 9 til 1 er nu undersøgt – de følger samme tur. Lad os tage et nyt: n=12. Det giver 12, 6, 3, 10 og så rammer vi et, vi har kortlagt, nemlig 10 og følger som ovenfor 10, 5, 16, 8, 4, 2, 1.

Vejen til 1 for små tal

De første 100 tals vej ned til 1 (fra Wikipedia Creative Commons)

Naturligvis har Sloanes heltalsfølger, som Ege Rubak har skrevet om på bloggen, forskellige varianter af spørgsmål om “3n+1”-følger, som de også kalde. Begynder man med 27 får man A008884 Listen er på 111 skridt og når helt op til 9232 på vejen.

Hvis det tal, man starter med, er mindre end 10^18, så når man til sidst 1 ved proceduren. Der er lignende problemer, som man ved er uafgørbare. Paul Erdös har efter sigende sagt, at matematikken endnu ikke er klar til at løse Collatzproblemet og Terry Tao er enig. Det er et fint problem, fordi det er let at forklare, man kan selv finde på lignende problemer – hvorfor skal der eksempelvis ganges med 3? hvad sker der, hvis man ganger med noget andet? Hvad er den længste følge af tal, man skal igennem for at nå ned til 1? Hvor langt når man op undervejs? Nok at lege med… Man kan lave heuristiske argumenter: Når n er ulige, så er 3n+1 lige, så det skridt kan erstattes med at gå til (3n+1)/2. Der er altså en omskrivning:

Hvis n er lige divideres med 2. Hvis n er ulige går man til (3n+1)/2.

Den lille analyse bruger Tao og andre til at sandsynliggøre, at man vil ende ved 1. Men det er ikke et bevis. Dog gør det, at Tao tror på formodningen…

Hvis man udvider spørgsmålet og tillader an+b i stedet for 3n+1, og desuden giver flere muligheder, a la hvis 2 går op i x, så…, hvis 3 går op i x, så…, så er spørgsmålet “vil følgen ende i 1” uafgørbart i datalogisk forstand. Det kan I læse om her http://people.cs.uchicago.edu/~simon/RES/collatz.pdf

Men man skal passe på, som xkcd bemærker: