reklama

Collatzov hlavolam - v číslach je poriadok

Collatzova hádanka ešte stále nie je rozlúštená. To ale neznamená, že sa o tejto matematickej hypotéze nemá čo povedať. Čísla, ktoré dostávama vo výsledkoch pri používaní algoritmu, nemusia byť také chaotické, akoby sa mohlo zdať.

Písmo: A- | A+
Diskusia  (1)

Collatzov algoritmus je definovaný týmti krokmi:

  1. zvoľte si ľuboboľné prirodzené číslo, vo všeobecnosti ho označme výrazom x.

  2. Ak je x nepárne, vypočítajte, koľko je y = 3x + 1.

  3. Ak je x párne, vypočítajte y = x / 2.

  4. Výsledok dosaďte znova za x: x = y a vráťte sa ku druhému kroku.

V Collatzovom algoritme teda po každom kroku vyhodnocujeme, či sme dostali párne alebo nepárne číslo a podľa toho si vyberáme ďalší krok. Collatzov predpoklad znie tak, že nech si vyberieme akékoľvek prirodzené číslo, aj tak sa raz dostaneme k hodnote x = 1.

Poďme si ukázať, ako sa striedajú spomenuté dva pravidlá (krok 2 a krok 3) pri počítaní v Collatzovom algoritme.

Koľkokrát za sebou môžeme urobiť prvé pravidlo: 3x +1 = y?

Ake sme si už povedali, toto pravidlo robíme len pre nepárne čísla. Ako často za sebou k tomu môže dôjsť?

(x modulo 2 = 1) => 3x + 1 modulo 2 =0

SkryťVypnúť reklamu
Článok pokračuje pod video reklamou

Ak je x nepárne tak súčet 3x + 1 bude párnym číslom. Prvé pravidlo teda nemôžeme použiť viac ako jeden krát za sebou.

Koľkokrát za sebou môžeme použiť druhé pravidlo v = y/ 2?

Toľkokrát, koľkokrát bude výsledok “3x + 1” deliteľný výrazom 2ⁿ., kde n je ľubovoľné prirodzené číslo (patrí do množiny N). Druhé pravidlo potom použijeme práve n-krát.

Ako zistíme maximálne “n” z výrazu: 2ⁿ? Kedy je výraz “3x + 1” ešte deliteľný dvomi a kedy už nie? Vieme na to prísť aj z vlastností čísla x?

Urobme si malý prieskum situácie. Vypíšme si niekoľko menších nepárnych čísel a zistime, ako sa postupne bude meniť hodnota n. V nasledujúcej tabuľke sú vypísané všetky nepárne čísla menšie ako 57. Je v nej vypočítaný krok “3x + 1”, ako aj “n”, teda to, koľkokrát budeme musieť následne deliť dvomi.

SkryťVypnúť reklamu
reklama
Tabuľka 1
Tabuľka 1 (zdroj: Tomáš Teicher)

Je na tejto tabuľke niečo pozoruhodné?

Rôzne čísla y v tabuľke smerujú k rôzne veľkým hodnotám n. Tretí stĺpec som zafarbil tak, aby tie isté hodnoty n boli zafarbené tou istou farbou. V našej vzorke nepárnych čísiel vyšla najväčšia hodnota n pri čísle 21 a to n = 6.

Všimnite si, že výsledky vo farebnom stĺpci nie sú také chaotické, ako by sa mohlo zdať. Premenná n má hodnotu 1 práve v každom druhom riadku. Hodnotu 2 sú oproti tomu v každom štvrtom riadku a hodnotu 3 máme v každom ôsmom riadku. Ćím väčšie n, tým sa v tabuľke vyskytuje zriedkavejšie. Akoby rozdiely medzi číslami s rovnakou hodnotou n boli zároveň aj násobakmi čísla 2ⁿ (každý druhý, každý štvrtý alebo každý ôsmy riadok). Ide o náhodu alebo majú tieto nepárne čísla niečo spoločné?

SkryťVypnúť reklamu
reklama

Poďme sa na takéto čísla pozrieť bližšie. Počítajme Collatza pre výraz x a pre výraz posunutý o 2ⁿ riadkov nižšie: (x + 2ⁿ)

Predpokladajme, že 3x + 1 < 2ⁿ

  • 3(x + 2ⁿ) + 1 = 3x + 3*2ⁿ + 1

Z takéhoto zápisu vidíme, že nepárne čísla, ktoré sú v tabuľke od seba vzdialené o 2ⁿ riadkov, budeme deliť rovnaký počet krát ako delíme aj x.

Táto hypotéza by mala platiť aj pre nekonečne veľké čísla. Ako preukážeme pravidelné striedanie farieb pre n-násobné delenie?

Ukážme si to, ale pre zmenu si skúsme Collatzovu úlohu prepísať do dvojkovej sústavy.

Ako sa v dvojkovej sústave počíta výraz 3x + 1?

V dvojkovej sústave sa nepohodlne násobí tromi. Zato sa v nej veľmi pohodlne násobí dvomi.

Výraz 3x + 1 si môžeme napísať aj v takomto tvare:
 

SkryťVypnúť reklamu
reklama
  • 3x + 1 = x + 2x + 1.

