Meddig kell szitálni, hogy kb ugyanannyi összetett szám maradjon mint prím?

Ha erre analitikus választ keresel, akkor az nehéz ügy, bár biztos van irodalma.

Az alapötlet: a szita minden p_i eleme a megmaradó számok 1/p_i-ed részét szűri ki. Ha q-ig szitázol, azzal a természetes számok r = (1-1/2)(1-1/3)(1-1/5)...(1-1/q)-ed részét hagyod bent. Az n magasságban található prímek sűrűsége ~1/log(n), tehát addig a q-ig kell menni, amire r = 2/log(n).

Az a baj, hogy ezt az r produktumot nehéz kezelni. Amit ilyenkor csinálni lehet, hogy r = produktum(akármi) helyett r = e^szumma(log(akármi)) átalakítást csinálsz, ahol a szummázott elemeid log(1-1/p_i) alakúak, és p-re indextől függő becslést adsz. A prímszámtétel alapján i*log(i) vagy még jobb i*log(i) - i*(log(log(i))-0.9385)-öt. A szummázást ilyenkor az ember megpróbálja integrálásra cserélni, csak sajnos az x*log(x) + ... függvénynek nincs ismert elemi integrálfüggvénye. Ilyenkor vagy utánanézel, hogy van-e legalább alsó-felső korlát becslés rá, vagy numerikusan folytatod.

Én most numerikusan folytatom. A példádhoz r = 2/log(10^18) = 0.04825 kell, ami átírva e^-3.031. Az első ezer prímet egy gyors guglival letöltöm, és egzaktul számolom rájuk a log(1-1/p) szummát, ami -2.773. Efelett meg jó lesz a p_i = i*(log(log(i))-0.9385) becslés, és az jön ki, hogy a hiányzó -0.258-at további kb. tízezer elem adja ki:

[link]

Az első 11 ezer prímmel szitázva tehát a 10^18 köré eső túlélők fele lesz prím, fele összetett szám. Hogy ez általánosítva, f(n) formában hogy nézhez ki, elképzelésem sincs.

Jól számoltad, és nyilván nem véletlen egybeesés: a linkelt kérdésben annó rájöttünk hogy meddig kell elmenni, hogy a kívánt arányt elérjük, ebbe már csak be kell helyettesíteni az általad most kívánt 2/log(n)-t és jó lesz.

Mint látható, ugyanaz jön ki: ha az #1-t finomítod a Wolfram Alphában hogy pontosan -0.258 legyen az integrál, kijön hogy a 10660-es prímindexig kell elmenni, ami 112429. Az e^(0.56145/(2/ln(10^18))) értéke pedig 112992, ami pár ezreléknyire van csak tőle.