Prím-szakértő, segítenél? Ha veszek egy véletlen számot 2^64 közelében akkor az mekkora valószínűséggel prím?
Mekkora valószínűséggel prím, ha tudjuk, hogy nincs osztója 64-ig, 256-ig, 1024-ig, 2^n-ig?
Egy képletet esetleg, ha van, köszi!
válasza:Valószínűsége = prím számok számossága / összes figyelembe vett szám számossága.
Néhány nem diszjunkt halmaz, amit figyelembe lehet venni ilyenkor:
- a^2 - b^2 = (a - b)(a + b), tehát a negatív irányba négyzet szám távolságra lévők biztos nem prímek.
- minden páros nem prím
- minden addigi "prím számadik" szám nem prím (3., 5., 7., ...)
Numerikus megoldással, egy szám prím tulajdonságát a gyögy(szám)-nál kisebb számok szorzatára próbálunk osztót keresni hozzá. Ez a legprimitívebb módszer, ami könnyen programozható. Tehát 2^32 számot vizsgálnánk meg, hogy kiderüljön prím-e egy 2^64 körüli szám.
2^n -ig könnyen megszámolható, mennyi prím szám van.
n = 32-ig nincs osztója, akkor valószínű prím
többi n esetén Kérdés, hogy 2^32-ig mennyi (nem)prím szám van és 2^n-ig mennyi (nem)prím szám van. Ezek számosságából lehetne okoskodni.
Én arra gondoltam, hogy ha veszek egy véletlen számot 2^64 közelében akkor annak a valószínűsége hogy prím:
kb. 1 / ln(2^64) = 0,02254
De, ha tudom, hogy nem osztható 2-vel, sem 3-mal, akkor kiesik a számok 2/3-a, ezért 3* akkora a valószínűség.
És, ha tudom, hogy nem osztható 5-tel, sem 7-tel, akkor kiesik a maradék 1/5-e, majd a maradék 1/7-e, az
eredeti számok 22,86%-a marad, ezért 4,5* akkora a valószínűség, stb.
Ez kellene képletszerűen ha tudjuk, hogy nincs osztója 64-ig, 256-ig, 1024-ig, stb.
válasza:
válasza:A prímszámtétel szerint egy adott x számig "kb" x/ln(x) darab prímszám van, ahol ln a természetes alapú logaritmus.
Ez a képlet csak aszimptotikusan igaz, tehát minél nagyobb x-eket mondasz, akkor a képlet egyre jobban közelíti a prímek számát addig az x-ig.
A képlet a gyakorlatban tehát nagyon nagy számokra lesz csak pontos. Minél nagyobb pontosság kell, annál nagyobb számok lesznek csak használhatóak.
Ezt úgy is mondjuk, hogy a prímszámszámláló függvény és az x/ln(x) hányadosának határértéke 1. :)
Szerencsére neked egy jó nagy számod van, ezért ez a függvény kb igaz lesz annak a környékén.
Ebből kiesik, hogy a valószínűséged 1/ln(x). 2^64 esetében ez kb. 0.0225, tehát nagyjából minden ötvenedik szám prímszám arrafelé.
Ha tutira akarsz menni nagy prímekkel, akkor osztáspróbák helyett hazsználj sztochasztikus teszteket, pl. a Miller-Rabin prímtesztet ( [link]
A prímszámok számával, átlagos sűrűségével tisztában vagyok.
"A prímszámtétel szerint egy adott x számig "kb" x/ln(x) darab prímszám van..."
Ez elég pontatlan, az n=x/(ln(x)-1) ill. n=x/(ln(x)-1-1/ln(x)) ill. Li(x) sokkal pontosabbak, és a
" veszek egy véletlen számot x közelében akkor annak a valószínűsége hogy prím: kb. 1 / ln(x)" pontos.
Ismerem a Miller-Rabin prímtesztet, BPSW tesztet, de most nem ezek érdekelnek, hanem hogy mennyi "csak nagy osztójú"
szám van, pl. a legkisebb osztója 2^31...2^32 között, 2^30...2^31 között, stb van. Ez segítene.
Tulajdonképpen egy olyan függvényt, görbét szeretnék ami leírja a valószínűség növekedését(próbaosztás) - a sikertelen prímosztók növekedésével.
1 / ln(N) -nél kezdődik, és gyök(N)-nél 1.
#3: "tehát azokat, amelyek nem oszthatóak 14-el, 21-el vagy 35-el"
Nem igazán értem: ezek már kiestek, mert oszthatóak voltak 2-vel, 3-mal, 5-tel, tehát a "maradék"-ban nem játszanak.
válasza:#3 vagyok, igazad van.
Amikor írtam a választ, akkor összekevertem a maradékot az összessel (fáradt voltam...)
Igen, van egy elméletem a két nagy osztóval rendelkező számok arányára/dbszámára, de kellene egy matematikus
vagy egy programozó, az elméletem bizonyítására (cáfolására).
Szerintem:
Érdekes következtetés: 2^n környékén, a számok 1/n részének van két nagy, a köbgyökénél nagyobb osztója.
2^64 környékén, a számok 0,14%-ának van két nagy, a köbgyökénél nagyobb osztója, a kisebbik 2^31...2^32.
Majdnem ua. 2^30...2^31 és 2^29...2^30 között.
Ha igaz az elméletem...
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!