Formula za izbacivanje svih prostih brojeva

Formula za "izbacivanje" svih prostih brojeva 12.11.2008. u 00:57 · pre 219 meseci #1

Poznato je da ne postoji formula pomoću koje se mogu dobiti svi prosti brojevi...
Ima li ovdje nekih pomaka ili pribliznih rjesenja...

Re: Formula za "izbacivanje" svih prostih brojeva 12.11.2008. u 09:03 · pre 219 meseci #2

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.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Formula za "izbacivanje" svih prostih brojeva 12.11.2008. u 11:39 · pre 219 meseci #3

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...

Re: Formula za "izbacivanje" svih prostih brojeva 12.11.2008. u 11:55 · pre 219 meseci #4

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.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Formula za "izbacivanje" svih prostih brojeva 12.11.2008. u 12:34 · pre 219 meseci #5

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)?

Re: Formula za "izbacivanje" svih prostih brojeva 12.11.2008. u 18:56 · pre 219 meseci #6

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".

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Formula za "izbacivanje" svih prostih brojeva 12.11.2008. u 21:51 · pre 219 meseci #7

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?

Re: Formula za "izbacivanje" svih prostih brojeva 12.11.2008. u 23:20 · pre 219 meseci #8

Evo tog polinoma:

$P(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z)=\\ =(k + 2) \Bigg( 1-\bigg(wz + h + j - q\bigg)^2-\bigg((gk + 2g + k + 1)(h + j)+h-z\bigg)^2-\bigg(2n + p + q + z - e\bigg)^2-\\-\bigg(16(k + 1)^3(k + 2)(n + 1)^2+1-f^2\bigg)^2- \bigg(e^3(e + 2)(a + 1)^2 + 1 - o^2\bigg)^2 - \bigg((a^2 - 1)y^2 + 1 - x^2\bigg)^2-\\ - \bigg(16r^2y^4(a^2- 1)+1-u^2\bigg)^2-\bigg(\Big(\big(a + u^2(u^2- a)\big)^2-1\Big)(n+4dy)^2+ 1 - (x + cu)^2\bigg)^2 - \bigg(n + l + v - y\bigg)^2-\\- \bigg((a^2 - 1)l^2 + 1 - m^2\bigg)^2 - \bigg(ai + k + 1 - l - i\bigg)^2 - \bigg(p + l(a - n - 1) + b(2an + 2a - n^2 - 2n - 2) - m\bigg)^2-\\ - \bigg(q + y(a - p - 1) + s(2ap + 2a - p^2 - 2p - 2) - x\bigg)^2 - \bigg(z + pl(a - p) + t(2ap - p^2 - 1) - pm\bigg)^2\Bigg)$

Moguće je poboljšati bilo stepen polinoma, bilo broj promenljivih. U prvom slučaju postoji polinom stepena $5$ , ali on koristi $42$ promenljive. Broj promenljivih je pak moguće svesti na $10$ , no tada je stepen polinoma otprilike $1.6\cdot 10^{45}$ .

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: Formula za "izbacivanje" svih prostih brojeva 13.11.2008. u 00:51 · pre 219 meseci #9

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.

Re: Formula za "izbacivanje" svih prostih brojeva 13.11.2008. u 01:19 · pre 219 meseci #10

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 ??

Re: Formula za "izbacivanje" svih prostih brojeva 13.11.2008. u 09:11 · pre 219 meseci #11

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

Re: Formula za "izbacivanje" svih prostih brojeva 13.11.2008. u 12:04 · pre 219 meseci #12

Umesto $(k+1)3$ treba da stoji $(k+1)^3$ .

No, ako je polinom tacan i ovako faktorisan, to znaci da postoje dve vrednosti za $k$ (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.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Formula za "izbacivanje" svih prostih brojeva 13.11.2008. u 12:06 · pre 219 meseci #13

miki069

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

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Formula za "izbacivanje" svih prostih brojeva 13.11.2008. u 12:12 · pre 219 meseci #14

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

Re: Formula za "izbacivanje" svih prostih brojeva 13.11.2008. u 13:36 · pre 219 meseci #15

Citat:

Teoreticar:
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 ??

Citat:

Matijasevic's polynomial

Notice that this polynomial factors! Look at the special form of the second part: it is one minus a sum of squares, so the only way for it to be positive is for each of the squared terms to be zero (this is a trick of Putnam's).

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

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Re: Formula za "izbacivanje" svih prostih brojeva 13.11.2008. u 14:01 · pre 219 meseci #16

Citat:

miki069:
Vidi se da i tempo rasta koeficijenta razredjenosti polako pada...
Da li taj koeficijent ima maximum (gornji limes konačan) kome polako teži?

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

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: Formula za "izbacivanje" svih prostih brojeva 13.11.2008. u 14:46 · pre 219 meseci #17

Citat:

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

OK, $k\in\{-3,-1\}$ . Jeli sada bolje?

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Formula za "izbacivanje" svih prostih brojeva 13.11.2008. u 14:49 · pre 219 meseci #18

Citat:

uranium: Notice that this polynomial factors! Look at the special form of the second part: it is one minus a sum of squares, so the only way for it to be positive is for each of the squared terms to be zero (this is a trick of Putnam's).

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

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Formula za "izbacivanje" svih prostih brojeva 13.11.2008. u 15:17 · pre 219 meseci #19

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...

O prostim brojevima.doc19.5k

Re: Formula za "izbacivanje" svih prostih brojeva 13.11.2008. u 15:30 · pre 219 meseci #20

Citat:

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

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

Citat:

Teoreticar:
...gdje k može ima samo dve vrednosti i to:k=-1 v k=-3
Jeli sad sve OK?

Ne (vidi prethodni pasus).

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Forum kao aplikacija na telefonu

Srodne teme