Collatzi hüpotees

Vali algväärtus ja vaata, kuhu reegel selle viib. Seejärel uuri teist pilti, kus on korraga näha kõik algväärtused kuni piirini.

Näidisarvutus — Collatzi hüpotees

Kogu peatumisaeg	111
Kõrgeim saavutatud väärtus	9232
Kõrgeim väärtus ÷ algväärtus	341,93
Suurim vahe naabriga	101
Poolitamisi kolmekordistamise kohta	1,7073
Orbiit ilma +1 liitmisteta	0,8341
Lõpptulemus	Jõuab üheni
Pikim orbiit kuni 10 000	261

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

27 vajab 111 sammu. Selle naaber aga kümmet. 🖖

Määra algväärtuseks 26. Orbiit on 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Kümme sammu ja see ei tõuse kordagi üle 40.

Nüüd proovi arvuga 27. See vajab 111 sammu ja kerkib väärtuseni 9 232, mis on algsest 341,93 korda suurem.

Miski arvu 27 juures ei viita sellele. See asub 26 ja 28 vahel ning 28 jõuab pärale 18 sammuga. Rida Suurim vahe naabriga näitab selleks vaheks 101. Lohista algväärtust edasi ja märkad, et alumise paneeli punktid ei moodusta kunagi sujuvat kõverat.

Järseim hüpe alla 10 000 on 225 ning selle saavutavad kuus naaberarvude paari. Esimene neist on 6 170 ja 6 171: üks vajab 36, teine 261 sammu.

Kolm neljandikku iga kolmekordistamise kohta ja see peab pidevalt paika 🖖

Paaritu arv muutub kujule 3n + 1. Kuna tulemus on paaris, järgneb alati poolitamine. See väärtus jagub 4-ga pooltel kordadel ja 8-ga veerandil kordadest, mistõttu järgneb keskmiselt kaks poolitamist. Üks kolmekordistamine ja kaks poolitamist korrutavad arvu läbi ¾-ga.

Vii see lõpuni ja näed, et n-i üheni viimiseks vajalike kolmekordistamiste arv peaks olema umbes ln n ÷ ln(4/3), mis on 3,4761 ln n.

Tulemuste tabel võrdleb seda skaneeringu iga algväärtusega. Kuni 10 000 on kolmekordistamiste keskmine arv 28,21 ja ¾ reegel ennustab 28,54. Kuni 1 000 on see 19,67 võrrelduna 20,57-ga. Kuni 100 000 puhul 35,65 võrrelduna 36,54-ga.

Kogu arutelu tugineb fraasile keskmiselt. Ühe orbiidi poolitamised pole sõltumatud mündivisked; need on paika pandud hetkel, mil valid n-i. Keegi pole aga leidnud viisi, kuidas seda matemaatiliselt väljendada nii, et vastus säiliks. Paul Erdős on Jeffrey Lagariase 1985. aasta artiklis tsiteerituna öelnud: „Matemaatika pole sellisteks probleemideks veel valmis.“

Asenda 3 arvuga 5 ja sama reegel püüab 27 igaveseks lõksu 🖖

Vajuta 5n + 1 ja määra alguseks 13. Orbiit kulgeb 13, 66, 33, 166, 83, 416, 208, 104, 52, 26 ja naaseb tagasi 13 juurde. Kümme arvu ja tsükkel kordub täpselt nii kaua, kuni lased sel käia. Siin ei ole midagi oletuslikku; see on jada, mille saad minutiga käsitsi üle kontrollida.

Ka 27 jääb lõksu, ent teise kümnearvulisse tsüklisse: 27, 136, 68, 34, 17, 86, 43, 216, 108, 54.

Heuristika selgitab, miks. Kolmekordistamine ja kaks poolitamist annavad kokku ¾; viiekordistamine ja kaks poolitamist on aga 5/4. Reeglil, mis keskmiselt 5/4-ga korrutab, pole mingit põhjust kahaneda. Jäta 5n + 1 valituks ja uuri alumist paneeli, mis on nüüdseks peaaegu tühjaks jäänud. Esimesest 10 000 algväärtusest jõuab üheni vaid 256. Veel 470 satuvad tsüklisse. Ülejäänud 9 274 kasvavad üle 2⁵³. Sealt alates kaotab tööriista arvutusvõimekus täpsuse ja jälgimine katkeb.

Seega peab Collatzi hüpoteesi tõestus suutma eristada 3 ja 5 vahelist erinevust. Aastaks 2025 on reeglit kontrollitud iga algväärtuse puhul kuni 2⁷¹, mis teeb ligikaudu 2,36 × 10²¹ arvu. Selle töö tegi David Bařina Euroopa superarvutitel. Järgmine on endiselt lahtine.

