» »

pra števila..

pra števila..

«
1
2

tx-z ::

a obstaja funkcija za pra števila?? če sm prv povedu :)
mislm.. to more it po enem vrstnem redu 1,3,5,7,11,13,17,19,23,27,29,31,...najprej sm mislu da pač sam 2 prštevaš pa ni tko :)
tx-z

McHusch ::

Če bi obstajala funkcija za praštevila, bi bilo iskanje le-teh veliko lažje, se ti ne zdi? 8-) Obstajajo samo algoritmi, ki ti za določeno število izračunajo, če je praštevilo oz. ti poiščejo vsa praštevila na določenem intervalu.

BTW: 27 ni praštevilo.

Thomas ::

Funkcija je:

F(N) = Signum(((N-1)!+1) mod N)

Signum od 0 je 0, od večjih števil pa 1.

Za praštevila da F(N) = 0. Za ostale da 1.

F(5)=Signum(((5-1)!+1) mod 5)

To je 0, torej 5 je praševilo.

:)

Man muss immer generalisieren - Carl Jacobi

tx-z ::

ja, pa res ni 27 :) 27:9=3 :\

tx-z ::

aha, če prv razumm je to tko:
F(N) = Signum(((N-1)!+1) mod N)
F(17) = Signum(((17-1)!+1) mod 17)

ne, nerazumm, kako pol to sesteješ pa ...
pa še neki
F je funkcija ne
kaj je N
kaj je Signum
kaj je !
kaj je mod
???? >:D
tx-z

Thomas ::

mod je ostanek po deljenju

signum je pa 1, če je število pozitivno in 0, če je 0. Pa seveda -1, če je negativno.

zigam - kok si star?

Itak me pa zanima, kdo je to funkcijo sploh poznal.

:D
Man muss immer generalisieren - Carl Jacobi

tx-z ::

14 :)
a se ti da čist podrobn opisat, kako to zračunaš?
tx-z

Thomas ::

14-1=13

1*2*3*4*5*6*7*8*9*10*11*12*13=6227020800

6227020800+1=6227020801

6227020801/14 = 444787200,071428

Ne deli se brez ostanka, ali kar je isto, mod 14 ni 0 - torej 14 ni praštevilo.

:)
Man muss immer generalisieren - Carl Jacobi

tx-z ::

naprimer 7, k je praštevilo..
7-1=6
1*2*3*4*5*6=720
720+1=721
721/7=103

kako pa pol to zvem a je al ni??
tx-z

Gandalfar ::

Zato, ker ni ostanka pri deljenju :)

McHusch ::

Zato ker se deljenje 721/7 izide brez ostanka, lahko sklepaš da je 7 praštevilo.

tx-z ::

aja, pol sm pa bil že mal zaspan :) nism vidu da ni blo ostanka :)
a to je pol to?
a se da komu še nardit to po tem k je thomas napisu:
F(N) = Signum(((N-1)!+1) mod N)
za številko 7 pa 6 :)
tx-z

Sergio ::

Koliko procesorskega časa potrebujemo, da izračunamo fakulteto števila z milijardo znakov?
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.

tx-z ::

dooooooo :) velik??
a je težko za 6 pa 7 zračunat??? po tisti formuli?
tx-z

Thomas ::

Sergio

> Koliko procesorskega časa potrebujemo, da izračunamo fakulteto števila z milijardo znakov

Precej, precej manj, kot za zračunat fakulteto števila z milijardo in enim znakom. :P

Če pa sprašuješ, če je tale funkcija praktična za velika (ali majhna) števila - ne ni praktična. Zelo je nepraktična.

A obstaja pa praktična? Nihče ne ve. Misli se, da ne, dopušča se pa, da tudi ja. Samo noben je ne pozna.

:)

Man muss immer generalisieren - Carl Jacobi

tx-z ::

ej Thomas, a mi lah po tem F(N) = Signum(((N-1)!+1) mod N)
zračunaš za 7 pa 6 na ta dolg način :) za vsak korak posebi :\ no pa še eno vprašanje? a kdo ve kje bi dubu program k mi lah zračuna na tut več k 1000 decimalk natančn.. no da bi določu do kok natančn naj ti zračuna(pa če se da neomejeno)

