Collatzov hlavolam - 2. časť: algoritmus obrátený hore nohami

Collatzova hypotéza je matematický oriešok, ktorý ešte len čaká na svoje rozlúsknutie. V tomto blogu si ukážeme jeden z prístupov, ktorý by nám mohol pomôcť k úspechu.

Collatzov algoritmus je definovaný týmito krokmi:

zvoľte si ľuboboľné prirodzené číslo, vo všeobecnosti ho označme výrazom x.
Ak je x nepárne, vypočítajte, koľko je y = 3x + 1.
Ak je x párne, vypočítajte y = x / 2.
Výsledok dosaďte znova za x: x = y a vráťte sa ku druhému kroku.

Collatzova hypotéza hovorí, že hoci si v prvom kroku vyberieme akékoľvek prirodzené číslo, raz sa v štvrtom kroku dostaneme k hodnote x = 1.

Collatzov algoritmus hore nohami – násobíme dvomi a delíme tromi

V predošlom blogu sme si ukázali, že čísla, ktoré dostaneme vykonávaním Collatzovho algoritmu, nevyznievajú až tak chaoticky akoby sa mohlo na prvý pohľad zdať. Zaujímavé veci sa o algoritme môžeme dozvedieť aj vtedy, keď úlohu otočíme – zaradíme spätný chod. Práve o obráternom postupe Collatzovho algoritmu budeme hovoriť v tomto blogu.

Otočme teda obidva pravidlá:

x patrí do N:
krok A: y = x * 2
krok B: y = (x – 1) / 3

Kedy môžeme urobiť ktorý krok?

Podľa Wikipédie si pri obrátenom postupe môžeme vybrať v každom momente ľubovoľný z dvoch krokov. Jediným obmedzením je pre nás podmienka, aby výsledná hodnota y bola tiež prirodzeným číslom (platnosť tohto tvrdenia si v tomto blogu nebudeme dokazovať).

Pre niektoré hodnoty x platí, že podmienku (y patrí do N) spĺňajú naraz obidva kroky (A aj B). Ktorou cestou sa vtedy vyberieme? Ak bude našim cieľom hĺadanie všetky čísiel, ktoré spĺňajú Colatzovu hypotézu, musíme sa vybrať všetkými možnými cestami.

Pri akých číslach môžeme urobiť krok A?

ak x patrí do N, tak aj x * 2 patrí do N

Krok A teda môžeme zvoliť v každom momente.

Pri akých číslach môžeme urobiť krok B?

Tento krok už bude mať niekoľko úskalí. Výraz (x - 1) musí byť deliteľný menovateľom (v našom prípade tromi), aby bol výsledok prirodzeným číslom. Musí platiť:

x – 1 mod 3 = 0
z toho vyplýva: x mod 3 = 1

V Collatzovom algoritme platí:

3x + 1 mod 2 = 0

Z toho vyplýva, že krok B môžeme vykonať len pri párnych číslach aj to len pri niektorých z nich.

Vyskúšajme si rátanie takéhoto opačného postupu aj na príkladoch:

x = 5
1. krok A: y = 5 * 2 = 10
2. krok B: y = (10 – 1) / 3 = 3

Vyberme si ai iné nepárne číslo:

x = 9
1. krok A: y = 9 * 2 = 18
2. krok B: y = (18 – 1) / 3 = 5 + 2/3

Číslo 9 teda nestačí násobiť dvomi len raz, ak chceme v ďalšom kroku prejsť do pravidla B.

Ako zistíme, koľkokrát za sebou musíme urobiť krok A, aby sme mohli prejsť do kroku B? Ako sme si už povedali, pre hodnotu x musí v takom prípade platiť:

x mod 3 = 1

Urobíme si krátky prieskum pri najmenších nepárnych číslach.

1*2 mod 3 = 2
3*2 mod 3 = 0
5*2 mod 3 = 1
7*2 mod 3 = 2
9*2 mod 3 = 0
11*2 mod 3 = 1
13*2 mod 3 = 2
15*2 mod 3 = 0
17*2 mod 3 = 1

Zatiaľ to vyzerá tak, že pri každom treťom nepárnom čísle by sme mohli prejsť do kroku B hneď po prvom násobení dvomi. Platí takáto pravidelnosť aj vo všeobecnosti, teda aj pre čísla väčšie, ako máme v našom príklade? To si overíme trocha neskôr. Zvyšok po delení tromi sa pri postupnosti nepárnych čísel strieda akoby so železnou pravidelnosťou. Striedajú sa hodnoty 2, 0 a 1. Prečo je tomu tak - ide o náhodu?

Nie je to náhoda. Ak si z postupnosti nepárnych čísel vyjmeme len každé tretie číslo, tak rozdiel medzi nimi bude rovný 6. Takýto rozdiel 6 (čiže 2*3) je deliteľný tromi a preto nijak nezasahuje do zvyšku:

x mod 3 = (x + 6) mod 3