Násobenie dvomi už zvládneme, v dvojkovej sústave stačí pripísať jednu nulu na koniec čísla a už máme hotovo. Budeme násobiť napr. číslo 13:

v dvojkovej sústave: 1101

  • x + 2x + 1:

  •  

  •  1101

  • 11010

  •  1

  • --------


Teraz to už len spočítame a vyjde nám výsledok 101000 (teda v desiatkovej sústave 40). Po pravidle “3x + 1” musíme použiť pravidlo delenia dvomi. Ale koľkokrát máme výsledok deliť dvomi? Číslo 40 je deliteľné ôsmimi (to je 2³) teda dvomi delíme spolu trikrát. V dvojkovej sústave sa dá oveľa rýchlejšie zorientovať v tom, koľko krát máme deliť. V tejto sústave sa ľahko dvomi nielen násobí ale aj delí. Pri každom delení dvomi treba od konca čísla odobrať práve jednu nulu. Náš výsledok 101000 má na konci až tri nuly, preto musíme deliť dvomi práve trikrát po sebe.

V zápise čísla v dvojkovej sústave sa nám teda pracuje veľmi dobre (keď delíme dvomi). Ako to využijeme pri preverovaní našej hypotézy, že farebné riadky v tabuľke sa opakujú s nejakou konkrétnou pravidelnosťou?

Keď máme číslo zapísané v dvojkovej sústave, tak každá jedna číslica zapisuje iné 2ⁿ desiatkovej sústavy (n patrí do N) . Napr. číslo 40 má takýto zápis:

1101 (v dvojkovej sústave) = 1*2³ + 1*2² + 0*2¹ + 1*2° = 40 (v desiatkovej sústave)

My budeme v Collatzovom algoritme robiť operáciu sčítavania. Pri sčítavaní čísel dvojkovej sústavy samozrejme postupujeme rovnako, ako pri sčítavaní čísel v akejkoľvek inej sústave. Teda začíname “zprava” (od konca) - od číslic, ktoré reprezentujú najmenšie mocniny čísla dva. Postupne prichádzame k čísliciam zprava do ľava. V tabuľke 1 je výsledok čísla 13 zafarbený rovnakou farbou ako napr. číslo 29. Tieto dva čísla majú teda niečo spoločné. Prepíšme si aj toto druhého číslo do dvojkovej sústavy a zistime, o čo konnkrétne ide:

  • 29 = 2⁴ + 2³ + 2² + 0*2¹ + 2° = 11101 v dvojkovej sústave.

Všimnime si, že čísla 29 a 13 (teda 11101 a 01101) majú naozaj niečo spoločné – majú takmer rovnaký zápis v dvojkovej sústave. - majú rovnaké posledné 4 číslice, hoci v piatej od konca sa už líšia. Pri sčítavaní začíname zprava, preto aj výsledky výrazu 3x + 1 budú mať v oboch prípadoch štyri rovnaké cifry. Rozdiel medzi čísalmi 29 a 13 je 16, čo je 2⁴. Môžeme teda zovšeobecniť takýto záver:

Ak je rozdiel medzi dvoma nepárnymi číslami rovný 2ⁿ, tak výsledky výrazu 3x + 1 týchto čísel bude (v prepise do dvojkovej sústavy) totožný práve v n cifrách za sebou (zprava).

V našom prípade sú to cifry “1000”. Pri štvrtej cifre sa sled núl zastavil, teda sme navyše zistili, koľkokrát sme museli deliť desiatimi v dvojkovej sústave (3 krát). Pri delení dvomi tieto nuly odstránime, jednotka (zatiaľ) ostane. Čím viac rovnakých cifier ostane číslam aj po delení, tým viac sa bude podobať ich ďalší osud v Collatzovom algoritme aj po ďalších krokoch. V obidvoch operáciách (krok 2 aj krok 3 v zadaní algoritmu) budú bezprostredne nasledujúce kroky závisieť od posledných cifier čísel zapísaných v dvojkovej sústave. Skúsme si napríklad z Tabuľky 1 vybrať len také nepárne čísla, v ktorých výraz n vyšiel n = 2. Ako budú vyzerať výsledky v ďalších krokoch? To si znázorníme v Tabuľke 2:

Tabuľka 2
Tabuľka 2 (zdroj: Tomáš Teicher)

Ako vidíme, znova dostaneme pravidelne opakujúcu sa paletu farieb v stĺpci pre ďalšie delenie dvomi. Čísla, ktoré dostávame vykonávaním Collatzovho algoritmu teda nie sú také chaotické, akoby sa mohlo zdať na prvý pohľad.

Tomáš Teicher

Tomáš Teicher

Bloger 
  • Počet článkov:  38
  •  | 
  • Páči sa:  2x

Aktivista, člen Komisie mestského zastupiteľstva v Banskej Bystrici pre modernú samosprávu (komisia sa zmariava na oblasť IT a transparentnosť) Zoznam autorových rubrík:  FikciaSúkromnéNezaradené

Prémioví blogeri

Yevhen Hessen

Yevhen Hessen

20 článkov
Juraj Hipš

Juraj Hipš

12 článkov
Karolína Farská

Karolína Farská

4 články
Lucia Šicková

Lucia Šicková

4 články
Pavol Koprda

Pavol Koprda

10 článkov
reklama
reklama
SkryťZatvoriť reklamu