Alkuluvuista löytynyt (uusi) ominaisuus

No jos tuo on totta, että kyse on vain satunnaisesta alkupään heilahteluista, niin olen kyllä pettynyt Tekniikka ja Talous -lehden artikkeliin. Minua huijattiin! :(

Alkuluvut kirjoitti:

No jos tuo on totta, että kyse on vain satunnaisesta alkupään heilahteluista, niin olen kyllä pettynyt Tekniikka ja Talous -lehden artikkeliin. Minua huijattiin! :(

Kyse on tosiaan vain alkupään heilahtelusta, mutta "löydös" onkin juuri se, että se ei ole ihan satunnaista, vaan siinä on tuollaisia systemaattisia harhoja, että jotkin tuplet ovat toisia yleisempiä (esim (9, 1) vs. (9, 9)).

Ja tämä kaikkihan oli siis vasta konjektuurin tasolla, muutenkaan :D.

Mutta Tekniikka & Talous -lehden artikkeli antaa tosiaan vähän väärän kuvan jutusta.

En voi tutkia mielivaltaiselta väliltä, kun käytän Eratostheneen seulaa alkulukujen tuottamiseen ja siinä tarkastelu täytyy aloittaa luvusta 2. Se tuotti 10 miljoonaa pienemmät alkuluvt vaivaisessa 22 sekunnissa. Muut tavat ovat tuskastuttavan hitaita.

https://fi.wikipedia.org/wiki/Eratostheneen_seula

Alkuluvut kirjoitti:

En voi tutkia mielivaltaiselta väliltä, kun käytän Eratostheneen seulaa alkulukujen tuottamiseen ja siinä tarkastelu täytyy aloittaa luvusta 2. Se tuotti 10 miljoonaa pienemmät alkuluvt vaivaisessa 22 sekunnissa. Muut tavat ovat tuskastuttavan hitaita.

https://fi.wikipedia.org/wiki/Eratostheneen_seula

Lue lisää

Höpö höpö! Käytä Python:ia. Voit tehdä ihan mitä vain noin kymmenen rivin ohjelmalla. Voit tutkia melivaltaisen isoja lukuja täysin automaattisesti. Hidastuu tietysti lukujen kasvaessa yli 64-bittisiksi ja lisää hidastusta tulee yli 128-bittisissä. Kaikki tapahtuu automaattisesti. Lataa tarvittavat ohjelmistopaketit, esim. gmpy2.

PythonillaOnnistuu kirjoitti:

Höpö höpö! Käytä Python:ia. Voit tehdä ihan mitä vain noin kymmenen rivin ohjelmalla. Voit tutkia melivaltaisen isoja lukuja täysin automaattisesti. Hidastuu tietysti lukujen kasvaessa yli 64-bittisiksi ja lisää hidastusta tulee yli 128-bittisissä. Kaikki tapahtuu automaattisesti. Lataa tarvittavat ohjelmistopaketit, esim. gmpy2.

Lue lisää

Vai että höpö höpö. En osaa käyttää ohjelmakirjastoja enkä Pythonilla ole koskaan ohjelmoinnut. Joskus C:llä olen yrittänyt käyttää ohjelmakirjastoja - siis, jotta saisin ominaisuuksia käyttöön, joita ei peruskielessä ole - mutta ohjelmat eivät menneet läpi edes käännösvaiheesta. Ohjelmoin REBOL:lla. Tai no, täytyy miettiä - jospa joku päivä innostuisin kokeilemaan Pythonia. Olisihan tuo mielenkiintoinen tutkimusaihe. Ai on siinä siis ihan peruskielessä mahdollisuus käyttää mielivaltaisen suuria lukuja? Ei tarvitsisi käyttää edes mitään ohjelmakirjastoja?

Ai niin, ja tietokoneeni muistikapasiteettikin tulee vastaan. Pystyin tällä koneella laskemaan vain kaikki alle 10 miljoonan alkuluvut.

PythonillaOnnistuu kirjoitti:

Höpö höpö! Käytä Python:ia. Voit tehdä ihan mitä vain noin kymmenen rivin ohjelmalla. Voit tutkia melivaltaisen isoja lukuja täysin automaattisesti. Hidastuu tietysti lukujen kasvaessa yli 64-bittisiksi ja lisää hidastusta tulee yli 128-bittisissä. Kaikki tapahtuu automaattisesti. Lataa tarvittavat ohjelmistopaketit, esim. gmpy2.

Lue lisää

Gmpy2:n next_prime(x) on supertehokas. Isoja alkulukuja käsittelevissä nopeutetuissa kirjasto-ohjelmissa on aina häviävän pienen pieni virhemahdollisuus. Eli pitää hieman ymmärtää mitä tekee. Ei mitään merkitystä tälläisissä pienimuotoisissa tilastollisissa laskuissa.

PythonillaOnnistuuKaikki kirjoitti:

Gmpy2:n next_prime(x) on supertehokas. Isoja alkulukuja käsittelevissä nopeutetuissa kirjasto-ohjelmissa on aina häviävän pienen pieni virhemahdollisuus. Eli pitää hieman ymmärtää mitä tekee. Ei mitään merkitystä tälläisissä pienimuotoisissa tilastollisissa laskuissa.

Lue lisää

Tuo erittäin pieni virhemahdollisuus kokee vain yli 64-bittisiä lukuja (18x10^18). Ja aina kun mennään alkuluvuissa paljon yli 64-bitin, alkaa tulla kotikoneissa selviä hitausongelmia. Nuo kirjasto-ohjelmat siirtyvät kyllä automaattisesti multiprocessing-tilaan, mutta se tuhlaa tehoa nopeuden kustannuksella.

Ohjelmoija kirjoitti:

Ai niin, ja tietokoneeni muistikapasiteettikin tulee vastaan. Pystyin tällä koneella laskemaan vain kaikki alle 10 miljoonan alkuluvut.

Ei niitä alkulukuja mihinkään tarvitse tallentaa. Et tarvitse juuri lainkaan muistia. Voit laskea helposti vaikka 1000 miljoonalla alkuluvulla. Kannattaa pysytellä aluksi 64-bittisisä luvuissa. Niissäkin riittää pureskeltavaa koneesi eliniäksi. 18 triljoonaa.

No, en sitten ehkä Pythonilla jos sen ohjelmakirjastoissa on alkulukuja käsitteleviä funktioita, mutta jos haluan laskea alkuluja Eratostheneen seulalla ja laskea esimerkiksi kaikki 10 miljoonaa pienemmät alkuluvut niin minun on tehtävä 10 miljoona alkioinen true/false taulukko. Vähän yli 10 miljoonaa arvoilla ohjelma kaatui ajo-aikaiseen virheeseen: "Not enough Memory"

Ohjelmoija kirjoitti:

Vai että höpö höpö. En osaa käyttää ohjelmakirjastoja enkä Pythonilla ole koskaan ohjelmoinnut. Joskus C:llä olen yrittänyt käyttää ohjelmakirjastoja - siis, jotta saisin ominaisuuksia käyttöön, joita ei peruskielessä ole - mutta ohjelmat eivät menneet läpi edes käännösvaiheesta. Ohjelmoin REBOL:lla. Tai no, täytyy miettiä - jospa joku päivä innostuisin kokeilemaan Pythonia. Olisihan tuo mielenkiintoinen tutkimusaihe. Ai on siinä siis ihan peruskielessä mahdollisuus käyttää mielivaltaisen suuria lukuja? Ei tarvitsisi käyttää edes mitään ohjelmakirjastoja?

Lue lisää

Pythonin perusteet on äärimmäisen helppo oppia. Et välttämättä tarvitse mitään ylimääräisiä kirjasto-ohjelmia. Ne ovat tehty vain nopeuttamaan määrättyjä laskutoimituksia. Esim. luvun toteaminen alkuluvuksi voidaan tehdä tyhmästi hitaasti tai erittäin älykkäitä monimutkaisia algoritmeja käyttäen nopeasti.

Itse käytän Linux Ubuntua. Siinä Python (kolme eri versiota) valmiiksi asennettuna. Windowsiin se pitää aina erikseen asentaa. Onnistuu helposti. Netti on täynnä ohjeita. Eri Python versiot eivät ole keskenään yhteensopivia ja ne vaativat aina niille käännetyt ohjelmakirjastot. Kannattanee aloittaa uusimmasta eli Python 3:sta. (Sen kanssa ei tietysti vielä toimi jotkut ihan kaikki vanhat hyvät kirjasto-ohjelmat, joten ...)

Minusta Pythonilla koodattu Atkinsin seula ei vie niin paljon muistia. Kokeilin laskea arvoon 20 miljoonaa asti ja se suoriutui onnistuneesti, Koodi sivulta https://stackoverflow.com/questions/21783160/sieve-of-atkin-implementation-in-python

Ohjelmoija kirjoitti:

No, en sitten ehkä Pythonilla jos sen ohjelmakirjastoissa on alkulukuja käsitteleviä funktioita, mutta jos haluan laskea alkuluja Eratostheneen seulalla ja laskea esimerkiksi kaikki 10 miljoonaa pienemmät alkuluvut niin minun on tehtävä 10 miljoona alkioinen true/false taulukko. Vähän yli 10 miljoonaa arvoilla ohjelma kaatui ajo-aikaiseen virheeseen: "Not enough Memory"

Lue lisää

Jos sinulla olisi käytössä kirjastofunktio nextprime(x) (tai next_prime(x)), miten tekisit ohjelmasi?

x = 9876543210123456789
Tähän joku silmukkarakenne
p = next_prime(x) ¤Haetaan seuraava x:ää suurempi alkuluku
...
x = p

Tietysti on hyvä opetella tekemään ensin itse kaikki älykkäästi pienillä luvuilla nopeasti muistia tuhlaten, mutta aina tulee rajat vastaan. Sitten pitää vaan luottaa uusien 64-bittisten prosessoreiden äärimmäiseen nopeuteen ja uskoa, että monet kirjasto-ohjelmat on tehty paremmin kuin mihin itse pystyisi. Saattaa tuhlautua muutama minuutti aikaa, mutta sitä riittää! Jos on käytössä monta ydintä, niihin voi käynnistää ohjelman eri alkuarvoilla.

i7_8700KonNopea kirjoitti:

Jos sinulla olisi käytössä kirjastofunktio nextprime(x) (tai next_prime(x)), miten tekisit ohjelmasi?

x = 9876543210123456789
Tähän joku silmukkarakenne
p = next_prime(x) ¤Haetaan seuraava x:ää suurempi alkuluku
...
x = p

Tietysti on hyvä opetella tekemään ensin itse kaikki älykkäästi pienillä luvuilla nopeasti muistia tuhlaten, mutta aina tulee rajat vastaan. Sitten pitää vaan luottaa uusien 64-bittisten prosessoreiden äärimmäiseen nopeuteen ja uskoa, että monet kirjasto-ohjelmat on tehty paremmin kuin mihin itse pystyisi. Saattaa tuhlautua muutama minuutti aikaa, mutta sitä riittää! Jos on käytössä monta ydintä, niihin voi käynnistää ohjelman eri alkuarvoilla.

Lue lisää

En pääse alkua pidemmälle. Tämä ohjelma ei tulosta mitään vaikka sen pitäisi. Väliltä 100000000000000 ...10000000000010 löytyvät alkuluvut:
100000000000031
100000000000067
100000000000097
100000000000099
Mutta mitään ei tulostu esim. parin (1,7) eikä muunkaan kohdalla.
import gmpy2
from gmpy2 import mpz
from gmpy2 import mpfr
eka = mpz(100000000000000)
toka = mpz(100000000000100)
vikat = [1,3,7,9]
for luku1 in range(mpz(eka), mpz(toka)):
if gmpy2.is_prime(luku1):
print luku1
for vika1 in range(0, 4):
for vika2 in range(0, 4):
print(vika1, vika2)
for luku1 in range(mpz(eka), mpz(toka)):
if gmpy2.is_prime(luku1):
string1=str(luku1)
vikamrk1=string1[len(string1)-1]
if vikamrk1 == str(vika1):
luku2 = gmpy2.next_prime(luku1)
string2=str(luku2)
vikamrk2=string2[len(string2)-1]
if vikamrk1==vikamrk2:
print luku1, luku2, vika1, vika2

Ohjelmoija kirjoitti:

En pääse alkua pidemmälle. Tämä ohjelma ei tulosta mitään vaikka sen pitäisi. Väliltä 100000000000000 ...10000000000010 löytyvät alkuluvut:
100000000000031
100000000000067
100000000000097
100000000000099
Mutta mitään ei tulostu esim. parin (1,7) eikä muunkaan kohdalla.
import gmpy2
from gmpy2 import mpz
from gmpy2 import mpfr
eka = mpz(100000000000000)
toka = mpz(100000000000100)
vikat = [1,3,7,9]
for luku1 in range(mpz(eka), mpz(toka)):
if gmpy2.is_prime(luku1):
print luku1
for vika1 in range(0, 4):
for vika2 in range(0, 4):
print(vika1, vika2)
for luku1 in range(mpz(eka), mpz(toka)):
if gmpy2.is_prime(luku1):
string1=str(luku1)
vikamrk1=string1[len(string1)-1]
if vikamrk1 == str(vika1):
luku2 = gmpy2.next_prime(luku1)
string2=str(luku2)
vikamrk2=string2[len(string2)-1]
if vikamrk1==vikamrk2:
print luku1, luku2, vika1, vika2

Lue lisää

Siis väliltä 100000000000000...100000000000100

Ohjelmoija kirjoitti:

Siis väliltä 100000000000000...100000000000100

Koodi siisteyti paljon modulos % operaattorilla, mutta ei se vieläkään toimi.
import gmpy2
from gmpy2 import mpz
eka = mpz(100000000000000)
toka = mpz(100000000000100)
vikat = [1,3,7,9]
for luku1 in range(mpz(eka), mpz(toka)):
if gmpy2.is_prime(luku1):
print luku1
for vika1 in range(0, 4):
for vika2 in range(0, 4):
print(vika1, vika2)
for luku1 in range(mpz(eka), mpz(toka)):
if gmpy2.is_prime(luku1):
if vika1 == luku1 % 10:
luku2 = gmpy2.next_prime(luku1)
if vika2 == luku2 % 10:
print luku1, luku2, vika1, vika2

Ohjelmoija kirjoitti:

Koodi siisteyti paljon modulos % operaattorilla, mutta ei se vieläkään toimi.
import gmpy2
from gmpy2 import mpz
eka = mpz(100000000000000)
toka = mpz(100000000000100)
vikat = [1,3,7,9]
for luku1 in range(mpz(eka), mpz(toka)):
if gmpy2.is_prime(luku1):
print luku1
for vika1 in range(0, 4):
for vika2 in range(0, 4):
print(vika1, vika2)
for luku1 in range(mpz(eka), mpz(toka)):
if gmpy2.is_prime(luku1):
if vika1 == luku1 % 10:
luku2 = gmpy2.next_prime(luku1)
if vika2 == luku2 % 10:
print luku1, luku2, vika1, vika2

Lue lisää

Kokeilepa näin: http://tpcg.io/vcW62X
Tekeekö haluamasi eli halusitko tulostaa ne vierekkäiset alkulukuparit ja niiden vikat numerot?

Virhe ylläolevassa taitaa olla siinä, että testaat
if vika1 == luku1 % 10:
mutta eihän sinun tarvitse testata tuota vaan vain katsoa mitkä vikat luvut on.
Tuossa noin testaamisessa käy niin, että muuttuja vika1 on jäänyt edellisessä luupissa (jossa ilmeisesti halusit tulostaa kaikki mahdolliset parit)
for vika1 in range(0, 4):
for vika2 in range(0, 4):
print(vika1, vika2)
viimeiseen sijoitettuun arvoon, samoin kuin muuttuja vika2:kin, joten sen takia mitään ei tulostu, kun tuolla välillä ei ole yhtään (9,9) paria.

Ja joo, täällä forumilla ylimääräiset väli-merkit poistuvat, joten ainakaan Python koodia on tänne hankala postata. Mutta tuolla linkatulla sivulla sitä voi jopa suorittaa (klikkaa Execute ylävasemmalla).

Muuten, ehdotus tuohon koodiin: käytä while-luuppia ja pidä muistissa missä luvussa olet menossa. Kun otat seuraavan alkuluvun, niin jatka siitä. Testaa jos mennään yli loppuarvon ja breikkaa luuppi siinä tapauksessa.

Kanootti3 kirjoitti:

Kokeilepa näin: http://tpcg.io/vcW62X
Tekeekö haluamasi eli halusitko tulostaa ne vierekkäiset alkulukuparit ja niiden vikat numerot?

Virhe ylläolevassa taitaa olla siinä, että testaat
if vika1 == luku1 % 10:
mutta eihän sinun tarvitse testata tuota vaan vain katsoa mitkä vikat luvut on.
Tuossa noin testaamisessa käy niin, että muuttuja vika1 on jäänyt edellisessä luupissa (jossa ilmeisesti halusit tulostaa kaikki mahdolliset parit)
for vika1 in range(0, 4):
for vika2 in range(0, 4):
print(vika1, vika2)
viimeiseen sijoitettuun arvoon, samoin kuin muuttuja vika2:kin, joten sen takia mitään ei tulostu, kun tuolla välillä ei ole yhtään (9,9) paria.

Ja joo, täällä forumilla ylimääräiset väli-merkit poistuvat, joten ainakaan Python koodia on tänne hankala postata. Mutta tuolla linkatulla sivulla sitä voi jopa suorittaa (klikkaa Execute ylävasemmalla).

Muuten, ehdotus tuohon koodiin: käytä while-luuppia ja pidä muistissa missä luvussa olet menossa. Kun otat seuraavan alkuluvun, niin jatka siitä. Testaa jos mennään yli loppuarvon ja breikkaa luuppi siinä tapauksessa.

Lue lisää

Jotai niinkun tähän tyyliin: http://tpcg.io/stl5x1

Tällä tavoin voisi tallentaa löytyneiden parien lukumäärät Pythonin dict:iin: http://tpcg.io/5rYcQ8

Kanootti3 kirjoitti:

Jotai niinkun tähän tyyliin: http://tpcg.io/stl5x1

Kiitoksia! Nyt sun koodi löytää lukuparit :) Nyt voin alkaa taulukoimaan ja "tilastoimaan" niitä.

Kanootti3 kirjoitti:

Tällä tavoin voisi tallentaa löytyneiden parien lukumäärät Pythonin dict:iin: http://tpcg.io/5rYcQ8

Joo, sähän teitkin sitten koko koodin ja veit multa ohjelmointi ilon :) Meillä meni vähän ristiin kommentoinnit. Ehdit juri ennen mun seuraavaa kommenttia julkaisemaan koko koodin - siis sen lukuparien tilastoinninkin.

Kanootti3 kirjoitti:

Tällä tavoin voisi tallentaa löytyneiden parien lukumäärät Pythonin dict:iin: http://tpcg.io/5rYcQ8

Perättäisten alkulukujen viimeisten numeroiden tilasto väliltä kvadriljoona (10 potetenssiin 24) ja (kvadriljoona miljardi).
(7, 3) : 1166576
(9, 3) : 1144502
(1, 3) : 1220574
(3, 7) : 1188492
(9, 1) : 1259451
(7, 1) : 1141032
(3, 1) : 1129175
(7, 7) : 991558
(9, 9) : 995211
(3, 9) : 1213985
(1, 9) : 1096316
(1, 7) : 1212767
(3, 3) : 990388
(9, 7) : 1130502
(1, 1) : 995038
(7, 9) : 1224154
Todennäköisyys että 9:n seuraisi 1 useammin kuin 9 on pienentynyt oleellisesti. Tässä enää 17% suurempi on tn. sille että seuraa 9(mikäli osasin prosenttilaskun oikein). Mun konjektuuri on, että eri peräkkäisten lukuparien määrät lähestyvät toisiaan kun alkulukujen määrä lähestyy ääretöntä ;) .