Perlička: Collatzův problém
Neživá příroda | 29.09.10
Vezměme libovolné přirozené číslo. Pokud je sudé, vydělíme ho 2. Pokud je liché, vynásobíme 3 a přičteme 1. Podle tohoto algoritmu postupujeme dále...
Sdílet
U všech zatím známých čísel tímto postupem nakonec narazíme na mocninu 2, takže výsledkem operace je číslo 1. (respektive samozřejmě můžeme pokračovat 1 x 3 + 1 = 4, 4/2, 2/2, ale to už se točíme jen v kruhu a přestává to být zajímavé). Otázka však je, zda to tak platí úplně vždy. Obecnou větu se zatím nikomu dokázat nepodařilo; nás ostatní může těšit, že na rozdíl od jiných matematických problémů v tomto případě alespoň dokážeme snadno porozumět jeho formulaci :-).
Zdroj: Adrián Paenza: Matematiko, jsi to ty?, Kniha Zlín 2010
Poznámky:
Úloze se také říká syrakuský problém. Lothar Collatz ji ale zformuloval v roce 1937, podle všeho nejde o úlohu, jejíž historie by se táhla až do antiky (nebo snad nezávislá formulace?).
Existuje i projekt distribuovaných výpočtů, které z tohoto hlediska zkoušejí stále větší čísla. (Viz zde. Ovšem nepředpokládá se, že by se podařilo objevit protipříklad. Zajímavé je ale i „soutěžení“, kdy celý algoritmus běží nejdéle.)
Co když namísto násobení 3 zvolíme 5 nebo jiné liché číslo (a zase + 1)? Ustřelí nám pak hodnoty tak, že budou divergovat, nebo dříve či později i takto natrefíme na nějakou mocninu 2? Řekne nám eventuální důkaz věty pro 3x + 1 i něco o dalších lichých číslech?
Další články z rubriky
Související články
Nahrává se..
Videa
Chobotnice mění průhlednost stejně rychle jako displej Amazon Kindle
Maskování chobotnice se svou rychlostí vyrovná...
Komentáře
10.06.11, 20:57 jrjina
to headless:
nejen 16, ale i 4 (pro předcházející 1) 64, 256, 1024, protože pouze každá druhá mocnina dvojky (tj. mocnina čtverky) se může rovnat 3n+1, kde n je celé. Ostatní mocniny vznikají pouze jako n/2, ale jako 3n+1 vzniká pouze každá druhá mocnina dvojky. Důkaz je jednoduchý, pomocí kongruence.
03.10.10, 12:12 headless
opačný proces + jiná lichá čísla - celá verze
ak po pár minutách programování:
Podmínce, ((2^x - 1) mod 3 == 0) vyhovují všechna sudá x (? - zkoušeno do x 8192). Problém asi je, že jich je v celém tom rozsahu tak nějak "málo".
Pro 3 je vyhovujících do 2^8192 4097. Pro 5 už jen 2049. Tam je ještě zajímavé, že všechna čísla vyhovující 5 zároveň vyhovují i 3 a je jich "polovina". U 7 je to také zajímavé, s tím by se dalo vyblbnout dlouho...
K tomu cyklu - ono to byla taková náhoda, protože když jsem si to na počítači zkoušel, tak mi to většinou hodně rychle ustřelilo (za pár vteřin číslo na spoustu řádků obrazovky). Že zvolení "rozumnějšího" testovacího čísla povede k vyvrácení možnosti obecné konvergence by mě ani nenapadlo...
Na testování cyklů pro 7 by to chtělo také náhlé osvícení - na počítači by to spotřebovalo dost paměti...
03.10.10, 12:08 headless
opačný proces + jiná lichá čísla
ak po pár minutách programování:
podmínce, ((2^x - 1) mod 3 == 0) vyhovují všechna sudá x (? - zkoušeno do x
02.10.10, 22:42 pavelhouser
ano
no, oboje je fakt. ukazuje to, myslim, jak ani prirozena cisla nejsou ve svych vlastnostech nejak "prirozene" uchopitelna, alespon pro nematematika ne (ted si predstavte, ze pro 5 to neplati, ale pro 7 treba zadny cyklus nenajdeme; i kdyz, pravda, velikost cisla by nemusela tak souviset s existenci cyklu, protoze ustrelit nahoru to muze i u mensich cisel a bez toho, ze bychom nasli cyklus)
ad to 16: zkusit si s tim hrat "naopak" s jinymi mocninami 2?
02.10.10, 15:46 headless
konvergence u násobení 5
tak pro násobení 5 to zjevně obecně nekonverguje, protože např. u čísla 13 se dostaneme do cyklu 13>66>33>166>83>416>208>104>52>26>13
u násobení 3 mě překvapilo, že u všech čísel, co jsem si zkusil, je ta mocnina 2, ke které algoritmus dojde, 16...
Napsat vlastní komentář
Pro přidání příspěvku do diskuze se prosím přihlašte v pravém horním rohu, nebo se prosím nejprve registrujte.