Postoji polinom stepena 25 sa 26 promenljivih i sa celim koeficijentima takav da je skup pozitivnihvrednosti tog polinoma za celobrojne vrednosti promenljivih jednak skupu prostih bojeva.

Bio bi ti veoma zahvalan ako bi nam napisao taj polinom - ako si u mogućnosti, veoma me zanima.
Postojel jos neke pojedinosti u vezi toga...

Trenutno mi nije pri ruci knjiga "Hilbertovi problemi i logika" u kojoj je taj polinom napisan, ali cu se potruditi da ga okacim.

Ako ti ovo treba zbog kriptografije, onda ti je ovaj polinom lose resenje.

Ok, hvala ti mnogo...strasno bi me interesovao taj polinom.Ne treba mi za kriptografiju.

Na koji način bi se onda menjale vrednosti promenljivih u tom polinomu (cele vrednosti)?

Zameniš promenljive bilo kojim celim brojevima, izračunaš vrednost izraza, pa ako dobiješ pozitivnu vrednost, onda je to sigurno prost broj, a ako vrednost nije pozitivna, onda jednostavno nisi imao sreće - ne znaš ni da li je prost ni da li je složen. No, svaki prost broj se može dobiti kao pozitivna vrednost tog polinoma za neke celobrojne vrednosti promenljivih. Mislim da ću tek sutra moći da ti pošaljem polinom, ali samo da znaš da je mnogo "ružan".

Ok, hvala ti mnogo,kad stignes napisi nam...

Pa cekaj, kada se taj polinom odredio...koje godine?
Jer, zadnjih godina stalno se govori da ne postoji formula za dobijanje SVIH prostih brojeva.
Prosvetlite me?

Evo tog polinoma:



Moguće je poboljšati bilo stepen polinoma, bilo broj promenljivih. U prvom slučaju postoji polinom stepena , ali on koristi promenljive. Broj promenljivih je pak moguće svesti na , no tada je stepen polinoma otprilike .

_{[Ovu poruku je menjao Bojan Basic dana 13.11.2008. u 13:49 GMT+1]}

Ako ti nešta znači imam napisano programče u Delphi-ju koji za nekih 60 sekundi (na PIV računaru) izgeneriše prvih 4 000 000 prostih brojeva.


Statistika pojave je sledeća:

- 1 000 prost broj je 7 919 (svaki osmi u proseku je prost),
- 10 000 prost broj je 104 729 (svaki deseti u proseku),
- 100 000 prost broj je 1 299 709 (svaki trinaesti u proseku),
- 1000 000 prost broj je 15 485 709 (svaki petnaesti u proseku),
- 4 000 000 prost broj je 67 667 969 (svaki sedamnaesti u proseku),
- 10 000 000 prost broj je 179 424 691 (svaki osamnaesti u proseku).

I tako sve su redji i redji... Al ih ima beskonačno mnogo...
Vidi se da i tempo rasta koeficijenta razredjenosti polako pada...
Da li taj koeficijent ima maximum (gornji limes konačan) kome polako teži?
Ili i taj koeficijent teži beskonačnosti a njih opet ima beskonačno mnogo? Što je moguće ali je neinteresantno.
Ili on već postoji a ja ga ne znam?


Nemam programski odgovor jer ograničenje mi je LONGINT (mislim 2 na 64) u Delphi-ju. Ne mogu ga pustiti do beskonačnosti.
Vreme nije problem.Ovaj skor je sa pisanjem rezultata u txt fajl. Moram onda malo da ga preradim.

Ako ti nešta znači mogu ti dati to programče.


_{[Ovu poruku je menjao miki069 dana 13.11.2008. u 02:15 GMT+1]}

Hvala miki ,ali ne treba za sada...
Hvala Bojane...
Ovo me malo zbunjuje ,jer polinom je faktorisan na dva izraza od kojih je jedan k+2 i ovaj u drugoj velikoj zagradi.Pa onda imamo UVEK proizvod dva cela broja ??

A da mozda tu ne koristi Rimanova zeta funkcija...

Umesto treba da stoji .

No, ako je polinom tacan i ovako faktorisan, to znaci da postoje dve vrednosti za (0 i -2) za koje je vrednost polinoma pozitivna.

Postojanje ovakvog polinoma nije nikakva specificnost skupa prostih brojeva. Podkup skupa prirodnih brojeva se moze ovako predstaviti akko je rekurzivno nabrojiv. Primera radi, ovako se moze predstaviti skup svih prirodnih brojeva n, takvih da je zbir cifara broja n^n!-n! deljiv sa n²+7.

miki069

O raspodeli niza prostih brojeva govori teorema o prostim brojevima (prime number theorem).

Ali za ako je k jednako -2 onda je vrijednost polinoma nula, jer je jedan faktor k+2

... bilo je već sličnih tema:
http://www.elitesecurity.org/p810683

Ne znam šta podrazumevaš pod „tempom rasta koeficijenta razređenosti“, ali ovo u zagradi (svaki ... u proseku) asimptotski je (dokazano), pa vidi da li to odgovara na tvoje pitanje.

OK, . Jeli sada bolje?

Stvarno, ako je poenta u tome da svi kvadrati budu nule, sta onda radi faktor k+2?

Da rezimiramo:
Skup pozitivnih vrednosti polinoma kojeg je napisao gosp. Bojan jednak je skupu prostih brojeva, polinom daje SVE proste brojeve za proizvoljne vrednosti promenljivih , gdje k može ima samo dve vrednosti i to:k=-1 v k=-3
Jeli sad sve OK?

Evo još neki polinomi prvog stepena, nista posebno...

Faktor je upravo prost broj koji dobiješ kao rezultat polinoma kada promenljivima dodeliš vrednosti. Dakle, prost broj dobićeš za (i pogodne vrednosti ostalih slova), dok nema načina da vrednost polinoma bude pozitivna za npr. .

Ne (vidi prethodni pasus).

@Nedeljko:

pogledaj screenshot u prilogu ( kako glasi formulacija teoreme ... )

Ok, hvala ti Bojane, mislim da je sad OK.
Znaci ako zelim da proverim recimo da li je 83 prost ili slozen uzimam k=81. Dalje, trazim vrednosti ostalih promenjivih za koje su svi kvadrati u drugom faktoru nula sto ce rezultirati da drugi faktor ima vrednost 1.
Ako je to moguce (da je vrednost drugog faktora 1) broj jeste prost ??

Sad je sve jasno. Pored ostalog i to da ovaj polinom nema nikakvu prakticnu primenu.

Zar ne mozemo primeniti na ispitivanje da li je neki broj prost?
Ali, ako mogu dobro videti bilo bi jako tesko ??

Za to se koriste drugi algoritmi. Pre svega, testovi pseudoprimalnosti, a ako bas hoces da budes siguran da je neki broj prost, onda su neki indijci pronasli algoritam polinomijalne slozenosti za testiranje primalnosti. No, i taj algoritam je isuvise skup za prakticnu primenu, pa se pribegava (aproksimativnim) testovima (pseudo)primalnosti.

Uklapa se ln(n) u koeficijent razudjenosti.
Sto je n veci i veci sve je blizi iznosu ln(n).
Pustao sam program do milijardu prostih brojeva.
Zato kasnim.

Hvala Bojane.