Katsokaa Numberphile:n video John Conwayn "Climb to a Prime" väittämästä ja sen todistamisesta vääräksi (James Davis).
https://www.youtube.com/watch?v=3IMAUm2WY70
Arvioikaa kuinka monta vastaava lukua löytyy ja löytyykö lukua 13532385396179 pienempää vastaavaa lukua? Eiköhän tälläkin hetkellä kymmenet kotikoneet raksuta ongelman parissa toinen toistaan älykkäämmillä ohjelmilla. Ei noita pienempiä sopivia kandidaatteja ole kovin monta miljardia.
(Eli jos luku jaetaan alkutekijöihinsä pienimmästä suurimpaam ja poistetaan kerto- ja potenssimerkit, saadaan tämä sama luku.)
Tuloksia tulee ajallaan matematiikan tietokantaan: https://oeis.org/A195264
Väittämä (5) on tuossa: https://oeis.org/A248380/a248380.pdf
https://www.youtube.com/watch?v=3IMAUm2WY70
Arvioikaa kuinka monta vastaava lukua löytyy ja löytyykö lukua 13532385396179 pienempää vastaavaa lukua? Eiköhän tälläkin hetkellä kymmenet kotikoneet raksuta ongelman parissa toinen toistaan älykkäämmillä ohjelmilla. Ei noita pienempiä sopivia kandidaatteja ole kovin monta miljardia.
(Eli jos luku jaetaan alkutekijöihinsä pienimmästä suurimpaam ja poistetaan kerto- ja potenssimerkit, saadaan tämä sama luku.)
Tuloksia tulee ajallaan matematiikan tietokantaan: https://oeis.org/A195264
Väittämä (5) on tuossa: https://oeis.org/A248380/a248380.pdf
Vastaukset 32
Vanhimmat
Suoraan videon lopussa olevista viesteistä:
Etsitty luku n voidaan jakaa kahteen osaan:
n = x * p = f(x) * 10**y p
p on suurin alkuluku ja oletetaan sen olevan potenssiton. (Jos sen potenssi on 2, pitää muodostaa erilaiset kaavat.)
Funktio f(x) (ohjelmapätkä) purkaa x:n alkutekijöihin ja muodostaa niistä vaaditulla tavalla "numeromerkkijonon".
y = p:n numeroiden määrä.
x - 1 = (f(x) * 10**y)/ p
p = (f(x) * 10**y) / (x - 1)
Merkitään m = f(x)/p
=> x = m * 10**y 1
Nyt tarvitsee vain kasvattaa lukua m ja kokeilla, toteutuvatko ylläolevat kaavat ja p on alkuluku ja f(n) = n. Helppoa ja nopeaa.
Muutamassa sekunnissa löytyy y:n arvolla 5 sopiva m = 1407. Siitä saadaan x = 140700001 ja p = 96179.
Ymmärtääkseni y:n arvoja 2, 3 ja 4 on toistaiseksi testattu vain tiettyyn m:n rajaan asti. Joten löydettyä lukua pienempi luku voidaan ehkä löytää tai sitten joku ilmoittaa, ettei löydy.
Alla lnkki Paul -nimerkin kirjoittaman selkeään Python ohjelmaan (kolmas viesti).
https://programmingpraxis.com/2017/06/13/climb-to-a-prime/#comments
Ei löydy pienempää lukua, jos viimeinen (suurin) alkuluku (k) on toisessa potenssissa. Testaamiseen ei mennyt Python-ohjelmalla kuin muutama tunti (2...3 ytimellä). Helppo ja nopea testata. Pitää vain testata kahdella alkavia ja loppuvia lukuja 2...k2. Pisteiden paikalle laskuri 0...9, 0...99, jne. Luvun on oltava jaollinen k^2:lla. Ehdokkaat karsiutuvat tehokkaasti.
James Davisin luku saattaa jäädä ainoaksi laatuaan. Kaikki 64 bittiset luvut (n. 10^19) on jo varmasti testattu monin eri tavoin. Todennäköisyys löytymiselle pienenee rajusti lukujen kasvaessa.
"Kaikki+64+bittiset+luvut+(n.+10^19)+on+jo+varmasti+testattu+monin+eri+tavoin."
Kannattaisiko ongelmaa lähestyä toista kautta eli ensin generoida jollakin tavalla valikoiduista (valmiiksi lasketuista ja taulukoista) alkuluvuista luvun alkuosa ja laskea sitten ihan vaan jakolaskulla halutun pituinen loppuosa?
Jos alkuun valitaan esim. 13*53**2*3853 = 140700001
Sitten 13532385350000/140700001=96179. Hiukan pyöristäen. Toimii tarkasti isoilla luvuilla. Riittää tarkistaa onko 96179 alkuluku ja kokeilla onnistuiko valinta.
Onko nopeampi ja tehokkaampi todella isoilla luvuilla? Jos kaikkia lukuja ei voi ikinä kokeilla, lienee parasta vaan kokeilla mahdollismman paljon.
Toki voi löytyä luvuista monenlaisia kuvioita. Esim. jotkut neliöt ovat neliöiden summia, 9 16 =25. Tai toinen esimerkki, joidenkin neliöiden lopussa esiintyy 61. Eli sadalla jakamisen jakojäännös olisi 61.
19 ^2 =361
31 ^2 =961.
Mutta mielestäni näistä ei voi tehdä mitään yleispätevää sääntöä, vaan menee taiteen puolelle.
Fermatin menetelmä jakaa tekijöihin lukuja:
https://en.wikipedia.org/wiki/Fermat's_factorization_method
http://yippy.com/search/?v:project=clusty-new&query=fermat factorization&xtoken=13662076055948fe6b3e9a1
Tuli linkkeihin jotain hässäkkää. Yippy-hakukoneella on näköjään aikaraja.
Opentext.com -hakukoneella onnistui löytää ymmärrettävää selitystä englanniksi.
Hakusanoilla pdf fermat factorization.
Fermatin menetelmä etsiä tekijöitä luvuille. Perustuu algebran kaavaan a^2 -b^2 =(a b) (a-b).
https://www.math.ksu.edu/math511/archive/notes/925.html
Ensin tutkittavasta luvusta t otettaisiin neliöjuuri. Pyöristettäisiin ylös kokonaisluvuksi, esimerkissä käytetty kirjainta n. Sitten kokeiltaisiin, antaako n^2 -t tulokseksi täsmälleen tasan jonkin neliöjuuren. Jos ei anna, kasvatetaan n suuremmaksi ja kokeillaan uudelleen. Esimerkkilinkissä on taulukoitu
Tutkittavana 426749
neliöjuuri(426749) = 653.26...
Aloitetaan arvosta n = 654, ja kullekin n arvolle lasketaan n^2 - 426749
n .. ......... (n2 - 426749)
654 .....967
655 .....2276
656 .....3587
657 .....4900
Löytyi neliö, joten tästä voidaan kaavalla laskea tekijöitä 426749 = (657 70)(657 - 70).
En ole tätä vielä ajatellut ja perehtynyt, että milloin tekijöitä kannattaa hakea pienien lukujen kautta, milloin neliöjuuren läheltä Fermatin menetelmällä. Vai molemmatko tavat yhtä hitaita.
Ja tässä vielä linkkiä Opentext-hakukoneeseen: http://fqs.opentext.com/web.htm
No koeta nyt perehtyä. Ihmiskunta odottaa malttamattomana tämän ongelman ratkaisua.Alienit ovat asettaneet ihmiskunnan säilymisen ehdoksi että löytyy tälle ongelmalle ratkaisija.
Mutta muista, että kun nokka irtoaa niin pyrstö tarttuu.
Tietokoneen suorituskyvyn kannalta ei ole yhdentekevää, haetaanko luvulle tekijöitä tällä tai tuolla algoritmilla. Sikäli kuin niitä kovin monenlaisia onkaan. Kryptografian puolella tämä on juuri pullonkaulana, että miten nopeasti kryptaus voidaan murtaa esim. tekijöihin jakamisen kautta.
Luulisin, että perinteinen pienistä luvuista lähtien tekijöiden etsintä jakolaskulla on nopeampaa, kuin lähteä neliöjuurilla ja neliöillä haeskelemaan, Fermatin tavalla.
Ei huutiukon vittuiluista kannata välittää, jos se vain oomannin vittuileva sivupersoona, joka vetää yötäpäivää hernekeittoa molempiin sieraimiinsa. Ja aivastelee pärskii sillinkatkua ympäriinsä sitten.
Jos joku haluaa kotikoneellaan löytää löydetyä lukua pienemmän Conwayn Climb to a Prime -väittämän vääräksi todistaman luvun, niin kannattanee keskittyä löytämään kahden tai kolmen luvun muodostama päättymätön ketju.
Pitää vain aloittaa jostakin satunnaisesti valitusta noin dekadin tai parin (löydettyä lukua) pienemmästä luvusta ja käydä läpi esim. miljoona seuraava lukua. Tutkittavat luvut eivät kasva kovin suuriksi kolmen peräkkäisen muunnoksen aikana ja homma sujuu todella nopeasti. Tunnissa saa testattua usean miljoonn luvun alueen. Vaihtoehto lottoamiselle!
Alla lista 10000:sta alkulukuun päättyvistä ja toistaiseksi ratkeamattomista luvuista.
http://chesswanks.com/seq/a195264/
Klikatkaa esim. lukujen 20 tai 105 Unknown -linkkiä. Saatte hyvän käsityksen ongelmasta. Lukujen viimeinen tekijä kasvaa niin suureksi, että sen murskaaminen kestää viikkoja tai kuukausia. Listaa päivitetään jatkuvasti.
"Tiedemaailma" keskittyi nähtävästi lähes pelkästään noiden alkupään (alle miljardi) numeroiden selvittelyyn ja ja on uhrannut niihin tuhansia vuosia cpu-aikaa. James Davis selvitti lukunsa alle 3 sekunnin cpu-ajalla alle 20 rivisellä Python ohjelmalla.
Alla oleva Python 3 ohjelmapätkä yrittää löytää lukuja, jotka päättyisivät kahden tai kolmen luvun päättymättömään silmukkaan. Ohjelma testaa 10 miljoonaa (saa muutella vapaasti) parittottomasta luvusta alkavaa ketjua. Tulostetaan jotain mielenkiinnon vuoksi 10000 luvun välein. Paljon alle promille luvuista muuntuu parillisiksi (viimeinen tekijä parillisessa potenssissa), joten niihin ei vielä kannata uhrata aikaa kotikoneilla. Kannattanee keskittyä 12...14 numeroisiin lukuihin.
Toimiiko vastaava Julia-ohjelma nopeammin? Löytyykö nopeampia factorint tai isprime (is_prime) kirjastofunktioita tai voiko f(x) toteuttaa nopeammaksi? Muuttakaa ja mitatkaa 2...10 tulostukseen kuluva aika.
from sympy.ntheory import factorint
from sympy.ntheory.primetest import isprime
def f(x):
fac = factorint(x)
s = ''
for p in sorted(fac.keys()):
s = str(p) (str(fac[p]) if fac[p] > 1 else '')
return int(s)
x = 1156830000000 - 1 # Valitkaa joku muu alku (5...7 numeroa.)
for cc in range(0, 1000):
for m in range(0, 10000):
x = x 2
if isprime(x): continue
a = f(x)
if isprime(a): continue
b = f(a)
if isprime(b): continue
z = f(b)
if z==x or z==a or z==b: print("******* Found ******* ",x,a,b,z)
print(cc, x, a, b, z)
Testattavaa ketjua voi pidentää lisäämällä siihen c=f(b), d=f(c), ... ja lisäämällä vastaavat or-ehdot ja pidentämällä tulostuksia. Luvut kasvavat kuitenkin mielettömän suuriksi ja ohjelma hidastuu. (f-kirjainta ei voi käyttää, ellei muuta f(x):n nimeä. )
Frimefac+kirjasto-ohjelmat+toimivat+Python+2:ssa+(2.7)+ainakin++40+%+nopeammin+kuin+vastaavat+sympy.ntheory+kirjasto-ohjelmat+Python+3:ssa+(3.5).+(Frimefac-kirjastoa+ei+ole+vielä+käännetty+Python+3:lle+sopivaksi.)+Alla+yhdellä+pidennetty+silmukka.+Jos+sisennykset+eivät+säily,+niin+vika+on++Suomi24:n+editorissa.
Kukaan ei nähtävästi ole löytänyt 13532385396179:n kaltaista toista lukua.
Ei pitäisi olla mahdotonta. Pystyykö joku arvioimaan todennäköisyyttä tälläisen toisen luvun löytymiselle?
Kaava on yksinkertainen:
n = x * p = f(x) * 10^y p
x = (f(x)/p)* 10^y 1
m = f(x)/p
x = m* 10^y 1
f(x)/m on oltava kokonaisluku ja oikean kokoinen alkuluku (p)
Alkulukujen pituuksia (y) on ääretön määrä ja niille kaikille on lähes ääretön määrä vaihtoehtoja. Vaikka p olisi yli 100 tai 1000 numeroinen, niin ei mitenkään estää ehdot täyttävän x:n löytymistä ihan "pienilläkin" (<10^20) m:n arvoilla.
Tehtävä on tietysti matemaattisesti typerä, joten kukaan ei saa käyttöönsä mitään tehokasta supertietokonetta jauhamaan sitä kuukausien ajan. Triljoonien isojen lukujen jako tekijöihin on vieläkin aivan liian työlästä.
Todennäköisyyttä ei voi oikein arvioida, ellei pysty testaamaan valtavaa määrää tapauksia. Lukujen kasvaessa kaikki muuttuu vaikeammaksi ja harvinaisemmaksi, joten käytännössä ei saa mitään tilastoa aikaan. Conway varmasti ymmärsi kaiken.
f(x) pitäisi olla pienempi kuin x. Harvinaista isoilla luvuilla. Paljon alle prosentti.
f(x):n pitäisi olla jaollinen m:llä. Äärimmäisen harvinaista. Ja jos m on parillinen, tämä on vielä todella paljon harvinaisempaa. Ja jos m on jaollinen 5:llä, käytännössä täysin mahdotonta. (f(x):n suurimman tekijän potenssi pitäisi olla 5.)
Jos f(x) olisi jaollinen m:llä, niin jakotulos olisi erittäinn harvoin oikean kokoinen alkuluku. Alkuluvut harvenevat koon kasvaessa.
Kokeilkaa vaikka y:n arvolla 5. Helposti löytyy m:n arvo 21391, jolla f(x) on jaollinen. Tällä arvolla f(x) on kuitenkin aivan liian suuri. Sitten ei mitään vaikka testaisi 100 miljoonaa m:n arvoa. Sama juttu muilla y:n arvoilla paljon vaikeampana. Testasin 5 vuotta sitten miljardeja erilasia tapauksia eri y:n arvoilla. Oli täysin toivotonta päästä lähellekään. Muut ovat testanneet varmasti satoja kertoja enemmän.
No nyt on sen verran turbonörttikilpailu etten taida osallistua
Kannattaa ehdottomasti osallistua.
Voit lyödä vetoa siitä löytyykö vai eikö löydy vastaavaa lukua. Pienin panos on miljoona euroa. Panosta ei tarvitse maksaa etukäteen. Maksut kerätään vasta kun tulos selviää. Kaikkien on pakko osallistua. Mitä teet?
No sehän pomppas ihan parin lauseen välillä siitä että "kannattaa osallistua", siihen että "kaikkien on pakko osallistua".
Jokainen matematiikasta jotain tietävä osallistuu heti. Itse löin vetoa miljardilla löytymisen puolesta.
Täysin riskitöntä. Voi voittaa useita senttejä. Ei voi missään tilanteessa edes treoriassa hävitä.
Mikä sinulle on epäselvää?
Mut mitä jos ei osallistu?
Ihan sama. Laitan kaks euroo sen puolesta ettei ikinä tulla löytämään.
Hävisit. Miljoonat matemaatikot jakavat keskenään sinun eurosi.
Miten tuon voi ikinä todistaa, ettei löydy? Mieti hetki. Voisi hyvin löytyä, vaikka p olisi kolminumeroinen.
Ääretön^2 on iso luku.
No entä jos laitan 3 euroo?
Miljoona on pienin panos. Laita miljardi, niin jotkut matemaatikot saattaisivat saada kympin. Osa on pelannut triljoonilla, joten vaikea laskea miten voitot jakautuisivat. Kymmenissä vuosissa ehtii kertyä mielettömiä summia ja syntyä tuhansia uusia älykkäitä matemaatikkoja.
Laitoin jo kolme euroo. Jos oisin miljardööri ni sitte voisin pistää miljoonan, mutta nyt ei oo ihan niin suurta rahaa maksaa siitä ilosta että ääretön määrä matemaatikkoja jakaa äärettömän suurilla panoksilla eurojani palasiin ja tappelee äärettömän kauan ketä saa suurimman määrän infinitesimaaleja.
Todennäköisyys sille, ettei löytyisi vastaavaa ratkaisua lähestyy nollaa vaikka miten laskisi.
Jos keskittyy vain p:n arvoon 6, niin lähestyykö tuolloinkin vastaava todennäköisyys nollaa? Pienenee kyllä, mutta aika hitaasti.
Piti tietysti olla y:n arvoon 6. Siis kuusinumeroisiin p:n arvoihin.
Päinvastoin. Todennäköisyys lähestyyy ääretöntä. Taisit unohtaa kerto taulun
Ja sinä matematiikan ja suomen kielen.
Älä jatkuvasti jaa typeriä venäläisiä oppejasi täällä.
Tämmöstä se teettää kun ei osaa kerto taulua ja lähtee pätemään intter netissä! Kaikea hulua sitä tulee kirjoiteltua, jos tajuaisit niin häpeäisit!