Názory k článku Výpočetní ověření Collatzovy domněnky až do velikosti 2⁶⁸

To je zvláštní, že to ještě nikdo matematicky nedokázal. Chvilku mi tedy trvalo než jsem pochopil problém.
Ale když se nad tím zamyslím, tak každé druhé číslo je sudé, tedy počet dělení číslem 2 musí být minimálně každý druhý výpočet.
Dobře, vzoreček se pro lichá čísla upravil na (3n+1)/2 protože zákonitě musí být 3n+1 sudé, pokud je n liché, takže jako další krok by bylo dělení číslem 2.
V každém případě, pokud (3n+1)/2 povede k sudému číslu, tak jsme zákonitě na sestupné trajektorii k číslu 1. A to se dřív nebo později stane.

To je něco jako Velké Fermátova věta.
Zadání celkem triviální ale důkaz dlouho odolával.
Jen tak mě napadá ... při rozvoji této řady musíte narazit na číslo, které je minimálně druhá mocnina čísla 2. Pak to začne konvergovat k číslu 1.
Ale zkuste dokázat, že se tak stane vždy.

napsal jsem to špatně
... musíte narazit na číslo, které je nějakým násobkem minimálně druhé mocniny čísla 2.

Lagarias and Weiss už v roce 1992 ukázali, že maximální hodnota, které může počáteční hodnota n dosáhnout je zhruba n^2. Výpočetní verifikace tohle potvrzuje. Podívejte se třeba na tu tabulku Path records a vezměme například počáteční hodnotu 1410123943, která dosáhne nejvyššího bodu ve své trajektorii 3562942561397­226080, což je přibližně její druhá mocnina.

Pokud je to konečné možné maximum dokázané, máme neomezený počet kroků a řada se pro žádné n nemůže zacyklit v kruhu, tak z toho vyplývá, že se k té jedničce dostanu vždy.

Oni ukázali náhodným procesem, že to maximum bude zhruba n^2, ale nikdo vám nezaručí, že neporoste ještě dále nebo že místo, aby dostoupalo na n^2 neskončí v netriviálním cyklu.

Ten problém bude v tom pro žádné n se nemůže zacyklit v kruhu.

Nemá to být 2^n?
Protože pro číslo 27 toto zrovna neplatí. Tam je vrchol 4616 a 27^2 = 729

Ne, správně je n^2. Podívejte se do tabulky zde na číslo 27. Trajektorie vystoupala o něco výše než n^2, ale u ostatních rekordů je naopak o něco níže. Tedy zhruba n^2.

Ano. Máte pravdu. Haluz. No to je matematika. Proto to chce důkaz :-)

A já si tipnu, že pokud existují čísla, co nedoiterujou do jedničky, tak jich bude nekonečno a nejmenší z nich bude liché ;-).

Tak ta cast s tim lichym ale neni tipnuti si, to lze naprosto trivialne dokazat.

Jo přesně tak a podobně se dá i to nekonečno. Geometrická řada krát 2 z té nejmenší hodnoty. BTW myslím, že i řada

2^i\frac{3x+1}{2}

a

2^i\frac{9x+5}{4}

Tady je vysvetleni toho problemu pro lidi:
The Simplest Math Problem No One Can Solve - Collatz Conjecture
https://www.youtube.com/watch?v=094y1Z2wpJg

Kdysi jsem na tento problém narazil a trochu se mu věnoval. Postupné zkoušení čísel je výpočetně náročné a už to zkusili jiní. Tak jsem na to šel jinak. Velmi zjednodušeně: předpokládám, že existuje číslo, pro které doměnka neplatí, tedy existuje smyčka. To je vlastně nějaký počet násobení třemi (a přičtení jedničky) a dělení dvěma v nějakém pořadí. A měl bych se vrátit k původnímu číslu. Takže hledám, kdy se se k sobě přiblíží nějaká mocnina 3 a mocnina 2. Hranice jsou dané případem, kdy nejprve násobím a pak dělím a případem opačným. Výraznější přiblížení nastane až u 2^301994 a 3^190537, shoduje se 7 desítkových číslic. To ale nestačí, výchozí číslo by v tom případě muselo být příliš malé a ta už byla vyzkoušena. Další je až někde u 2^85137581 a 3^53715833. Tak příliš malá shoda. No prostě závěrem: Pokud smyčka existuje, tak její délka bude minimálně deset milionů kroků. (Což ovšem neznamená, že nemůže začínat už v relativně malých číslech)

