» »

Znano novo največje praštevilo

Znano novo največje praštevilo

Slo-Tech - Od včeraj smo lahko prepričani, da je 282.589.933-1 največje znano praštevilo. Gre za število, ki ima v desetiškem zapisu 24.862.048 mest, tako da zapis v stisnjeni obliki (ZIP) zasede več kot 11 MB. Novo praštevilo je našel Patrick Laroche s Floride, ki sodeluje v projektu skupinskega iskanja Mersennovih praštevil GIMPS. Za nagrado prejme 3000 dolarjev in mesto v zgodovini.

Vsa največja znana praštevila so Mersennova praštevila, kakor se imenujejo praštevila, ki jih lahko zapišemo kot 2p - 1, kjer je p tudi praštevilo. Ta niso zelo pogosta, a ker zanje poznamo izjemno hiter test, se pri iskanju praštevil lotevamo prav njih. V splošnem je namreč iskanje praštevil počasno in računsko potratno. Projekt GIMPS je imel v zadnjih petnajstih letih neverjetno veliko sreče. Najnovejše praštevilo je že 12. praštevilo od 220000000-1 dalje, ki ga je odkril GIMPS, sicer pa gre za 51. znano Mersennovo praštevilo. Ker še nismo prečesali vseh možnosti, je mogoče, da se med znanimi Mersenovimi praštevili skriva še kakšno.

51. Mersennovo praštevilo so odkrili že 7. decembra, a so ga uradno potrdili šele sedaj, ko so izvedli še nekaj neodvisnih preverb. Njegovega predhodnika so odkrili decembra lani. GIMPS ni uporaben le za iskanje praštevil, temveč se pogosto uporablja kot test stabilnosti sistemov, saj močno obremeni procesor in pomnilnik. Še vedno pa nestrpno pričakujemo tudi prvo znano praštevilo z vsaj 100 milijoni števk, za katero je razpisana nagrada 150.000 dolarjev.

26 komentarjev

MrStein ::

zapis v stisnjeni obliki (ZIP) zasede več kot 11 MB

Koliko pa zasede z bzip2? LZMA?
Motiti se je človeško.
Motiti se pogosto je neumno.
Vztrajati pri zmoti je... oh, pozdravljen!

7982884e ::

nevem zakaj bi s kakrsnokoli (drugo) obliko kompresije zasedel kaj manj. limit je itak entropija, in ponavadi v prastevilih ni nekih vzorcev, ki bi jih lahko izkoriscal za kompresijo.

StarMafijec ::

Z idealno kompresijo bi zasedal ta zapis malo manj kot 10 MB.

Matevžk ::

Z idealno kompresijo zasede par bajtov. V članku je porabljenih le nekaj znakov. Seveda zapis ni desetiški, ampak z matematično formulo, ampak tudi to je kompresija.
lp, Matevžk

MrStein ::

original (ASCII fajl): 25.359.292 bytes

ZIP: 11 610 317
bzip2 : 11.023.244 bytes
LZMA2 : 11 235 236
LZMA : 11 228 083
Motiti se je človeško.
Motiti se pogosto je neumno.
Vztrajati pri zmoti je... oh, pozdravljen!

Vazelin ::

Zakaj je kurjenje elektrike za iskanje praštevila bolj uporabno od kurjenja elektrike za rudarjenje kriptovalut?>:D Nisem še zasledil, da bi se kdo pritoževal nad temi pointless števili :P

7982884e ::

Matevžk je izjavil:

Z idealno kompresijo zasede par bajtov. V članku je porabljenih le nekaj znakov. Seveda zapis ni desetiški, ampak z matematično formulo, ampak tudi to je kompresija.

to je res, ampak to bi bil bolj format. jaz si lahko izmislim nek svoj simbol za neko nakljucno 100-milijonov dolgo stevilko, mu dodelim neko kombinacijo utf-8 znakov in bo stvar isto zasedala par bajtov.
sicer ne vem zakaj uporabljajo dejanski desetiski zapis v tem primeru, ampak mora imeti neko vrednost.

Vazelin je izjavil:

Zakaj je kurjenje elektrike za iskanje praštevila bolj uporabno od kurjenja elektrike za rudarjenje kriptovalut?>:D Nisem še zasledil, da bi se kdo pritoževal nad temi pointless števili :P

imajo vrednost, zato tudi nagrade. in ta vrednost ima tudi veze s kriptografijo in posledicno kriptovalutami ;)

Zgodovina sprememb…

  • spremenilo: 7982884e ()

SimplyMiha ::

Številu lahko damo poljubno etiketo oz. identifikator, npr. 51. Mersennovo število, pa vemo, za katero število gre. Idealna kompresija je tako zgolj indeksiranje znanih podatkov.

Ko pa hočemo videti oz. prebrati dejansko število, ga moramo še vedno nekje dobiti v celoti.

Gagatronix ::