Tie čísla, pri ktorých vychádza zvyšok nevhodný pre krok B, skúsime vynásobiť dvomi ešte raz:

1*2*2 mod 3 = 1
7*2*2 mod 3 = 1
13*2*2 mod 3 = 1

Teraz už tieto čísla majú ten správny zvyšok pre krok B. Ešte nám na preskúmanie ostala tretia skupina nepárnych čísel. To sú tie, pre ktoré platí:

a * 2 mod 3 = 0

Pre tieto čísla sa nebude dať nikdy uplatniť krok B, pretože platí:

a * 2ⁿ mod 3 = 0 (pre každé n patrí N)

Ďalej sa preto tejto skupine nepárnych čísel nebudeme zvlášť venovať.

Ako zistíme, ktoré nepárne číslo musíme koľkokrát násobiť dvomi, aby sme mohli prejsť ku kroku B? Skúsme teda nepárne číslo násobiť opakovane dvomi a sledujme, ako sa postupne v medzivýpočtoch mení zvyšok po delení tromi. Stanovme si premennú c, kde c patrí do N:

3c + 2 mod 3 = 2
(3c + 2) * 2 = 6c + 4
6c + 4 mod 3 = 1
3c + 1 mod 3 = 1
(3c + 1) * 2 mod 3 = 6c + 2
6c + 2 mod 3 = 2

Dokázali sme si, že ľubovoľné nepárne číslo môžeme dookola násobiť dvomi a zvyšok sa bude zakaždým meniť z 1 na 2 a z 2 na 1 a tak dookola. Platí to všeobecne pre každé c, ktoré patrí do N. Z toho vyplýva, že niektoré nepárne čísla musíme násobiť dvoma práve párny počet krát, iné zase práve nepárny počet krát, aby sme (pred krokom B) dostali želaný zvyšok 1. Napr. číslo 5:

(5 * 2 – 1) / 3 = 3
(5 * 2 * 2 – 1) / 3 = chyba
(5 * 2 * 2 * 2 – 1) / 3 = 13
(5 * 2 * 2 * 2 * 2 – 1) / 3 = chyba

Každé tretie nepárne číslo teda násobíme (okrem iného) aj jedenkrát aby sme mohli prejsť ku kroku B.

Košatý strom čísel uviaznutých v Collatzovej hypotéze

Keď som písal o obrátenom postupe Collatzovho algoritmu, sľúbil som, že pôjdeme od konca, teda od čísla 1 smerom k nekonečnu. Napriek tomu som si vtedy vybral do príkladu iné číslo: 5. Poďme to teraz napraviť a začnime naozaj od konca – od čísla 1. Postupne bude strom čísel košatieť, lebo pri hľadaní nových čísel budeme vytvárať jeho vetvy. Pri niektorých číslach sa bude dať ísť oboma cestami (bude sa dať urobiť krok A, ale aj krok B). My budeme mapovať všetky možné cesty a práve preto budeme vytvárať vetvy stromu, krorý má koreň v čísle 1. Vytváranie stromu si o poznanie zjednodušíme, ak namiesto krokov A a B budeme uvažovať vo všeobecnosti o takejto skupine krokov:

(x * 2ⁿ - 1) / 3

Za x budeme pritom dosadzovať len nepárne čísla. Vo výslednom strrome budú taktiež len nepárne čísla. Párne hodnoty sa stratia v medzivýpočtoch (násobením 2ⁿ ). Pri potvrdzovaní Collatzovej hypotézy sa pritom o nič neukrátime. Ak hypotézu spĺňajú všetky nepárne čísla, tak ju spĺňajú aj všetky prirodzené čísla. Všetky párne čísla sa totiž v Collatzovi skôr či neskôr dostanú aspoň k jednému nepárnemu číslu (opakovaným delením dvomi). V novom zápise máme teda nový parameter n a práve ten spôsobí, že strom bude rýchlo “košatieť”. Za parameter n môžeme dosadiť ľubovoľné prirodzené číslo, ktoré spĺňa podmienku z predošlých odstavcov (o párnosti resp. nepárnosti n). Poďme vytvoriť niekoľko prvých vetiev, ktoré budú vychádzať z čísla 1:

(1 * 2 – 1) / 3 = 1
(1 * 2³ – 1) / 3 = 5
(1 * 2⁵ – 1) / 3 = 21
(1 * 2⁷ – 1) / 3 = 85
(1 * 2⁹ – 1) / 3 = 341

Vytvorili sme teda prvých 5 vetiev stromu. Je na týchto výsledkoch niečo podozrivé, niečo, čo by nám ukázalo, že majú niečo spoločné? Prvá vetva sa vracia do koreňa (výsledok je 1). Toto je zároveň jediná anomália nášho stromu, kto to kedy videl, aby sa vetva vrátila späť do koreňa! A čo ostatné vetvy? Na prvý pohľad sa čísla môžu zdať chaotické. Nové výhonky majú toho istého predka – číslo 1. Ale na to, že sú to súrodenci, tak sa veľmi na seba nepodobajú. Prepíšme si tieto čísla do dvojkovej sústavy a zistíme, či to nebude vyzerať o niečo lepšie.