Beznaděj. Tímto způsobem cesta zcela jistě nevede.

Já měl třeba toto na jednom interview, a ani nevim co se tím vlastně snažili dokázat. To že se dá použít count trailing zeros na to jsem přišel hned, ale problém jako takový jsem znal a věděl jsem, že na interview asi breakthrough opravdu neudělám a nějak opatrně jsem se jim to snažil říct :)

Článek jsem víceméně nečetl, protože nechci přemýšlet nad matematickými nuancemi.
Nicméně myslím si, že jediný exaktní důkaz by mohl provést kvantový počítač, pokud by se algoritmus testu podařilo převést na kvantově zpracovatelnou úlohu.

To právě asi ne. Kvantový počítač by mohl pomoci ověřit vyšší čísla, takže by mohl nalézt číslo, pro které neplatí. Ale dokázat platnost takto nelze. Na to bude asi potřeba matematický důkaz na úrovni kterou matematika zatím nedosáhla.

A proč by kvantový počítač nemohl pracovat s nekonečnem. Není snad ve vlnové reprezentaci nekonečný spojitý počet možností?

Jen netuším, proč se na tom pálila el. energie. Ověřili jsme další čísla ale to nikdy nevede k důkazu. Jen jsme se i u dalších čísel utvrdili, že hypotéza platí.

Důkaz vs hypotéza. Důkaz dokládá, že daná věc platí pro všechny možnosti.

Za svych studii jsem s panem autorem souperil o verejne zdroje Metacentra, kde je viditelne, kolik toho bylo napocitano. Pokud me pamet nelze, odhadoval jsem to tehdy na nizsi jednotky milionu za elektrinu pro vypocet popsany v clanku.

Smysl to asi má, protože můžou najít číslo, pro které to neplatí a tím by dokázali, že hypotéza neplatí. Navíc se tím určitě získalo spousta dat (jak dlouho dané číslo konverguje, jaké nejvyšší hodnoty dosáhne posloupnost daného čísla, ...) a ty mohou teoreticky přispět k nalezení důkazu..

Ano pokud najdu číslo pro které to neplatí, tak vyvrátím hypotézu a nemusím hledat důkaz.
Nedomnívám se, že spousty dat dokážu teoreticky přispět k důkazu.
Důkaz musí platit pro jakékoliv číslo...

A konkrétně k Collatzově doměnce, její potencionální užití mimo teoretické hraní? To pak můžu stále zkoušet na kovadlině tlouci do olova jestli náhodou nevyrobím atom zlata :-)

V praktickém světě, by se daná hypotéza považovala za fakt na základě empirického ověření, dokud by někdo neprokázal opak. Pak by se sice vše založené na tomto problému zhroutilo, ale stále otázka je to k něčemu? Už to řešíme od roku 1937 a stále jsme u hrubé síly.

Jestli se nemylim tak timto problemem se zabyvali poctari na svych pocitacich projektech BOINC: 3x+1@home a Collatz Conjecture.

Nedavno se podarilo jednomu z nejlepsich soucasnych matematiku (Terrence Tao) dokazat, ze "temer vsechna" N doiteruji "temer k 1".

Jedno je jiste, dukaz bude mnohem slozitejsi a vyuzivat novou matematiku. Bude to asi podobne jako s Fermatovou vetou, kde dukaz vyzadoval postupy z 2. poloviny 20 stoleti (elipticke rovnice, L-funkce, modularni formy). A vlastne slo o dukaz Tanijama-Simurovy domnenky z 50. let, ktera implikovala Fermatovu vetu.

Vice zde:

https://www.quantamagazine.org/mathematician-proves-huge-result-on-dangerous-problem-20191211/

https://arxiv.org/abs/1909.03562 (pro matematiky)