Mi lahko kdo razlozi kaksna je aplikativna vrednost iskanja teh prastevil? Pa ne mislim zdaj v smislu "Js tega na rabm zkaj dnar za to zapravlajo!!!" bedarije ampak me dejansko zanima vendar sem na tem podrocju totalni neznalec. :)

SimplyMiha ::

Praštevila se uporabljajo za šifriranje (npr. RSA), generiranje hashev (številčnih kod za vse živo), generiranje naključnih števil itd.

Gagatronix ::

Ahh. Najlepsa hvala! :)

win64 ::

SimplyMiha je izjavil:

Številu lahko damo poljubno etiketo oz. identifikator, npr. 51. Mersennovo število, pa vemo, za katero število gre. Idealna kompresija je tako zgolj indeksiranje znanih podatkov.

Ko pa hočemo videti oz. prebrati dejansko število, ga moramo še vedno nekje dobiti v celoti.

Lahko zapišemo številko 24.862.048, kar nam vzame 24bitov. Potem pa imamo tukaj ultra-počasni dekodirnik omenjen v članku :)

neverlucky ::

Gagatronix je izjavil:

Mi lahko kdo razlozi kaksna je aplikativna vrednost iskanja teh prastevil? Pa ne mislim zdaj v smislu "Js tega na rabm zkaj dnar za to zapravlajo!!!" bedarije ampak me dejansko zanima vendar sem na tem podrocju totalni neznalec. :)


Mersenova prastevila vecinoma iscejo samo zato ker jih lahko in je zanimivo vedet katero je najvecje znano prastevilo. Nimajo neke uporabne vrednosti.

Kot pa je nekdo ze omenil, so drugace velika prastevila izredno pomembna za kriptografijo. In nagrade za velika prastevila, ki niso mersenova so se kar nekaj visja.

jb_j ::

Zanimajo me le dejstva, in me zanima kakšen napredek bomo dobili na podlagi tega.

(so mi všeč super-računalniki, ki napovedujejo vreme in podobno)

neverlucky ::

Kakšna je korist od tega, da se povzpneš na Triglav, da se povzpneš na Everest? Da tečeš maraton pod dvema urama? Je ni. Moral boš dojeti, da nekateri preizkušajo meje kaj se še da, kaj je največ kar lahko naredimo, itd. brez da bi to imelo korist za družbo. S podobnim namenom tudi iščejo, katero je največje znano praštevilo. Zarada lastnega zanimanja in nekaj slave, ki jo dobiš, če si to praštevilo odkril ti.

jb_j ::

neverlucky je izjavil:

Kakšna je korist od tega, da se povzpneš na Triglav, da se povzpneš na Everest? Da tečeš maraton pod dvema urama? Je ni. Moral boš dojeti, da nekateri preizkušajo meje kaj se še da, kaj je največ kar lahko naredimo, itd. brez da bi to imelo korist za družbo. S podobnim namenom tudi iščejo, katero je največje znano praštevilo. Zarada lastnega zanimanja in nekaj slave, ki jo dobiš, če si to praštevilo odkril ti.


A hočeš povedat, da niso dosegl povsem nič.

In dosegajo le nove mejnike?
(ki sicer v praksi ne pomenijo ničesar za boljši razvoj)

Zgodovina sprememb…

  • spremenil: jb_j ()

pegasus ::

jb_j je izjavil:

(so mi všeč super-računalniki, ki napovedujejo vreme in podobno)
Tole me je zmotilo - vreme napovedujejo matematično fizikalni modeli, ki jih je moč v obliki algoritmov izvajati na računalnikih.

jb_j ::

pegasus je izjavil:

jb_j je izjavil:

(so mi všeč super-računalniki, ki napovedujejo vreme in podobno)
Tole me je zmotilo - vreme napovedujejo matematično fizikalni modeli, ki jih je moč v obliki algoritmov izvajati na računalnikih.


V bistvu jih napovedujejo računalniki.
(s pomočjo algoritmov, ki jih sestavljajo ljudje, in z neumnimi algoritmi, imamo napačno vremensko napoved)

pegasus ::

jb_j je izjavil:

V bistvu jih napovedujejo računalniki.(s pomočjo algoritmov, ki jih sestavljajo ljudje, in z neumnimi algoritmi, imamo napačno vremensko napoved)
Ne, motiš se, tako kot v praktično vsem, kar pišeš na ta forum. Algoritme lahko računaš peš na roke, ne rabiš računalnikov. Pravtako "neumni" algoritmi ne obstajajo, ta oznaka je samo nekaj, kar jim lahko nalepiš s svojim človeškim razumevanjem koristnosti.

neverlucky ::

jb_j je izjavil:

neverlucky je izjavil:

Kakšna je korist od tega, da se povzpneš na Triglav, da se povzpneš na Everest? Da tečeš maraton pod dvema urama? Je ni. Moral boš dojeti, da nekateri preizkušajo meje kaj se še da, kaj je največ kar lahko naredimo, itd. brez da bi to imelo korist za družbo. S podobnim namenom tudi iščejo, katero je največje znano praštevilo. Zarada lastnega zanimanja in nekaj slave, ki jo dobiš, če si to praštevilo odkril ti.