Sergio ::

Thomas, še vedno je funkcija bolj praktična od metode "poišči vsa praštevila do njegovega korena". IMO.
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.

Ziga Dolhar ::

Zigam, če ne gre drugače, na malce boljšem kalkulatorju preprosto izračunaš, potem pa slediš postopku:

napišeš na list papirja število z vsemi decimalkami, ki jih vidiš
zmnožiš s 1000,
odšteješ celi del števila.

ponavljaš do takrat, ko imaš dovolj decimalk :] tole
pomnožiš,
odšteješ celi del,
pripišeš na list zadnje 3 decimalke
>> ponavljaj.

... V sili ...

Thomas ::

zigam ... pa kok si ti star?

Po eni strani pri tebi vidim (zelo hvalevredno) ambicioznost, po drugi pa ne znaš rešit tegale?! Ampak nej ti bo!


N=2
N-1=1
1=1
1+1=2
2/2=1



N=3
N-1=2
1x2=2
2+1=3
3/3=1


N=4
N-1=3
1x2x3=6
6+1=7
7/4=1.75


N=5
N-1=4
1x2x3x4=24
24+1=25
25/5=5


N=6
N-1=5
1x2x3x4x5=120
120+1=121
121/6=20.1666666666667


N=7
N-1=6
1x2x3x4x5x6=720
720+1=721
721/7=103


N=8
N-1=7
1x2x3x4x5x6x7=5,040
5,040+1=5,041
5,041/8=630.125

N=9
N-1=8
1x2x3x4x5x6x7x8=40,320
40,320+1=40,321
40,321/9=4480.11111111111

N=10
N-1=9
1x2x3x4x5x6x7x8x9=362,880
362,880+1=362,881
362,881/10=36288.1


N=11
N-1=10
1x2x3x4x5x6x7x8x9x10=3,628,800
3,628,800+1=3,628,801
3,628,801/11=329891


N=12
N-1=11
1x2x3x4x5x6x7x8x9x10x11=39,916,800
39,916,800+1=39,916,801
39,916,801/12=3326400.08333333


N=13
N-1=12
1x2x3x4x5x6x7x8x9x10x11x12=479,001,600
479,001,600+1=479,001,601
479,001,601/13=36846277


N=14
N-1=13
1x2x3x4x5x6x7x8x9x10x11x12x13=6,227,020,800
6,227,020,800+1=6,227,020,801
6,227,020,801/14=444787200.071429

N=15
N-1=14
1x2x3x4x5x6x7x8x9x10x11x12x13x14=87,178,291,200
87,178,291,200+1=87,178,291,201
87,178,291,201/15=5811886080.06667

N=16
N-1=15
1x2x3x4x5x6x7x8x9x10x11x12x13x14x15=1,307,674,368,000
1,307,674,368,000+1=1,307,674,368,001
1,307,674,368,001/16=81729648000.0625


N=17
N-1=16
1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16=20,922,789,888,000
20,922,789,888,000+1=20,922,789,888,001
20,922,789,888,001/17=1230752346353


N=18
N-1=17
1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17 = 355,687,428,096,000
355,687,428,096,000+1=355,687,428,096,001
355,687,428,096,001/18=19760412672000.1


N=19
N-1=18
1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18 = 6,402,373,705,728,000
6,402,373,705,728,000+1=6,402,373,705,728,001
6,402,373,705,728,001/19=336967037143579


Sergio

Vidim, da te impresionira tale finta. Tud mene.

:D
Man muss immer generalisieren - Carl Jacobi

McHusch ::

Uuu, Thomas, dobra finta tole. Morda veš kdo se jo je spomnil oz. kako so jo odkrili?

jRk0 ::

kul tehnika ja.
ampak je problem da majo zdaj ze res tako gromozanska prastevila da je hudic to iskat:)

mislim da so tudi neke veeelike denarne nagrade za cloveka, ki odkrije naslednje najvecje prastevilo...


