Eratoszthenész szitája: mekkora p-ig kell elmenni, hogy a számok 1%-a maradjon meg?

0..n intervallumra ahol n nagy egy közelítés hogy n/(ln(n)-1) prímszám van.

Abból indulok, ki hogy p=n-ig csinálom, így a elegendő akkora n-t mondani.

Ekkor (n/(ln(n)-1))/n=0.001 -> n=e^1001 = 535 520 851 000 460 668 392 062 686 585 732 518 416 341 422 309 750 047 939 536 452 471 019 636 930 731 711 212 810 341 161 044 905 060 039 504 054 404 935 740 604 071 657 734 735 195 049 827 445 614 388 916 273 073 958 997 129 261 803 411 755 503 355 650 644 419 942 931 633 849 256 060 354 627 020 425 858 341 715 198 280 686 417 508 406 958 562 464 922 583 500 057 489 735 941 127 496 868 442 770 993 001 406 061 765 929 217 989 049 131 974 046 346 817 691 949 707 202 023 688 287 777 266 609 044 857 595 767 581 011 524 350 086 661 334 628 898 570 486 560 844 089 710 718 024

Ez nyilván egy közelítő érték.

#1 válasza (bár 1% helyett 0.1%-ra számolta ki) elég jó. Feltéve, hogy a megoldást úgy érti, hogy az akkora prímekig kell elmenni, nem pedig az annyiadik prímig.

Egy nagyon apró, már-már kötözködés szintű részletben lehet csak rajta javítani: (n/(ln(n)-1))/n = 0.01 helyett azt keresd meg, hogy n/(ln(n)-1) deriváltja hol lesz 0.01.

Azért említésre méltó ez a dolog, mert #1 megoldása azt számolja, hogy mekkora n alatt lesz 1% a prímek (azaz szita által el nem trafált számok) aránya, te viszont azt keresed, hogy az összes természetes szám körében (azaz alapvetően n feletti számok körében) mennyit nem trafál el a szita.

Ez utóbbi pedig az n körüli prímek sűrűségével egyenlő. Ami a prímszámláló függvény közelítésének deriváltja.

A különbség egyébként relatíve kicsi: e^101 helyett e^(51+20*gyök(6)) az érték, ami kb. e^100.

Na igen, egy nullával elcsúsztam az egyenlet felírásában.

Miért kéne inkább a deriváltjánál számolni?

Az eredeti kérdés megfogalmazása szerint megengedett az összes nem prím kiszitálása is, ha a kérdéses 1%-ot akkor éri el.

Ott is elcsúsztam, hogy p értékének felső korlátja n négyzetgyöke.

A kérdező azt kérdezi, hogy hány elem után éri el a szita a 99% sűrűséget. Tehát milyen p_i-re lesz produktum (1 - 1/p_i) = 0.01.

És erre a válasz nyilván az a réndzs, ahol a prímszámok sűrűsége épp 0.01 körüli. A prímszámok sűrűsége n körül pedig n/(ln(n)-1) deriváltja. A te megoldásod ugye egy átlagsűrűséget vesz 1 és n között (n-nel osztás), az enyém meg a pontosat n-nél (deriválás). A különbség, mint azt írtam is, elég kicsi (e^101 vs e^100).

Nálam a deriváltja ezt jelenti:

n/(ln(n)-1) d/dn = (log(n)-2)/(log(n)-1)^2

A deriváltja ahol 0.01:

(log(n)-2)/(log(n)-1)^2 = 0.01 =>

n = e^(51-20*sqrt(6)) & n = e^(51+20*sqrt(6))

"Tehát milyen p_i-re lesz produktum (1 - 1/p_i) = 0.01."

Nem igazán értem ezt a produktomos részt.

"A különbség, mint azt írtam is, elég kicsi (e^101 vs e^100)."

Ja csak alig 3x-os.

-Hány éves vagy?

-Áááá nem tudom 30 vagy 90 végül is alig van különbség.

Igazad van, tényleg nem jók a válaszok. Főleg amiatt amit a 89%-os már megjegyzett: az n körül adódó prímek sűrűségéért csak a szita gyök(n)-ig terjedő elemei felelnek. Tehát ezért van az általad illesztett kifejezés kitevőjében egy 0.5 körüli szorzó. De nincs olyan közel 0.5-höz, hogy ennyivel el lehessen intézni: a megközelítés nem az igazi.

Hogy akkurátusan ezt miként lehetne csinálni, azt nem tudom.

Először arra gondoltam, hogy az (1 - 1/p_i) tényezőkben használhatnánk közelítést, pl p_n = n*ln(n) becsléssel. És hátha folytonossá téve kijön valami épkézláb alak:

produktum(...) helyett exp(szumma(ln(...))) átírással, a szummából integrálást csinálva

exp(integrál ln(1-1/(x*ln(x)))dx, x=a..b) az a-adiktól a b-edikig terjedő prímszámok együttes szitaerejének becslése lenne. Az első a-t kiszámolod pontosan (hogy a kis számokra pontatlan közelítés ne zavarjon be annyira) majd afelett a közelítést hozzászorzod. Csakhogy ennek az integrálnak nincs zárt alakja, tehát nem jutottunk előrébb a folytonossá tétellel. Azért leírtam, hátha a gondolatmenetet valami más problémában később használni tudod.

Továbbra sem értem mit jelent a produktum (1 - 1/p_i), itt mit szorzol meddig??

"az n körül adódó prímek sűrűségéért csak a szita gyök(n)-ig terjedő elemei felelnek."

Ezt írj a kérdező : "Kihúzzuk a számok közül minden 2., 3., 5., 7., 11., ... p-edik számot"

Ha n négyzetgyökéig elment a p akkor a szita csakis a prímszámokat tartalmazza, hiszen az összes többszörösét kiszitálta p-nek. Viszont ha a legutolsó p értéknél nem menne végig a szita mert meg van a megfelelő kitöltöttség akkor p értékén hogy meddig kellett elmennie semmit sem befolyásol.

Továbbá meg nem tudom hogy mennyit számít, hogy van e a szitában a triviális optimalizáció. Vagyis, hogy amikor egy adott p összes többszörösét kiszitálta, a következő iterációs sorozatban mindig a sorra következő szám négyzetétől kezdi a szitálást.

Ezen felül nem látom, hogy ne lenne igaz amiket írtunk a javításokkal kompenzálva, hiszen ez akkor következne, ha belátjuk, hogy igaz, hogy egyetlen lehetséges n érték melleti p-re teljesülhet a feltétel. Az lenne a korrekt ha p értékének meghatározása mellett n-t is megmondanánk hozzá.