2^m - 3^n > 0
m ja n ovat positiivisia kokonaislukuja. Jos m > 65, millä m:n ja n:n arvoilla lausekkeen 2^m - 3^n positiivinen arvo on alle triljoonan (10^18).
Jos m>200, saako tuon lausekkeen positiiviseksi arvoksi edes millään alle triljoona triljoonaa trijoonaa?
(Ei ole helppo. Ehkä mahdoton ratkaista äärellisessä ajassa. Luvut kasvavat hetkessä aivan liian suuriksi Pythonillekin.)
m ja n ovat positiivisia kokonaislukuja. Jos m > 65, millä m:n ja n:n arvoilla lausekkeen 2^m - 3^n positiivinen arvo on alle triljoonan (10^18).
Jos m>200, saako tuon lausekkeen positiiviseksi arvoksi edes millään alle triljoona triljoonaa trijoonaa?
(Ei ole helppo. Ehkä mahdoton ratkaista äärellisessä ajassa. Luvut kasvavat hetkessä aivan liian suuriksi Pythonillekin.)
Vastaukset 23
Vanhimmat
Logaritmien suhteilla voi yrittää löytää jotain.
Ensin pitää löytää sellainen n:n arvo, jolla m = n*lg(3)/lg(2) on mahdollisimman vähän vajaa kokonaisluku. Esim. n:n arvolla 72057431991 m:n arvoksi tulee
114208327603.99999999999204946621398498729505 = 114208327604
Molemmissa lausekkeen tekijöissä on 34380132363 numeroa (10-järjestelmä).
lg(2^m) eroaa lg(3^n)sta vasta 12. desimaalissa. Tämä "pieni" ero on riittävä tekemään lausekkeen arvoksi paljon yli 100 numeroisen luvun. Katsokaa taskulaskimella ja kynällä ja paperilla suuruusluokka tarkemmin.
Missään vaiheessa ei kannata edes yrittää laskea lausekkeelle mitään tarkkaa kokonaislukuarvoa, ellei löydä jotain isoa n:n arvo, jolla n*lg(3)/lg(2):n desimaaliosan alussa on kymmeniä 9:jä. Mitä isommaksi n kasvaa, sitä enemmän 9:jä tarvitaan. Samalla tarvitaan lisää tarkkuutta liukulukulaskuihin. Hidasta. Isoja n:n arvoja on äärettömästi. Aikaa ja sähköä vain rajallinen määrä.
jep, tämä on ehdottomasti oikea lähestymistapa. Rust:lla ja 38 desimaalin tarkkuudella tuohon n=72057431991 arvoon asti pääsee alle 5 minuutissa.
Hyvin hitaasti kyllä nuo ysit lisääntyy joten ei taida ratketa tälläkään tavalla:
...
n=000171928773 xxx.99999999741870669289526386837853126375
n=000397573379 xxx.99999999984730012412922500905572056625
n=006586818670 xxx.99999999998539541730156128556871836250
n=072057431991 xxx.99999999999204946618794913220018142125
n=137528045312 xxx.99999999999870351507433697883164448000
n=890638885193 xxx.99999999999887513933240971962132993875
Tässä vielä Rust-ohjelma jota käytin:
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=d0b404f7fc6736844ae82f8eb43e4608
Jos oikein ymmärsin, niin korvaat hitaat tarkan liukuluvun ja peräkkäisten isojen konaislukujen kertolaskut nopealla kokonaislukujen (desimaaliosa) jatkuvalla summaamisella.
Virhe tietysti kasvaa koko ajan, mutta jos desimaaliosa on kokonaislukuna riittävän tarkka, se ei ehdi haitata mitään. Jos lähtee liikkeelle jostain muusta kuin 1:stä, pitää tietysti laskea vaikka tarkalla taskulaskimella sille tarkka lähtöarvo.
Pitää joskus tutkia Pythonilla, montako kertaa nopeammaksi ohjelman saa. Ei tarvitsisi käyttää hitaita gmpy2:n liukuluja. Gmpy2:n kanssa ei voi käyttää Pypyä, joten pelkästään Pypyllä nopeus lisääntyy moninkertaiseksi.
Jotta laskennan saisi todella nopeaksi, pitäsi keksiä (muodostaa) joku jaksollisuus.
n*lg(3)/lg(2) on sama kuin lg(3)/lg(2) lg(3)/lg(2) lg(3)/lg(2) ... joten otin vakioksi tuon lg(3)/lg(2) (ilman kokonaislukuosaa) ja sitten vaan summaan sitä, jättäen aina kokonaislukuosan pois.
Kun kokonaislukuosa pysyy pienenä (se on tässä aina joko 0 tai 1) niin lähes koko 128 bitin tarkkuus voidaan käyttää desimaaliosalle.
Tuon alkuarvon lg(3)/lg(2)-1 = 0,5849... laskin https://www.wolframalpha.com/ sivustolla että on varmasti tarkka arvo.
Viimeisessä arvossa tuossa tarkka luku olisi xxx.999999999998875139332409728...
eli ohjelman antamassa arvossa xxx.999999999998875139332409719... on vielä paljon oikeita desimaaleja ysien jälkeen.
Sama virhe tulee tietysti myös kertolaskua käytettäessä. Eihän se eroa mitenkään jatkuvasta summaamisesta.
Kokeilin Pypyllä. Sain lasketua alle tunnissa 100 miljardia lukua. Helppo kopsata viimeinen arvo putkelta, ja laittaa se uudeksi alkuarvoksi. Tarkalleen samat luvut tulivat kuin kertolaskutavalla. Ei nopeutunut tosin kovinkaan paljoa.Käytin hiukan vajaita vajaita 128 bitin lukuja (125 ja 126 bittiä), jottei Python tai Pypy vahingossakaan tulkitsisi lukuja yli 128 bittisiksi. Ei voi aina oikein tietää onko luvuissa etumerkkibitti mukana vai ei.
Kertolaskussa vaan erona on että siinä kokonaislukuosa kasvaa paljon suuremmaksi (koska sitä ei voi "nollata" kesken laskun kuten summaamisessa voi) ja siten desimaaliosalle on käytössä vähemmän bittejä kun minulla tuossa oli tasan 128 bittiä käytössä yhteensä.
Rust:ssa on muuten hyvin nopea 128-bittinen kokonaislukutyyppi (ei ole BigInt), noin tunnissa pääsin 1000 miljardiin.
Pythonilla 128 bittiä ei ole mikään raja kokonaisluvuille eikä liukuluvuille. Ja esim. gmpy2:lla voi valita mielivaltaisen tarkkuuden.
Tottakai summaustapasi on parempi ja älykkäämpi myös Pythonilla. Rustin kiinteät 128 bitin muuttujat ovat paljon Pythonin lukuja nopeampia, kun ei koko ajan tarvitse tarkkailla luvun tyyppiä ja suuruutta ja vaihtaa niitä tarvittaesa lennosta.
Ei sinulla ole ihan kaikki 128 bittiä desimaaliosan käytössä. Pari kolme ylimmäistä bittiä on ylivuotoluetta. Katsoppa hiukan tarkemmin koodiasi. Ei 10- ja 2-järjestelmän luvut mene tasan. ONE vakiosi on "vain" 10**38 ja LOG:ssa on "vain" 38 numeroa.
Kokeilin 99 ja 999 alun muodostumista 4- ja 6 numeroisilla desimaaliluvuilla. Ylivuodoissa vähensin aina 10^4 tai 10^6. Ei tule aina kaikilla summattavilla luvuilla 100 tai 1000 pituisissa silmukoissa. Tulee kyllä aina, jos jatkaa summaamista pitempään. Tulos on tietysti silloin jo täysin väärin.
> Ei sinulla ole ihan kaikki 128 bittiä desimaaliosan käytössä.
En väittänytkään noin, vaan että lähes 128 bittiä. Ja totta että yksinkertaistin hiukan kun en lähtenyt selittämään 10-järjestelmän ja 2-järjestelmän eroja kun en ollut varma minkä tasoista tietämystä tässä keskustelussa on.
Osaan kyllä tehdä tuon niin että ihan kaikki 128 bittiä ovat desimaaliosaa.
Kokeilin huvikseen tehdä Rust:lla ohjelman joka laskee 3^n tarkat arvot ja niiden likimääräisen erotuksen seuraavasta 2^m:sta.
Aika hitaasti laskee, muutamassa minuutissa pääsee lukuun 3^3000000 asti, eli tällä tavalla tätä ei ainakaan ratkaista.
Ehkä helpoin tapa löytää jotain on keksiä vastaesimerkki Collatzin konjektuuriin eli saada aikaan iso silmukka.
Jos parittomille luvuille seurava termi on (3x 1)/2 ja parillisille luvuille x/2, niin silmukan syntymiskaava on parittomille luvuille muotoa:
x = (3*(...(3*(3*(3*x 1)/2 1)/2 1)/2 ...)/2
Parilliset luvut lisäävät aina yhden 2:n lisää nimittäjään.
Saadaan
(2^m-3^n)x = 3^(n-1) (miljardeja 2:n ja 3:n potenssien tuloja)
Kaavassa n on silmukassa olevien parittomien ja m-n parillisen lukujen määrä. Jotta x saataisiin tarvittavan suureksi, niin 2^m-3^n on oltava "pieni". Koska x on kokonaisluku, niin oikean puolen on oltava jaollinen 2^m-3^n:llä.
Helpottaako yhtään? Jostain syystä miljoonat matemaatikot ovat jättäneen kaikki asiaan liittyvät tutkielmansa julkaisematta.
Konvergenteillähän löytää hyviä rationaali-approksimaatioita. Sage-koodi:
F = RealField(400)
a = F(ln(3)/ln(2))
#print (a)
c = continued_fraction(a)
for k in range(30):
t = c.convergent(k)
print (t)
#print (t-a)
Jos haluaa varmasti parhaan mahdollisen rationaalisen approksimaation siihen mennessä (eli rationaaliluvuista, joilla korkeintaan kyseisen suuruinen nimittäjä), niin pitää tarkastaa myös semikonvergentit. Tämän mukaisesti: https://en.wikipedia.org/wiki/Continued_fraction#Semiconvergents
Onko tuo löytämäsi 114208327604 / 72057431991 tarkastetusti paras tuon kokoisiin nimittäjiin asti?
Tuo koodi antaa siis ln(3)/ln(2):n konvergentit:
1
2
3/2
8/5
19/12
65/41
84/53
485/306
1054/665
24727/15601
50508/31867
125743/79335
176251/111202
301994/190537
16785921/10590737
17087915/10781274
85137581/53715833
272500658/171928773
357638239/225644606
630138897/397573379
9809721694/6189245291
10439860591/6586818670
103768467013/65470613321
217976794617/137528045312
1193652440098/753110839881
8573543875303/5409303924479
9767196315401/6162414764360
18340740190704/11571718688839
83130157078217/52449289519716
683381996816440/431166034846567
Ei liene mikään paras, vaan siinä on ysejä eniten siihesti lasketuista luvuista.
Listassasi on hiukan pienempi 65470613321, joka tuottaa paljon nollia ja 2^m - 3^n tulee negatiiviseksi. Jostain syystä halusin lausekkeen pysyvän positiviisena. Matemaattisesti itseisarvo on tietysti parempi kriteeri.
Listasi ln(3)/ln(2):n konvergentit ovat juuri niitä mitä hainkin. Ei tarvitsekaan käydä tyhmästi läpi biljoonittain lukuja.
Pitää yrittää muokata Saga-koodisi Pytoniksi ja katsoa kuinka pitkälle pääsee. Lähes varmasti lauseketta 2^m - 3^n ei saa pienentymään lukujen kasvaessa. Jossakin äärettömän kaukana voi olla poikkeuksia, mutta niitä lienee mahdoton löytää.
Pieni+Python+3+ohjelma.+Ovatko+99.+ja+100.+luvut+oikeita?++Tulostin+vain+sen+jälkimmäisen+luvun.+En+kyllä+ihan+ymmärrä,+miten+noin+pieni+ohjelma+voi+toimia+oikein?
Samat tulee Sagella (paitsi indeksointi yhdellä jäljessä)! Suorituskyvystä en ole varma. Melko yksinkertainen algoritmihän ketjumurtoluvun laskeminen on, joten vaikeudet tullee suuren tarkkuuden käytöstä. En tiedä miten paljon "overheadiä" tuolla RealField()in käytöllä sitten on.
Itse asiassa en ollut varma toimiiko continued_fraction()-funktio ihan suoraan myös suuren tarkkuuden luvuilla mutta näyttää toimivan sillä saatiin sama vastaus.
Joo, ei sitä |2^m - 3^n|:ää saa pienentymään, jos tuohon mathoverflow:ssa olleeseen vastaukseen on uskomista. Siellähän oli että se on suurempaa kuin max(2^m, 3^n) jaettuna (e * max(n, m))^C jollekin vakiolle C. (Kommenteissa laskettu C=821013300.694... mutta että paljon pienemmänkin pitäisi jo toimia.)
Ohjelma+jätti+tulostamatta+viimeksi+lasketut+arvot.+Silmukka+pitää+alkaa+1:stä+
Jos lausekkeessa n on 99. luku, saadaan m:n desimaaliarvoon 48 peräkäkkäistä 9:iä. Pitäisi tietysti olla todella paljon enemmän, jotta lausekkeen arvo pienenisi järkeväksi.
Vasta 205. luku tuottaa 100 peräkkäistä 9:iä. Tarkistakaa:
205: 911103872450681792581904018794276516086007868645731660155183922765510884785143299405304437390578757
Jos+haluaa+laskea++yli+100000++arvoa,+ei+aikaisempia+arvoja+ole+mitään+tarvetta+tai+järkeä+säilyttää+q-listassa.+Tarvitaan+vain+kaksi+viimeistä+arvoa+ja+ne+kannattaa+pitää+muuttujissa+q0+ja+q1.+Lukujen+määrän+ja+koon+kasvaessa,+muistin+tarve+kasvaa+räjähdysmäisesti.+Ei+tietysti+haittaa+juuri+mitään+pienissä++alle+100000+luvun+laskuissa.+
Oletetaan :
2^m - 3^n = d
Arvioidaan hiukan d:n arvoa. Jollakin pienen pienellä positiivisella x:n desimaaliarvolla:
2^(m-x) - 3^n = 0 => 3^n = 2^(m-x)
2^m - 2^(m-x) = d
2^m(1 - 2^(-x) = d
Otetaan molemmilta puolilta 10-logaritmi:
m lg(2) lg(1 - 2^(-x)) = lg(d)
Lukuun x voidaan helposti saada miljoonia etunollia ja lausekkeen lg(1 - 2^(-x)) arvoksi itseisarvoltaan iso negatiivinen luku. Jos luvussa on miljoona etunollaa, lauseke ei kasva paljoakaan yli miljoonaksi. (Tarkistakaa jollakin vanhalla likiarvokaavalla!) Siinä vaihessa m:n arvo on kasvanut monimiljoonaiseksi luvuksi ja myös d:n arvo valtavaksi.
Vaikka laskuja tekisi triljoonan bitin tarkkuudella, ei d:n arvoa saa mitenkään pienenemään.
Kaavasta
m lg(2) lg(1 - 2^(-x)) = lg(d)
näkee suoraan, että jos m on miljoona ja d menisi sattumalta pieneksi, niin sen laskemiseksi tarvittaisiin n. 300000 desimaalin tarkkuutta. Vastaa yli miljoonan bitin tarkkuutta. (Onnistuisi tietysti vielä kokonaislukuina helpommin.)
Ja 2 ja 3 korvataan alkuperäisessä lausekkeessa joillakin hiukan isommilla luvuilla x ja y), joilla ei ole yhtään yhteistä tekijää (esim. 3 ja 4 tai 4 ja 5 tai 5 ja 6), tilanne vain pahentuu.
Ihan tilastollisestikin voi päätellä, ettei kokonaislukulausekkeen x^m - y^n arvoa saa millään pieneksi isoilla n:n arvoilla. Todennäköisyys on luokkaa n/y^n. Eli mitättömän pieni. Ei tietysti todista mitään!
Täällä: https://mathoverflow.net/questions/116840/distance-between-powers-of-2-and-powers-of-3 on asiaa kanssa pohdittu. Ensimmäisen vastauksen mukaan ero kasvaa eksponentiaalista vauhtia.
Joissakin vastausten linkeissä tulee vastaan myös Collatz conjecture. Eli asiaa on pohdittu paljon. Matemaatikoilla riittää töitä ikuisesti.
Ymmärtääkö joku Li Jiang:n Collatzin konjektuurin todistuksen eli kaikki luvut päätyvät ykköseen.
https://www.researchgate.net/publication/343287191_The_Collatz_Conjecture_and_Linear_Indefinite_Equation
Ei näyttäisi ihan aukottomalta. Jos ihan suhteellisen yksinkertaiseen peruskaavaan pohjautuvaa todistusta ei kukaan matemaatikko ymmärrä, niin jossakin on jotain vikaa. Luulisi Li Jiangilla olleen riittävästi aikaa kirjoittaa todistus selkeämpään muotoon. On saanut varmasti kyselyjä ja kommentteja.