Collatzin konjektuuri

Wikipedia

Collatzin konjektuuri on yksinkertaisesti muotoiltu matemaattinen väittämä, jolle ei kuitenkaan ole toistaiseksi löydetty todistusta (ks. konjektuuri). Sen mukaan tietynlaiset lukujonot päättyvät aina samalla tavalla, riippumatta mistä luvusta kyseinen lukusarja aloitetaan. Paul Erdősin mukaan "Matematiikka ei ole vielä valmis tämän kaltaisiin ongelmiin".

Väittämä voidaan havainnollista seuraavasti:

Mielivaltaiselle positiiviselle kokonaisluvulle suoritetaan seuraava toimenpide:

Jos luku on parillinen, jaetaan se kahdella
Jos luku on pariton, kerrotaan se kolmella ja lisätään yksi.

Eli matemaattisesti ilmaistuna määritellään funktio f:

$f(n) = \begin{cases} n/2 &\mbox{jos } n \equiv 0 \\ 3n+1 & \mbox{jos } n\equiv 1 \end{cases} \pmod{2}.$

Tämän jälkeen toistetaan operaatio useita kertoja peräkkäin alkaen mistä tahansa mielivaltaisesta kokonaisluvusta ja suoritetaan seuraava operaatio edellisen operaation lopputulokselle. Eli:

$a_i = \begin{cases}n & \mbox{kun } i = 0 \\ f(a_{i-1}) & \mbox{kun } i > 0\end{cases}$

Tällöin Collatzin väittämä kuuluu: Tämä prosessi johtaa aina loppujen lopuksi lukuun 1, huolimatta siitä, mikä luku valitaan sarjan aloitusarvoksi. Toisin sanoen:

$\forall n \isin \mathbb{N} > 0 : \exists i \isin \mathbb{N}: a_i = 1$

Collatzin väittämää on tutkittu tietokoneita käyttäen huomattavan pitkälle. Elokuun 2005 alkuun mennessä on osoitettu, että Collatzin jono päätyy triviaaliin silmukkaan {1,4,2}, kun jonon ensimmäiseksi luvuksi valitaan mikä tahansa lukua $6 * 2 58$ (n. $1,729 * 10 18$ ) pienempi positiivinen kokonaisluku. Yhtään vastaesimerkkiä ei ole löydetty [1].

Väittämän kumoamiseksi tulisi löytää sellainen positiivinen kokonaisluku, josta alkava edellä kuvatulla tavalla muodostettu lukujono joko

-jatkuisi loputtomiin, ilman että sama luku esiintyy siinä kahta kertaa tai

-päätyisi silmukkaan, jossa ei esiintyisi lukua 1.

Lähteessä [2] on osoitettu, että mikäli jälkimmäinen näistä toteutuu jollakin Collatzin lukujonolla, ts. löytyy ei-triviaali silmukka, niin tämä silmukka on miljardien lukujen pituinen.