pa ta beseda se pise skupaj. prastevila in ne pra stevila. predpono samo dodas...
You fuck up once, you loose two teeth.

Sergio ::

Thomas: to so bile neke osmorazredne finte. S Primozem sva se nekaj igrala, tako da je v Delphiju spisal program, ki je iskal vsa praštevila od 1 do 4 mrd ter jih zapisoval v neko datoteko. Dost dobra zadeva, delovala ko hudič na Celeronu 266. Sem žrtvoval cel gigabajt (leta 1998 je bilo to VELIKO) diska za vsa praštevila do 4 mrd. Malo me nostalgija daje, kaj naj rečem :D.
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.

Thomas ::

Tale fascinacija s praštevili je zanimiva. Jest sem 15 let nazaj shecal svojo punco, da mi je seštrikala pulover, ki je označeval praštevila do 1000.

:)
Man muss immer generalisieren - Carl Jacobi

Sergio ::

auč. :D

resnično upam, da je ta punca sedaj tvoja žena. :D
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.

Thomas ::

McHusch

To je Wilsonov theorem. Da je število praštevilo tedaj in le tedaj, ko deli faktorel svojega predhodnika plus 1.

Link.


Sergio

Jasno, s taprvo, ki je bla sposobna seštrikat pulover v obliki Eratostenovega sita sem se oženu.

Istega sita, ki sta ga vidva s Primožem rabila za določitev praštevil do 232.


;)
Man muss immer generalisieren - Carl Jacobi

Marjan ::

Heee, hudo :D >:D

To gre definitivno na mojo steno!

Jasno, s taprvo, ki je bla sposobna seštrikat pulover v obliki Eratostenovega sita sem se oženu.

Car si, Thomas!
:)) :)) :))

tx-z ::

Thomas,,sj sm napisu, sam si mislu, da zračuni to število :) :) 14let sm :D , Sergio, a maš še kje ta program, al pa original zapis?,, sj zdj to razumm
tx-z

Zgodovina sprememb…

  • spremenilo: tx-z ()

CHAOS ::

Thomas vprašanje zate:

The 2002 Nevanlinna Prize -> Madhu Sudan

Dobil je nagrado za nov algoritem v iskanju praštevil.

Ker sem to zgolj slišal, me zanima, če lahko poveš kaj več o tem (o algoritmu)?


:D

PS. Sem poskusil poiskate v googlu pa na žalost ne ločim trave od plevela. Tako, da je iskanje splavalo po vodi.

'They have computers, and they may have other weapons of mass destruction.'

Zgodovina sprememb…

  • spremenil: CHAOS ()

Thomas ::

Kolikor sem (doslej) razumel, se zdaj v matematiki koncentrirajo na naslednje. Pocukajo neko korenino, ki štrli iz Zemlje v Sloveniji - in gledajo kateri evkaliptus v Avstraliji se bo zamajal.

Biologija na Zemlji sicer ni tako povezana, toda matematični aksiomi po različnih teorijah - začuda so!

Zadnji, najbolj slavni primer je povezanost sugeirana v Taniyama-Shimura domnevi, o sorodnosti med števili in eliptičnimi funkcijami. To je rešilo prej 300 let nerešen problem. Z dokazom te domneve++.

Kje vse ven silijo praštevila, oziroma bolj korektno rečeno, kaj vse je v ozki povezanosti z njimi, je zdaj nek tak hit, ki prinaša "Nobelove nagrade" za matematiko.

Sudan jo je fasal za to. Za cukanje takoimenovanega zlatega teorema.

Se bom jutri potrudil napisati nekaj bolj konkretnega o tem.

:)





Man muss immer generalisieren - Carl Jacobi

P_Nut ::

najvecje prastevilo ki so ga odkrili je blo 2^832455 - 1. Neki tazga, ne vem če je čist točn. Kul a ne.?

Thomas ::

Ne ni.

Največje poznano praštevilo je:

213,466,917-1

:)
Man muss immer generalisieren - Carl Jacobi

P_Nut ::

