Collatz problem

Collatz problem är ett olöst problem inom talteorin. Problemet kallas även för bland annat Collatz förmodan, Ulam-förmodan och 3n+1-förmodan. Lothar Collatz formulerade problemet under sin tid som student. Problemet utgår från en räknelek som börjar med ett positivt heltal n. Nästa steg är att dela n med två om det är jämnt, eller multiplicera det med tre och addera ett om det är udda. Sedan upprepas detta steg med talet som erhölls genom uträkningen till dess att resultatet blir ett. Detta kan skrivas som en talföljd. Collatz problem är att avgöra om man, oavsett vilket tal man börjar med, kan nå talet ett. Problemet är ekvivalent med att avgöra om det finns någon cykel av tal som inte innehåller ett och om det finns något tal som växer oändligt stort; om något av dessa två saker existerar är förmodandet falsifierat, annars är det sant. Dessutom går det att omformulera problemet ytterligare. Datorberäkningar används för att undersöka och försöka hitta en lösning till Collatz problem. Än så länge har ingen kunnat avgöra huruvida alla talföljder slutar med ett, så problemet är olöst.

Problemformulering

Collatz problem utgår från följande räknelek:

1. Utgå från ett positivt heltal n.
2. Om n är jämnt, dividera det med två. Om det är udda, multiplicera det med tre och addera därefter ett.
3. Upprepa steg 2 tills du når talet ett.

Collatz problem består av att avgöra om det för alla n är möjligt att nå talet ett. Detta kan även uttryckas som en förmodan, som är att det för alla n faktiskt är möjligt att nå talet ett. För att underlätta förståelsen av problemet så används en funktion definierad som steg 2 i räkneleken. Den blir så här:

$T(n)=\left\{{\begin{matrix}n/2,&{\mbox{om }}n\equiv 0{\mbox{ (mod 2)}}\\3n+1,&{\mbox{om }}n\equiv 1{\mbox{ (mod 2)}}\end{matrix}}\right.$

Denna funktion används återigen på resultatet från tidigare beräkningar. Detta ger upphov till en talföljd. Alla termer i talföljden, bortsett från den första, är definierade rekursivt som en funktion av sin föregående term. Ett skrivsätt för detta är:

$a_{i}={\begin{cases}n,&{\mbox{då }}i=0\\T(a_{i-1}),&{\mbox{då }}i\neq 0\end{cases}}$

Exempelvis så ger talet 11 upphov till följande talföljd:

$a_{0}=11,\ a_{1}=34,\ a_{2}=17,\ a_{3}=52,\ a_{4}=26,\ a_{5}=13,\ a_{6}=40,\ a_{7}=20,\ a_{8}=10,\ a_{9}=5,\ a_{10}=16,\ a_{11}=8,\ a_{12}=4,\ a_{13}=2,\ a_{14}=1$

För en sådan talföljd $a_{0},a_{1},\ldots ,a_{k}$ så kan vi definiera följande två funktioner:

$\operatorname {Mx} (n)=\lim _{k\to \infty }\operatorname {Max} (a_{0},a_{1},\ldots ,a_{k})$

$\operatorname {Mn} (n)=\lim _{k\to \infty }\operatorname {Min} (a_{0},a_{1},\ldots ,a_{k})$

Dessa funktioner möjliggör tre definitioner för ett positivt heltal n. Talet n är:

• Konvergent om Mn(n)=1.
• Divergent om Mx(n) ej existerar.
• Cykliskt i alla andra fall.

Med hjälp av definitionera så är det möjligt att omformulera problemet. Alternativa formuleringar är:

• Inget n är divergent.
• Alla n är konvergenta.

Dessa två formuleringar antyder att det inte skulle finnas någon annan cykel än 1, 4, 2, 1, ... bland talföljderna för alla olika n. (På grund av räknelekens regler skulle denna cykel aldrig skrivas med i någon talföljd.) Inget av detta har ännu bevisats, och Collatz problem är olöst.

Resultat från datorberäkningar

Med hjälp av datorberäkningar har man kunnat undersöka många olika n. Samtliga n som undersökts har visat sig vara konvergenta. Följande kod är skriven till Lisp-dialekten DrScheme. Där kan en talföljd till ett tal n beräknas genom:

(define collatz
  (lambda (n)
    (cons n
          (cond ((= n 1) '())
                ((= (modulo n 2) 0) (collatz (/ n 2)))
                ((= (modulo n 2) 1) (collatz (+ (* n 3) 1)))))))

I och med att datorer blir bättre och bättre har det varit möjligt att visa att Collatz problem stämmer för mycket stora tal. Det tar lång tid att utföra beräkningarna. Än så länge har det bevisats att Collatz förmodan stämmer för tal upp till $2^{68}$. Detta har lett till att många matematiker tror att det gäller för alla tal.

Alternativa problemformuleringar

Det finns fler sätt att formulera Collatz problem. Bland annat kan funktionen T(n) inverteras till en flervärd funktion som här kallas R(n), och så börjat talföljden med ett istället. Då består problemet istället av att bevisa att talet ett kan leda till samtliga positiva heltal via funktionen:

$R(n)={\begin{cases}2n&{\mbox{om }}n\equiv 0,1,2,3,5{\mbox{ (mod 6)}}\\2n,(n-1)/3&{\mbox{om }}n\equiv 4{\mbox{ (mod 6)}}\end{cases}}$

Detta kan förklaras med en graf, vars centrum är talet ett. Andra tal är placerade runt ettan. Ett tals talföljd, som erhålls genom att funktionen T(n) används till dess att resultatet blir ett, fås genom att man följer pilarna. Den nästkommande termen i talföljden är den som pilen från talets ruta pekar mot.

Referenser

• Alexandersson, Per. "Talserier och rekursion". [1]
• Guy, Richard K: "Unsolved Problems in Number Theory". Springer-Verlag, New York. 1981.
• "The 3x+1 problem". [2]
• "Collatz Conjecture - Nitrxgen". [3]
• "On The 3x+1 Problem". [4]
• Engelska wikipedia för information om alternativa formuleringar av Collatz problem. [5]