Ülesanne täielikult lahendatud

Miks vajab 27 koguni 41 kolmekordistamist, kui arvutus näitab kahtteist 8 sammu
¾ reegel ütleb, et orbiit vajab pärale jõudmiseks umbes ln n ÷ ln(4/3) kolmekordistamist. Kui n = 27, jääb see üheteistkümne ja kaheteistkümne vahele. Tööriist aga näitab arvu 41. Uuri välja, kust need lisandunud kakskümmend üheksa tulid, ning kasuta seejärel sama arvestust suurima seni kontrollitud algväärtuse peal.

Ava see ülesanne tööriistas
1. Paaritust n-ist järgmine väärtus on 3n + 1, mis on paaris, mistõttu järgneb vähemalt üks poolitamine. See jagub 4-ga pooltel kordadel, 8-ga veerandil kordadest, 16-ga kaheksandikul kordadest ning oodatav poolitamiste arv on summa k·2^−k, mis on täpselt 2. Kolmekordistamine, millele järgneb kaks poolitamist, korrutab arvu läbi ¾-ga.
  
  $E [v_{2} (3 n + 1)] = k \geq 1 \sum k 2^{- k} = 2 ⟹ \frac{3}{2 ^{2}} = \frac{3}{4}$
2. Korrutades iga kord ¾-ga, peaks orbiit jõudma üheni hetkel, mil (¾)^o on n-i olematuseni kahanenud. Leides o väärtuse, saame ln 27 ÷ ln(4/3) = 11,46. Loeme selle kaheteistkümneks kolmekordistamiseks, mis teeb kahe poolitamisega igaühe kohta kokku umbes kolmkümmend viis sammu.
  
  $(\frac{3}{4})^{o} = \frac{1}{n} ⟹ o = \frac{ln 27}{ln ( 4/3 )} = \frac{3 . 2958}{0 . 28768} = 11.46$
3. Nüüd sisesta 27 tööriista. Kogu peatumisaeg näitab arvu 111 ja Poolitamisi kolmekordistamise kohta toob välja, millest see jaotus tuleneb: 41 kolmekordistamist ja 70 poolitamist. Ennustus eksib 3,58-kordselt. Seega pole 27 tüüpiline algväärtus.
  
  $o = 41, e = 70, t = o + e = 111, \frac{41}{11 . 46} = 3.58$
4. Kui võtame +1-d välja, muutub orbiit puhtaks korrutamiseks: 41 kolmekordistamist ja 70 poolitamist rakendatuna arvule 27. See korrutis on 0,8341 ja tööriist kuvab selle rea Orbiit ilma +1 liitmisteta all. See oleks täpselt 1, kui +1-d ei muudaks midagi, ent korrutis jääb ühest väiksemaks, kuna iga +1 annab poolitamistele veidi lisakoormust. Kahe astmete puhul, kus paarisarvulistest sammudest kõrvale ei kalduta, on see aga alati täpselt 1.
  
  $L = n \cdot \frac{3 ^{o}}{2 ^{e}} = 27 \cdot \frac{3 ^{41}}{2 ^{70}} = 0.8341 < 1, 2^{k} \cdot \frac{3 ^{0}}{2 ^{k}} = 1$
5. Kujundame valemi ümber. Tähistame korrutise L-iga. n·3^o ÷ 2^e = L, seega võttes logaritmid alusel 2, saame e = o·log₂3 + log₂(n/L) ning jagades o-ga, saamegi tööriistas kuvatava suhte. Arvu 27 puhul on see 1,58496 + 0,12236 = 1,70732, mille tööriist ümardab väärtuseni 1,7073. Üheni jõudva orbiidi puhul ei saa see suhe kunagi langeda alla log₂3 = 1,5850. Kõige lähemale jõuavad sellele need, mis kulutavad oma algväärtuse suuruse kohta kõige enam kolmekordistamisi. Alla 100 000 ei paku miski arvule 27 ses osas konkurentsi.
  
  $\frac{e}{o} = lo g_{2} 3 + \frac{lo g _{2} ( n / L )}{o} = 1.58496 + \frac{lo g _{2} ( 27/0 . 8341 )}{41} = 1.58496 + 0.12236 = 1.70732$