jst sm v VB-ju napisau program v katerga upises cifro in ti napiše če je praštevilo s to kodo, če zna kdo prebrat

Dim y As Double, x As Double, z As Double, rez As Double
x = Text1.Text
y = 1
For i = 1 To x - 1
y = y * i
Next i
Text2.Text = y
z = y + 1
rez = z Mod x
Text3.Text = rez
If rez = 0 Then
Label1.Caption = "To JE praštevilo"
Else
Label1.Caption = "To ni praštevilo"
End If

edina slabost je da ne mors računat s števili večjimi kot okoli 100.

mogoče kdo ve kako bi naredu, da bi mi delalo za vsa števila oz. vsaj do 1000?

P_Nut ::

Thomas : kdaj so ga pa odkril?

Thomas ::

Lani. 2001.

:)

See?
Man muss immer generalisieren - Carl Jacobi

P_Nut ::

Thomas : od kje ti veš toliko stvari in linkov. fak. 8-O

Thomas ::

Guglmajstr. :D
Man muss immer generalisieren - Carl Jacobi

P_Nut ::

:)

tx-z ::

ej P_Nut , a mi lah na mail pošleš original *vbp al krkol maš, bom pogledu če se bom kej znajdu:) ,, mogoče bom js odkril nov algoritm, k nam mogu zaspat, sm že par stvari ugotovu sam, problem je bil edin, k je blo to že zdavnej znano :) , sm mislu da je največje praštevilo mal manjše npr. okol 1 miljarde, pa je očitno večje :) ,pa P_Nut če se ti bo dal, da ti nav treba gledat posebi maila: zigamakuc@hotmail.com
tx-z

CHAOS ::

Thomas: še vedno čakam na tvoj odgovor? :D
'They have computers, and they may have other weapons of mass destruction.'

Thomas ::

CHAOS - I'll do my best!

6. avgusta letos so Agrawal, Kayal in Saxena iz indijskega inštituta za tehnologijo v Kanpurju, objavili nov algoritem za določanje tega, če je število praštevilo ali ne.

Posebnost tega algoritma je v tem, da je njegova časovna odvisnost teoretično sorazmerna z dvanajsto potenco logaritma iz števla. V praksi se pa izkaže, da le s šesto.

Če bi pa dokazali še nekaj dodatnih izrekov, ki jih imajo že na ponku, bi bila koračna odvisnost algoritma sorazmerna s tretjo potenco logaritma iz števila.

Kar je daleč bolje kot formula, ki sem jo navedel više zgoraj, kjer je koračna odvisnost transpolinomska - NP.

Algoritem:

if N = ab output COMPOSITE

r=2

while (r < n) {

    if ( gcd(n,r) != 1 ) output COMPOSITE // gdc je največji skupni deljitelj

    if (r is prime) let q be the largest prime factor of r-1

    if ((q > 4*sqrt(r)*log(n)) and (n(r-1)/q) != 1 mod r) break;



    r=r+1;


}

for a=1 to 2*sqrt(r)*log(n)


    if (x - a)n != (x - a)*((xr-1 mod n) output COMPOSITE


output PRIME;


End of algoritem.

Zdej hec je v tem, da se tisti break v while zanki relativno zelo hitro zgodi in da mora steči samo še spodnja zanka, ki teče do zgoraj v while zanki izračunanega r.

Vse skupaj pa temelji na probabilističnem testiranju števil za praštevila, v katerega se uspešno poglablja Mr. Sudan.



Any questions, anybody?

:)
Man muss immer generalisieren - Carl Jacobi

DavidJ ::

Ja! :)

Kaj naredita tale 2 stavka:

if (r is prime) let q be the largest prime factor of r-1

if ((q > 4*sqrt(r)*log(n)) and (n(r-1)/q) != 1 mod r) break;


In tole:

for a=1 to 2*sqrt(r)*log(n)
if (x - a)n != (x - a)*((xr-1 mod n) output COMPOSITE
output PRIME;

Mogoče je kr brezvezno vprašanje, samo nisem tolk v programiranju, da bi lahko tole razumel. :)
"Do, or do not. There is no 'try'. "
- Yoda ('The Empire Strikes Back')

