Collatz-formodningen

Collatz-formodningen (efter tyske Lothar Collatz), også kendt som $(3n+1)$-formodningen, er et berømt uløst problem inden for talteori. Problemet er enkelt at formulere, men vanskeligt at løse. Erdős sagde om det: "Matematikken er endnu ikke parat til sådanne problemer."

Collatz-problemet kan opfattes som rekreativ matematik.

Betragt funktionen

$f(n)={\begin{cases}n/2&{\mbox{hvis }}n{\mbox{ er lige}}\\3n+1&{\mbox{hvis }}n{\mbox{ er ulige}}\end{cases}}$

Med andre ord fungerer $f$ ved at halvere et tal hvis tallet er lige, og ved at tredoble det og lægge én til, hvis tallet er ulige.

Vælg en positiv startværdi $n$, og iterér denne funktion:

$n\mapsto f(n)\mapsto f(f(n))\mapsto f(f(f(n)))\mapsto \ldots$

Vælger man for eksempel at starte med 11, får man denne følge:

$11\mapsto 34\mapsto 17\mapsto 52\mapsto 26\mapsto 13\mapsto 40\mapsto 20\mapsto 10\mapsto 5\mapsto 16\mapsto 8\mapsto 4\mapsto 2\mapsto 1\mapsto 4\mapsto 2\mapsto 1\mapsto \ldots$

Formodningen lyder nu således: Ligegyldigt hvilken positiv startværdi $n$ der vælges, kommer følgen før eller siden ned til 1 (hvorefter den gentager sig i et trivielt mønster $1\mapsto 4\mapsto 2\mapsto 1\mapsto \ldots$).

Illustration af Collatz-følgen med startværdi 127. Følgen ender til sidst på 1,4,2.

Det er så let at programmere en computer til at udregne Collatz-følger, at mange amatører har prøvet kræfter med det. Det vides at et modeksempel til formodningen må have mindst sytten (decimaler) cifre.

Et modeksempel kan opstå på to forskellige måder. Enten kommer følgen ind i en anden "løkke" end 1,4,2, altså der findes en anden periodisk udvikling af Collatz-iterationen, eller også vokser følgen uden grænse (og går imod uendelig).

Mange tror på formodningen og forventer derfor ikke at et modeksempel kan findes. På den anden side kan formodningen modbevises ved blot at fremvise ét eksempel på en ikke triviel "løkke" (som i givet fald måske skal findes ved hjælp af computer).

Ekstern henvisning

• http://mathworld.wolfram.com/CollatzProblem.html
• Collatz-formodningen og andre sorte huller (engelsk)

Se også

• Alikvotfølge – en lidt mindre elementær iterativ følge