13532385396179 = 13*53**2*3853*96179

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
Ilmianna
Jaa

15 Vastausta


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
Ilmianna
Jaa
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.
Kommentoi
Ilmianna
Jaa
1 VASTAUS:
"Kaikki 64 bittiset luvut (n. 10^19) on jo varmasti testattu monin eri tavoin."
En usko tuota. Pitää odotella vielä muutamia kuukausia tuloksia. Eihän yli 90 % lukujen murskauksia harrastavista matemaatikoista ja ohjelmoijista ole vielä edes kuulleet ongelmasta. Pitää olla käytettävissä tuhansia ytimiä, jotta hommaa kannattaisi edes harkita.

Isojen lukujen jakaminen tekijöihin on aina hidas operaatio. Ja jos se suurin tekijä on vain kaksi- tai kolminumeroinen, testitapausten määrä on pahimmillan luokkaa 10^16.
Kommentoi
Ilmianna
Jaa
+Lisää kommentti
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.
Ilmianna
Jaa
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.
Ilmianna
Jaa
Kommentoi
Ilmianna
Jaa
5 VASTAUSTA:
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.
Kommentoi
Ilmianna
Jaa
Tekijät kirjoitti:
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
Kommentoi
Ilmianna
Jaa
Tekijät kirjoitti:
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.
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.
Kommentoi
Ilmianna
Jaa
Huutiukko kirjoitti:
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.
Kommentoi
Ilmianna
Jaa
Arvellen kirjoitti:
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.
Kommentoi
Ilmianna
Jaa
+Lisää kommentti
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!
Ilmianna
Jaa
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.
Ilmianna
Jaa
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ä. )
Kommentoi
Ilmianna
Jaa
1 VASTAUS:
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.

import primefac
from primefac import factorint
from primefac 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 = 27540000000 - 1 #Keksikää tähän joku oma aloituskohta
for cc in range(0, 1000):
for m in range(0, 10000):
x = x + 1
a = f(x)
if isprime(a): continue
b = f(a)
if isprime(b): continue
c = f(b)
if isprime(c): continue
z = f(c)
if z==x or z==a or z==b or z==c: print "******* Found ******* ",x,a,b,c,z

print cc, x, a, b, c, z
Kommentoi
Ilmianna
Jaa
+Lisää kommentti

Vastaa alkuperäiseen viestiin

13532385396179 = 13*53**2*3853*96179

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

5000 merkkiä jäljellä

Peruuta