Kezdőoldal » Tudományok » Természettudományok » Prím-szakértő, segítenél? Ha...

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?

Figyelt kérdés

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!



2013. nov. 23. 11:38
 1/9 anonim ***** 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.

2013. nov. 23. 12:32
Hasznos számodra ez a válasz?
 2/9 A kérdező kommentje:

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

2013. nov. 23. 15:09
 3/9 anonim ***** válasza:
A maradéknak nem esik ki az 1/7-e, mert amikor elveszed a 7-el osztható számokat, akkor csak azokat veszed el, amiket eddig még nem vettél el (tehát azokat, amelyek nem oszthatóak 14-el, 21-el vagy 35-el). Hasonló igaz az 5-el és a 3-al oszthatóakra.
2013. nov. 24. 00:51
Hasznos számodra ez a válasz?
 4/9 cli_hlt ***** 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]

2013. nov. 24. 01:27
Hasznos számodra ez a válasz?
 5/9 A kérdező kommentje:

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.

2013. nov. 24. 13:55
 6/9 A kérdező kommentje:

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

2013. nov. 24. 14:01
 7/9 anonim ***** válasza:

#3 vagyok, igazad van.

Amikor írtam a választ, akkor összekevertem a maradékot az összessel (fáradt voltam...)

2013. nov. 24. 14:13
Hasznos számodra ez a válasz?
 8/9 anonim ***** válasza:
Sikerült valahova jutni vele?
2013. dec. 8. 23:25
Hasznos számodra ez a válasz?
 9/9 A kérdező kommentje:

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:

[link]

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

2013. dec. 9. 15:07

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

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!