Alkuluvut

Seuraa 
Viestejä45973
Liittynyt3.9.2015

Miksi ihmisille jaetaan palkintoja siitä että, he löytävät vaikka, sanotaanko 9 lukuisen alkuluvun?

Olen jo kauan sitten törmänny näihin alkulukugeneraattoireihin. Niillä saa tuotettua alkulukuja koneen voimilla. Vaikka näkemäni ovat tuottaneet lukuja vain noin miljoonaan saakka, kyllä luulen, että miljardiinkin saakka laskevia on tai niitä voitaisiin ohjelmoida.

Eikö vai riitä? Siis palkinnonantajat vaativat vai todistusta? No tehkööt uuden ohjelman joka luo kirjallisen raportin siitä ettei jotain lukua voida jakaan millään muulla kuin ykkösellä ja itsellä.

Tyhmää, sanon minä.

Kommentit (14)

Vierailija

Suurten alkulukujen löytäminen on erittäin työlästä. Vieläkään ei tunneta determinististä polynomiaikaista algoritmia jolla voitaisiin varmistaa että joku tietty alkuluku tosiaan on alkuluku. Tämä tarkoittaa että algoritmi antaisi AINA oikean tuloksen kyllä tai ei ja lisäksi se tapahtuisi ajassa n^k jossa n on annetun luvun pituus ja k on jokin vakio. Määritelmän kannalta käytetyllä lukujärjestelmällä ei ole merkitysta mutta käytännössä se on usein joko 2 kantainen binäärinen järjestelmä tai jokin kakkosen potenssi esim. 2^8 kantainen järjestelmä jolloin jokainen luvun alkio on tavu.

Tähän tehtävään on kehitetty sekä probabalistisia algoritmeja, joilla saatu ratkaisu voi olla väärä tietyllä todennäköisyydellä, sekä exponentiaalisia algoritmeja. Exponentiaalisten algoritmien ongelma on se että ne tarvitsevat erittäin suuria määriä laskentatehoa, esim.Oletetaan että n=1000 ja 1GHz prosessori laskee yhden operaation kellojaksossa, joten n^2 ajassa toimiva algoritmi kestäisi noin sekunnin kun taas 2^n algoritmi tarvitsisi noin 10^266 vuotta.

Lisäksi on olemassa algoritmeja tietyn muotoisten lukujen tarkistamiseksi. Suurimmat nykyään tunnetut alkuluvut ovatkin muotoa 2^k-1 eli Mersennen alkulukuja. Tätä kirjoittaessa suurin tunnettu (Mersennen) alkuluku on 2^25,964,951-1, eli noin 10^7,816,230. Vertailun vuoksi maailmankaikkeuden alkeishiukkasten lukumäärä on luokkaa 10^80.

Palkintoja uusien alkulukujen löytämisestä jaetaan lähinnä sen takia että uusien lukujen löytämiseksi tarvitsee useimmiten kehittää uusia algoritmeja. Vaikka tietokoneiden laskuteho kasvaakin 2-kertaiseksi parissa vuodessa, eli exponentiaalisesti, uusille pituuden kertaluokille 10-järjestelmässä päästäisiin vain noin 5 vuoden välein. Kuitenkin pienelläkin algoritmin parannuksella saatetaan päästä useampiakin numeroita suurempien lukujen kimppuun.

Vierailija

Alku-luvun käsitteeksi voidaan sanoa lukua jota ei pysty jakamaan muuta kuin 1 ja omalla itsellään.
Tällä hetkellä alkulukuja lasketaan että saadaan tietoon pystyykö nollan arvo
olla muu kuin nolla.
Itse kysyisin että onko 1 alku-luku?

Vierailija

Itse tein juuri huvikseni ohjelman joka etsii alkulukuja. Toimii vielä jokseenkin hyvin kymmenenmiljoonan tienoilla olevissa luvuissa, mutta sadassamiljoonassa alkaa loppua koneesta tehot (tai sitten vika on ohjelman tekiässä...).

Onko kyseinen "suoritus" muuten mitään lukion toisen vuosikurssin opiskelijalta?

pöhl
Seuraa 
Viestejä828
Liittynyt19.3.2005

Osasin minäkin lukioikäisenä tuollaisen ohjelman tehdä. Joskus lukiossa kilpailtiin myös kavereiden kesken siitä, kuka tekee nopeimman kokonaisluvun tekiöihin jakavan ohjelman TI-86:lle.

Alkulukuja etsivä ohjelma on kuitenkin melko helppo tehdä, jos tuntee algoritmit. Ilmeisesti nopein tunnettu yleisen kokonaisluvut alkuluvuksi tarkastava algoritmi on Agrawalin, Manindran ja Saxenin kehittämä algoritmi tai siitä jotenkin optimoitu versio. Suurimmat tunnetut alkuluvut ovat nykyään yleensä Mersennen alkulukuja, joiden testaamiseen käytetään Lucasin-Lehmerin testiä.