1₁₀ = 1₂
5₁₀ = 101₂
21₁₀ = 10101₂
85₁₀ = 1010101₂
341₁₀ = 101010101₂

Akoby by ich jedna mater mala! Čisla sa na seba naozaj podobajú. Nových súrodencov v dvojkovej sústave vypočítate jednoducho tak, že predošlého súrodenca skopírujete a len na jeho koniec dopíšete dve číslice “01”. Prečo to takto funguje? Nejde len o náhodu? Vráťme sa na chvíľu do desiatkovej sústavy a v nej si to ukážeme: Povedzme, že máme nepárne číslo x. Postupujeme podľa “klasického” Collatza, teda násobíme tromi a delíme dvomi. Dostaneme sa k číslu: (3x + 1) / 2ⁿ. Teraz sa vrátime ku “opačnému” Collatzovi a budeme hľadať súrodencov k číslu x.

((3x + 1) / 2ⁿ * 2ⁿ+2 – 1) / 3 = 4x + 1

Súrodenci sa teda od seba líšia tak, že ak jeden je x, tak jeho bezprostredný mladší súrodenec je 4x + 1. Dokázali sme si to vo všeobecnosti, teda ďalší súrodenec bude číslo 4 (4x + 1) + 1. Prečo sa podobnosť čísel ukázala práve v dvojkovej sústave? V dvojkovej sústave totiž počítame výraz 4x + 1 nasledovným spôsobom:

Číslo vynásobíme štyrmi tak, že ku číslu sprava pripíšeme dve nuly na konci (násobíme 100-mi)
Ku párnemu číslu pripočítame jednotku tak, že poslednú nulu zprava nahradíme jednotkou.

Práve pre takéto pravidlá vyzerajú v obrátenom Collatzovi všetci súrodenci ako "cez kopirák".

Čo z toho vyplýva, že vieme, že súrodenci sa riadia výrazom 4x + 1? Ternto výraz si môžeme prepísať do inej podoby a bude čitateľnejší:

4x + 1 = x + 3x + 1

Čo je na tomto prepise zrozumiteľnejšie? Z takéhoto zápisu vidíme, že každý ďalší súrodenec má posunutý zvyšok po delení tromi. Výraz 3x je “neutrálny” z pohľadu delenia tromi, lebo nič zo zvyšku neuberá ani neprídáva. Jednotka na konci ten zvyšok vždy trocha posunie. Ak si vyberieme troch hocijakých súrodencov idúcich hneď po sebe, tak každý z nich má odlišný zvyšok po delení tromi. V praxi to má taký dôsledok, že traja súrodenci budú mať tri rôzne osudy: ako sme si ukázali vyššie. Pre každý zo zvyškov 0, 1 a 2 platí odlišný postup. Tie čísla, ktoré sa násobia nepárny počet krát, tak sa násobia aj jedenkrát. V takých situáciách vyjde prvý potomok menší ako jeho rodič x:

x > (x * 2¹ -1 ) / 3

Vo všetkých ostatných prípadoch platí:

x < (x * 2ⁿ -1 ) / 3

V predošlom blogu sme si ukázali, že čísla v Collatzovom algoritme "neskáču" až tak náhodne akoby sa mohlo zdať. Zoradenie čísel podľa veľkosti nie je jediná možnosť, ako mať v číslach poriadok. V tomto blogu sme si ukázali, že istý poriadok sa dá nájsť aj v "Colatzovi" obrátenom hore nohami - pri hľadaní čísiel od jednej k nekonečnu.

Páčil sa Vám tento článok? Pridajte si blogera medzi obľúbených a my Vám pošleme email keď napíše ďalší článok

Collatzov hlavolam - 2. časť: algoritmus obrátený hore nohami

Collatzov algoritmus hore nohami – násobíme dvomi a delíme tromi

Košatý strom čísel uviaznutých v Collatzovej hypotéze

Ďalšie články blogera

Ďalšie články z rubriky veda a technika

Hlavné správy

Testovanie začne už v pondelok. Dokedy sa treba otestovať a čo sa zmení?

Dobré ráno: Dotácie na rodovú rovnosť rozdali čudne

Hluchá linka, nefunkčná appka

Už ste čítali?

Koľko vakcíny nemocnice vyhodia? Priznala sa len Bratislava

Zmenky sfalšovali. Ako Jankovská vťahuje Smer do tejto kauzy

Imunita po vyliečení sa z covidu pretrvá dlhšie, ako sa čakalo

Sulíka chceli nahrávkou usvedčiť z klamstva, tá ukázala nedorozumenie

Čo pre Kočnera znamená rozsudok 19 rokov a aké má ešte možnosti? (otázky a odpovede)