Collatzin konjektuuri

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 ehkä vielä valmis tämän kaltaisiin ongelmiin".

Väittämä voidaan havainnollistaa 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 riippumatta siitä, mikä luku valitaan sarjan aloitusarvoksi. Toisin sanoen:

\forall n\in \mathbb {N} >0~\exists i\in \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⁵⁸ (n. 1,729 × 10¹⁸) 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.

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.^[2]

Collatzin konjektuuria pyritään ratkaisemaan samannimisessä projektissa BOINC-alustalla.

Lähteet

↑ Tomás Oliveira e Silva: Computational verification of the 3x+1 conjecture.
↑ Sinisalo, Matti K.: On the minimal cycle lengths of the Collatz sequences, Preprint, kesäkuu 2003, Oulun yliopisto ([1]).

Aiheesta muualla

Kuvia tai muita tiedostoja aiheesta Collatzin konjektuuri Wikimedia Commonsissa

[1] Tomás Oliveira e Silva: Computational verification of the 3x+1 conjecture.

[2] Sinisalo, Matti K.: On the minimal cycle lengths of the Collatz sequences, Preprint, kesäkuu 2003, Oulun yliopisto ([1]).

[1]

[2]