Joten miten määritellä "onko tuo hieno saavutus"? Varmaan aika harva lukiolainen osaa tuollaisen tehdä suhteessa koko ikäluokkaan, mutta on lukiolaisissa taitavia ohjelmoijia, jotka ovat lukeneet myös lukuteoreettisista algoritmeista. Olen itsekin miettinyt välillä haastavia ohjelmointiongelmia. Kun sitten olen opetellut oikeat algoritmit, huomasin, että enpä keksinytkään mitään mullistavaa.

Vierailija
Puuhikki
Joskus lukiossa kilpailtiin myös kavereiden kesken siitä, kuka tekee nopeimman kokonaisluvun tekiöihin jakavan ohjelman TI-86:lle.

Missä nörttiporukassa oikein pyörit?

Vierailija

heeeei löysin vahingossa yhden: 2^25,964,951-1:*10000000000000000
000000000000000000000000000000000000000000000000000000000000000
Lähettäkää rahaa, kiitos.

Vierailija
Pinky&Brain
heeeei löysin vahingossa yhden: 2^25,964,951-1:*10000000000000000
000000000000000000000000000000000000000000000000000000000000000
Lähettäkää rahaa, kiitos.

Toki lähettäisin, mutta kun lukusi ei ole alkuluku.

Vierailija
Puuhikki
Alkulukuja etsivä ohjelma on kuitenkin melko helppo tehdä, jos tuntee algoritmit. Ilmeisesti nopein tunnettu yleisen kokonaisluvut alkuluvuksi tarkastava algoritmi on Agrawalin, Manindran ja Saxenin kehittämä algoritmi tai siitä jotenkin optimoitu versio. Suurimmat tunnetut alkuluvut ovat nykyään yleensä Mersennen alkulukuja, joiden testaamiseen käytetään Lucasin-Lehmerin testiä.

Ai mitkä algoritmit? Itse laitoin vain testaamaan jaollisuuden (vertaaman onko x/y=(x/y)pyöristettynä alaspäin [x=tutkittava luku, y=sen hetkinen jakaja]) kaikilla luvuilla jotka eivät ole suurempia kuin "alkulukuehdokkaan" neliöjuuri. Jos löytyi luku jolla jako menee tasan laitettiin laskut seis ja luku ei ollut alkuluku. Jos ei löytynyt, luku oli alkuluku. Ei kyllä varmaan kaikista tehokkain menetelmä.. Jokaisen luvun kohdalla kun piti suorittaa max 3*sqrt(x) jakolaskua.

Vierailija
Joza
Ai mitkä algoritmit? Itse laitoin vain testaamaan jaollisuuden (vertaaman onko x/y=(x/y)pyöristettynä alaspäin [x=tutkittava luku, y=sen hetkinen jakaja]) kaikilla luvuilla jotka eivät ole suurempia kuin "alkulukuehdokkaan" neliöjuuri. Jos löytyi luku jolla jako menee tasan laitettiin laskut seis ja luku ei ollut alkuluku. Jos ei löytynyt, luku oli alkuluku. Ei kyllä varmaan kaikista tehokkain menetelmä.. Jokaisen luvun kohdalla kun piti suorittaa max 3*sqrt(x) jakolaskua.

Vaikuttaa melko tehottomalta.. tee ennemmin edes näin:

[code:2c6wqzju]
a = 131 (testattava luku, ei-parillinen)
b = 3

while (b*b <= a)
{
if (desimaaleja(a/b))
break;
b += 2;
}

if (b*b>a)
alkuluku();
else
ei_alkuluku();
[/code:2c6wqzju]

tarvii enää tehä toi desimaaleja funktio, miten haluaa (järkevin toteutus riippuu tietty käytettävästä kielestä).

laskimessa (TI-83) oli kätevä funkkari, joka otti luvusta vain desimaaliosan.

Vierailija

Käytin sen teossa gamemakeria joka siis on suunniteltu pelien tekemiseen mutta toimii yllättävän hyvin missä vain. Siitäkin löytyy tuo toiminto mikä antaa pelkän desimaali-osan, mutta en ihan ymmärtänyt tuota kaavaasi. Pitää vielä mietiskellä niin ehkä sen tajuaa.

EDIT: No nyt ymmärsin. Saatampa koittaakkin tuota.. vähentäähän se puolet jakajista pois.
EDIT2: Nyt se toimii suunnilleen tollatavalla.

Uusimmat

Suosituimmat