6. Just selline pikk orbiit ongi: seal tekib puudus poolitamistest. Siin on 27 ja need kolm algväärtust, mis troonivad skannimise kolme vahemiku tipus, lisaks on võrdluseks toodud naaberarv 26. Tüüpilisel algväärtusel on keskmiselt umbes kaks poolitamist iga kolmekordistamise kohta; iga siinne rekordiomanik jääb aga 1,70 ja 1,74 vahele. Orbiit kulutab ära kõik oma kolmekordistamised ega saa jagamisi tagasi.
  
  $n 2627871 6, 171 77, 031 t 10111178261350 o 2416596129 e 870113165221 e / o 4.0000 1.7073 1.7385 1.7188 1.7132$
7. Iga algväärtus kuni 2⁷¹ on kontrollitud. Neid on umbes 2,36 × 10²¹, mille arvutas David Bařina Euroopa superarvutitel ja avaldas 2025. aastal. Igaüks neist jõudis pärale. Kui pikk peaks aga olema teekond nii suurte arvude puhul? ln(2⁷¹) on 49,213, seega pakub heuristika sellise suurusega tüüpilise arvu jaoks 171 kolmekordistamist ja umbes 513 sammu.
  
  $n = 2^{71} \approx 2.36 \times 1 0^{21} : o \approx \frac{71 ln 2}{ln ( 4/3 )} = \frac{49 . 213}{0 . 28768} = 171, t \approx 3 o = 513$
8. Arvud, mis selle probleemi põnevaks muudavad, ei ole aga tüüpilised. Võrreldes iga skannitud vahemiku keskmise peatumisajaga, mis on 59,60, 84,98 ja 107,54 sammu, teeb rekordiomanik läbi vastavalt 2,99, 3,07 ja 3,25 korda pikema teekonna. Kui kanname neist viimase üle suurtele arvudele, vajavad 2⁷¹ lähedal asuvad aeglaseimad algväärtused pigem 1 700 kui 500 sammu. See suhe on aga endiselt kasvamas ka tööriista kõige suuremas skannitud vahemikus, seega on 1 700 pigem alampiir kui hinnang. Kõik selles arutluses toodud arvud on aga pelgalt heuristiline ekstrapolatsioon, sest keegi ei oska nii mastaapsete arvude kohta midagi kindlamat väita.
  
  $\frac{178}{59 . 60} = 2.99, \frac{261}{84 . 98} = 3.07, \frac{350}{107 . 54} = 3.25 ⟹ 3.25 \cdot 513 \approx 1, 700$
Vastus

41 kolmekordistamist kaheteistkümne asemel, sest 27 orbiit läbib 1,7073 poolitamist iga kolmekordistamise kohta, samas kui tüüpiline orbiit teeb neid umbes 2. Ainus ressurss arvu 27 allatoomiseks on lünk 1,7073 ja log₂3 = 1,5850 vahel ning see on väga kitsas, mistõttu võtab langus 111 sammu.

See kõik ei tõesta muidugi midagi. Väärtus ¾ tuleneb sellest, et käsitleme iga 3n + 1 sammu nii, justkui otsustaks juhuslik mündivise, mitu korda see kahega jagub. See münt on aga illusioon: iga orbiidi poolitamised on paigas juba n-i valimise hetkel. Sellest hoolimata on iga seni kontrollitud arv pärale jõudnud: kõik 2,36 × 10²¹ algväärtust. Terence Tao on jõudnud tõestusele kõige lähemale, näidates, et peaaegu iga algväärtus langeb lõpuks alla f(n), ükskõik kui aeglaselt see funktsioon f ka lõpmatuseni ei kasvaks. Peaaegu iga tähistab siinkohal logaritmilist tihedust 1. Ent peaaegu iga pole siiski iga ning just see vahe on koht, kus antud probleem endiselt püsib.

$\frac{e}{o} = lo g_{2} 3 + \frac{lo g _{2} ( n / L )}{o} o \to \infty lo g_{2} 3 = 1.5850$

Allikad (3)

The verification limit the page quotes, and where the 2.36 × 10²¹ comes from: David Bařina, "Improved verification limit for the convergence of the Collatz conjecture", The Journal of Supercomputing 81(1), 1–14, 2025. doi:10.1007/s11227-025-07337-0
The strongest partial result, which the answer quotes: Terence Tao, "Almost all orbits of the Collatz map attain almost bounded values", Forum of Mathematics, Pi 10, e12, 2022 (posted 2019). doi:10.1017/fmp.2022.8
Where the Erdős line comes from, and the standard survey of the problem: Jeffrey C. Lagarias, "The 3x + 1 problem and its generalizations", American Mathematical Monthly 92(1), 3–23, 1985.

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.