A hočeš povedat, da niso dosegl povsem nič.

In dosegajo le nove mejnike?
(ki sicer v praksi ne pomenijo ničesar za boljši razvoj)


Tako je, dosegli so nov mejnik, novo največje znano praštevilo. Uporabne vrednosti pa zaenkrat nima. Mogoče je nikoli ne bo imelo, mogoče bo, čeprav dvomim v to.

Kaboom ::

win64 je izjavil:

SimplyMiha je izjavil:

Številu lahko damo poljubno etiketo oz. identifikator, npr. 51. Mersennovo število, pa vemo, za katero število gre. Idealna kompresija je tako zgolj indeksiranje znanih podatkov.

Ko pa hočemo videti oz. prebrati dejansko število, ga moramo še vedno nekje dobiti v celoti.

Lahko zapišemo številko 24.862.048, kar nam vzame 24bitov. Potem pa imamo tukaj ultra-počasni dekodirnik omenjen v članku :)

Ha? Veš da je 24 bitov == 3 Bajte?
Zapis "24.862.048" vzame 10 Bajtov. Brez pik pa 8 Bajtov.
Konec koncev pa je 24.862.048 le število mest (števk) v novo odkritem številu. Vsaka vzame 1 Bajt. Torej celotno število zaseda okrog 24MB.
Če se zatakne - pritisni močneje. Če se zlomi - bil je skrajni čas za nakup novega.

MrStein ::

Ja, v ASCII zapisu. V drugem pa manj. Ali več.
Motiti se je človeško.
Motiti se pogosto je neumno.
Vztrajati pri zmoti je... oh, pozdravljen!

Cervantes ::

To so, oprostite, jajca.
Breaktrough bi bil algoritem, ki bi pokril VSA praštevila.
Še ni, niti na obzorju.

neverlucky ::

Kako to misliš vsa praštevila? Ne razumem čisto tvojega komentarja.

Kaboom ::

Cervantes je izjavil:

To so, oprostite, jajca.
Breaktrough bi bil algoritem, ki bi pokril VSA praštevila.
Še ni, niti na obzorju.

En dober algoritem iskanja je znan:
2P-1 ... rezultat poskusiš delit še s čem drugim razen 1 in rezultatom samim. Če je vedno ostanek, si najdel praštevilo.

Kako pa izračunat vse P v neskončnost, ki vedno dajo rezultat praštevilo, pa izvoli sam izvest preboj v matematiki. Ali pa nov način iskanja. Razen, če si pač samo pisatelj in samo pišeš?
Če se zatakne - pritisni močneje. Če se zlomi - bil je skrajni čas za nakup novega.

Zgodovina sprememb…

  • spremenil: Kaboom ()

win64 ::

Kaboom je izjavil:

win64 je izjavil:

SimplyMiha je izjavil:

Številu lahko damo poljubno etiketo oz. identifikator, npr. 51. Mersennovo število, pa vemo, za katero število gre. Idealna kompresija je tako zgolj indeksiranje znanih podatkov.

Ko pa hočemo videti oz. prebrati dejansko število, ga moramo še vedno nekje dobiti v celoti.

Lahko zapišemo številko 24.862.048, kar nam vzame 24bitov. Potem pa imamo tukaj ultra-počasni dekodirnik omenjen v članku :)

Ha? Veš da je 24 bitov == 3 Bajte?
Zapis "24.862.048" vzame 10 Bajtov. Brez pik pa 8 Bajtov.
Konec koncev pa je 24.862.048 le število mest (števk) v novo odkritem številu. Vsaka vzame 1 Bajt. Torej celotno število zaseda okrog 24MB.

1. Kot je že en komentar povedal. Celoštevilčna številka pri shranjevanju porabi log2(desetiskaStevilka) bitov (zaokroženo navzgor).
2. Ne razumeš. Če zapišeš številko 24.862.048 je ta informacijo dovoljšnja, da pridobiš celotno vsebino. Hitrost pridobitve pa ni ravno najboljša.
3. Za zapis vsako izmed 24.862.048 cifer bi lahko zapisali kot 4bite ali karkoli drugega, stvar odločitve. V članku so pač zapisali to v ASCII format, ker je to ljudem prijazen format.


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Odkrili največje doslej znano praštevilo

Oddelek: Novice / Znanost in tehnologija
136495 (5138) reeves
»

Odkrili novo največje praštevilo

Oddelek: Novice / Znanost in tehnologija
108266 (5189) PaX_MaN
»

Največje znano praštevilo potrjeno

Oddelek: Novice / Znanost in tehnologija
95730 (4583) MrStein
»

Znanost in tehnologija VI.

Oddelek: Novice / Znanost in tehnologija
244635 (3782) whitto
»

Najverjetneje odkrito štirideseto Mersennovo praštevilo

Oddelek: Novice / Znanost in tehnologija
93054 (3054) Thomas

Več podobnih tem