Liki aina loistava xkcd tietysti kertoi kaiken olennaisen jo jokin aika sitten. Otetaan mielivaltainen luonnollinen luku x, ja tarkastellaan sen esitystä 2-kantajärjestelmässä. Otetaan suurin luku k, siten, että x > 2k. Tällöin meillä on yksikäsitteinen esitys siten, että x = 2k + y. Binäärinä ajatellen y luku, joka saadaan, kun napataan x:n esityksestä eniten merkitsevä bitti pois.
Sovelletaan Collatzin otaksuman HOTPO-sääntöä x:ään siten, että merkitään lukua aina parina (u,v). Alussa se on siis (2k, y). Korostan, että tämä on vain merkintätapa. Alussa luvun parillisuus tässä esityksessä riippuu vain y:stä. Pidetään tämä esitys siten, että kun sääntöä sovelletaan parilliseen lukuun, niin luvusta (u,v) tulee (u/2, v/2). Kun sitä sovelletaan
parittomaan lukuun, niin luvusta (u,v) tulee (3u, 3v + 1). Jatketaan tätä niin kauan, kunnes luvun esityksessä (u,v) u on pariton. (Huom. tällöin tietysti ei vielä ole päästy oikeasti loppuun)
Tässä kohtaa u on väistämättä muotoa u = 3l; tämä on triviaalia todistaa, koska
u:lle ei voi mistään tulla muita tekijöitä kuin 3 ja 2, ja näistä saa parittoman vain, jos kakkosia ei ole. Lisäksi on triviaalia todistaa, että l on pienenmpi tai yhtäsuuri kuin k: vähintään toinen askel poistaa kakkosen tekijöiden joukosta ja korkeintaan joka toinen tuo yhden kolmosen lisää.
Tutkin eilen hypoteesia: jos parittomalle luvulle alussa (u,v) = (2k,y), niin sekvenssin "päättyessä" v on jokin kakkosen potenssi jos y ei ole muotoa 2m + 1 tai 2m - 1. Ensimmäinen luku, jolle tämä ei toimi, on x = 37. Esitys on tällöin (16,11) ja prosessi päättyy lukuun (27, 20). Tässä kohtaa lopetin.
4 kommenttia:
Ootko muuten nähnyt Sademiehen? :)
Olen nähnyt.
Meni pitkään, ennen kuin osasin kiinnostua ja innostua xkcd:stä, mutta nyt luen säännöllisesti. Hyviä oivalluksia useammin kuin vaikkapa Penny Arcadessa.
Oletetaan, että x on pienin sellainen luku, jolle HOTPO-algoritmi ei pysähdy.
Tiedämme, että x = 3 mod 4: Jos se olisi 0 tai 2, niin x olisi parillinen, eikä siten olisi pienin. Jos taas x = 1 mod 4, niin 3x + 1 on jaollinen neljällä, ja siten (3x + 1)/4 < x, joten x ei ole pienin.
Tiedämme myös, että x ei voi olla (3z + 1)/2 millekään kokonaisluvulle z, koska z olisi tällöin pienempi kuin x. Eli 2x != 3z+1, eli ei voi olla, että 2x = 1 mod 3, joten x != 2 mod 3. x:n jakojäännös 3:n suhteen ei siis ole 2.
Vastaavanlaisia väittämiä saadaan loputtomiin. Collatz voi todella viedä autismiin taipuvaisen ihmisen sellaisiin syvyyksiin, ettei sieltä enää ilman lääkkeitä nousta. Itselleni käy usein niin, että se imaisee silloin, kun joku tutkimusprojekti on juuri päättynyt ja pitäisi keksiä joku uusi.
Lähetä kommentti