Thomas ::

To je algoritem, ni ravno program. Program rabi več vrstic.

> if (r is prime) let q be the largest prime factor of r-1

Če je r=101 potem naj bo q enak 5. Torej največje praštevilo, ki deli 100.

To je treba zračunat s programom.

Potem pa preveriti pogoj:

> if ((q > 4*sqrt(r)*log(n)) and (n(r-1)/q) != 1 mod r) break;

Če je izpolnjeno, smo iz while zanke že ven.

V tazadnji for zanki, pa mora x izpolniti vse vrednosti do a.

V bistvu je dvojna for zanka v programu. Za algoritem je dosti napisano.

Bom mogoče napisal še točen program. Samo komu ne bo toliko razumljiv kot je tole.



:)

Man muss immer generalisieren - Carl Jacobi

Thomas ::

Ja programa ne bom še napisal, mi pobere cel dan.

Recimo poglejmo tole vrstico algoritma, kakšen subprogram zahteva.

> if N = ab output COMPOSITE

b=2;
While (b<=ln2(N)){
a=N^(1/b);
if a^b=N {oututput COMPOSITE; break;}
b++;
}

Pa tko naprej ...
Man muss immer generalisieren - Carl Jacobi

Simko ::

Thomas:
Funkcija je:

F(N) = Signum(((N-1)!+1) mod N)

Signum od 0 je 0, od večjih števil pa 1.

Za praštevila da F(N) = 0. Za ostale da 1.

F(5)=Signum(((5-1)!+1) mod 5)

To je 0, torej 5 je praševilo.


Saj funkcije Signum sploh ne potrebujemo. Lahko napišem:
F(N) = ((N-1)!+1) mod N

potem pa:
if(F(N) = 0) then
N je praštevilo
else
N ni praštevilo

Torej: Za praštevila da F(N) = 0. Za ostale da != 0.

P.S.: Tvoj trenutni podpis mi je zlo všeč! :)

Thomas ::

Res je Simko - lahko uporabiš kar mod - pa je ravno tako dobro.


Kar se pa podpisa tiče - nekaterim gre še bolj na jetra, kot vam je drugim všeč. Namen je obojestransko dosežen. >:D
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Čist tko me zanima - a je kdo kej imel od tegale?

Kaj če do konca napišem progija za določevanje sestavljenosti?

Ga bodo bwane gor uzele? Ga bo ljudstvo dol jemalo?

:\
Man muss immer generalisieren - Carl Jacobi

tx-z ::

kaj je bwane???
če mislš od tega foruma, ja smo kr neki zvedl (no vsaj js :) )
zard mene lah nardiš,, kaj mislš s tem določanje sestavljenosti?
tx-z

Thomas ::

Ja po zgornjem algoritmu bom napisal program, za hitro določevanje, če je število pra ali ni pra.

Pol pa, kdor si ga bo hotu, ga bo lahko dol vzel iz slotecha. Če na slotechu bo, seveda.

:)

Man muss immer generalisieren - Carl Jacobi

tx-z ::

no, če boš mel pa še kakšo urco odveč pa dodej programu možnost, da ti kaže kok časa bo še rabu da ti pove a je praštevilo al ni (za mal večja števila :) ) -če jih bo podpiru
tx-z

CHAOS ::

Jaz nestrpno pričakujem source. :D
'They have computers, and they may have other weapons of mass destruction.'
«
1
2


Vredno ogleda ...

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

Python

Oddelek: Programiranje
202408 (1094) d_DJ
»

matematika-zaporedja (strani: 1 2 )

Oddelek: Šola
564804 (3640) lebdim
»

Casovna kompleksnost algoritma

Oddelek: Programiranje
71146 (901) lebdim
»

Random

Oddelek: Znanost in tehnologija
434084 (3314) Thomas
»

Neskončno... (strani: 1 2 )

Oddelek: Loža
616144 (5058) Gh0st

Več podobnih tem