Výpočetní ověření Collatzovy domněnky až do velikosti 2⁶⁸

Collatzova domněnka je jednou z nejznámějších nevyřešených problémů v matematice. Domněnka se zabývá otázkou, zdali iterace funkce:

dosáhnou vždy čísla 1, nezávisle na tom, na kterém čísle jsme začali. Příkladem může být počáteční číslo 12 a jeho trajektorie 6, 3, 5, 8, 4, 2, 1. Domněnka zatím nebyla dokázána. V roce 2020 byla ale výpočetně ověřena pro všechna čísla až do velikosti 2⁶⁸. V tomto článku si vysvětlíme, jak toho bylo dosaženo.

Nejprve se zamysleme, jak ověřování čísel probíhá. Je skutečně třeba počítat iterace téhle funkce až do 1? Není. Pokud jednotlivá počáteční čísla ověřujeme po jednom od nejmenšího po největší, stačí sledovat trajektorii pouze, pokud počítané nespadne pod svoji počáteční hodnotu. Tedy u počátečního čísla 12 je v prvním kroku spočtena 6, což je číslo menší než 12, tudíž jsme ho již ověřovali a můžeme skončit.

Slučování vícero kroků

Teď krátká úvaha ke slučování vícero lichých a sudých kroků do jedné operace. Raději než abychom definovali T(n) jako v rovnici výše, a sledovali trajektorii na n, můžeme sledovat stejnou trajektorii na n + 1 s pomocnou funkcí:

Tím se násobení trojkou přesunulo do sudé větve n ≡ 0 (mod 2). Trik je v tom, že při výpočtu iterací funkce přepínáme mezi n a n + 1 tak, že vždy použijeme pouze sudou větev, buď T nebo T₁. Proto lze výše uvedené funkce vyjádřit jako:

a

V každém lichém kroku jsou zdánlivě dvě aditivní operace. Budeme-li uvažovat binární reprezentaci n, těmto aditivním operacím se lze téměř vyhnout sloučením několika sudých kroků do jednoho. Jinými slovy, používáme operaci, která počítá počet koncových nulových bitů následujících po nejméně významném nenulovém bitu (operace ctz, count trailing zeros), a poté provádíme více dělení dvěma (posuny doprava) najednou.

To také zahrnuje provádění několika násobení třemi najednou. Mocniny tří však mohou být předem spočítány v malé vyhledávací tabulce (LUT, look-up table) a pak se nám série násobení mění na jedno násobení s jedním prvkem v LUT.

Nový algoritmus

Výše zmínené slučování více sudých a lichých kroků lze zapsat pomocí následujícího algoritmu.

Input: n0 : kladné celé číslo

1: n := n0
2: repeat
3: 	n := n + 1
4: 	α := ctz(n)
5: 	n := 3α n / 2α
6: 	n := n - 1
7: 	β := ctz(n)
8: 	n := n / 2β
9: until n < n0

Tabulka s mocninami tří umožňuje vyhnout se umocňování 3^α. Dělení 2^α a 2^β jsou bitové posuny doprava. Operace ctz() odpovídá v moderních procesorech jedné instrukci. Lze ověřit, že pro liché n je průměrný počet iterací vypočítaných v jedné iteraci repeat-until smyčky čtyři iterace funkce T(n).

Výhodou tohoto algoritmu je to, že po řádku 6 máme v ruce vždy maximum z dané iterace smyčky. Lze tak snadno hledat maximální číslo dosažené na trajektorii počátečního čísla n₀.

Je znám algoritmus, který spočte více než 4 iterace funkce T(n) v jednom kroku. Označme T^k(n) kátou iteraci funkce T(n). Pak dostáváme rovnici T^k(2^kn_H + n_L) = 3^odd(n_L)n_H + T^k(n_L), kde odd(n_L) je počet lichých kroků T(n), který byl vykonán ve výpočtu T^k(n_L).

Některé projekty používají tuto rovnici k výpočku k iterací funkce T(n) najednou. Nevýhodou však je to, že přeskočením k iterací můžeme lehce minout maximum. Nelze tak hledat maximální číslo na trajektorii.

Jak ověřit čísla až po 2⁶⁸?

Máme tedy k dispozici algoritmus, o něco rychlejší než naivní počítání iterací funkce T(n). Můžeme tedy přistoupit k vlastnímu výpočetnímu ověřování Collatzovy domněnky. V projektu, který v roce 2020 dosáhl hranice 2⁶⁸, se postupovalo následovně. Chceme ověřit, jestli všechna čísla 1 až 2⁶⁸ konvergují k cyklu procházejícím číslem 1. Těchto 2⁶⁸ čísel rozdělíme do pracovních jednotek o velikosti 2⁴⁰. Musíme tedy ověřit 2²⁸ pracovních jednotek.

Velikost pracovní jednotky byla zvolena s ohledem na to, že verifikace pomocí výše uvedeného algoritmu bude trvat jednotky sekund až jednotky hodin, záleží na použitých algoritmech a hardwaru. Počet pracovních jednotek 2²⁸ je 268 435 456, každá z nich se s použitím chytrých algoritmů a výkonného hardwaru bude ověřovat jednotky sekund (to je případ GPU) až jednotky minut (odpovídá výpočtu na CPU).

Protože počet pracovních jednotek by byl na jednotkách počítačů, které má běžný uživatel k dispozici, neupočitatelný, nastupují do hry superpočítače. Využívaly se k tomu nejvýkonnější superpočítače v České republice a ve Finsku. Výpočet probíhal z části na CPU a z části na GPU. Začal v září 2019 a skončil v květnu 2020.

Všechny zdrojové kódy jsou jako otevřený software k dispozici na GitHubu. Protože v projektu se taktéž hledala taková počáteční čísla, v jejichž trajektorii se nechází maximum, které je větší než všechna dříve dosažená maxima, máme k dispozici také pěknou tabulku s těmito maximy.

Reference

• Barina, D. Convergence verification of the Collatz problem. J Supercomput 77, 2681–2688 (2021).