A nagy számok (pl 19-20 jegyű) között melyik a több: a prímek száma, vagy a csak 2 nagy osztóval rendelkezőké? Folyt.

Természetes, hogy azok is ritkábbak, hisz a prímek szorzatából jönnek.

A számuk nagyon attól függ, hogyan definiálod azt, hogy "nagy osztó". Ha nem teszünk kikötést, szóval lehet kis osztó is, akkor Landaunak van egy érdekes eredménye a legfeljebb k-majdnem prímek számáról mondjuk ennek a lapnak az alján:

[link]

E szerint a legfeljebb félprímek száma:

π₂(n) ≈ (n / ln n) · ln ln n

Ez persze nem csak a nagy osztójú félprímeket tartalmazza, hanem a kis prímek is lehetnek az osztói akár a sokadik hatványon is, illetve ebben a prímek is benne vannak.

De nem ezt kérdezted. Ha mondjuk a 2^62 és 2^64 közötti félprímeket nézzük, amiknek a prímtényezői 2^21-nél nagyobbak, akkor összeszámolhatjuk a közelítéseket mondjuk úgy, hogy vesszük a 2^21 és 2^22 közötti prímeket és megszorozzuk a 2^41 és 2^42 közöttiekkel. Így biztos, hogy félprímet kapunk, ráadásul a kívánt tartományban.

Ezt meg kell ismételnünk 2^22..2^23 és 2^40..2^41 közötti prímekkel is, és így tovább.

Írtam rá programot, ami egy olyan szubrutinon alapul, ami megbecsüli a 2^n és 2^(n+1) közötti prímek számát a prímszámtétel alapján. Ez jött ki:

Prímek száma 2^62 és 2^64 között: 3.085179e+17

Félprímek száma:

2^21*2^41 és 2^22*2^42 között: 1.309762e+05 * 7.369384e+10 = 9.652141e+15

2^22*2^40 és 2^23*2^41 között: 2.511327e+05 * 3.772204e+10 = 9.473236e+15

2^23*2^39 és 2^24*2^40 között: 4.823342e+05 * 1.931983e+10 = 9.318616e+15

2^24*2^38 és 2^25*2^39 között: 9.278356e+05 * 9.900745e+09 = 9.186264e+15

2^25*2^37 és 2^26*2^38 között: 1.787402e+06 * 5.076934e+09 = 9.074524e+15

2^26*2^36 és 2^27*2^37 között: 3.447921e+06 * 2.605063e+09 = 8.982051e+15

2^27*2^35 és 2^28*2^36 között: 6.659413e+06 * 1.337620e+09 = 8.907765e+15

2^28*2^34 és 2^29*2^35 között: 1.287722e+07 * 6.873238e+08 = 8.850820e+15

2^29*2^33 és 2^30*2^34 között: 2.492776e+07 * 3.534447e+08 = 8.810584e+15

2^30*2^32 és 2^31*2^33 között: 4.830471e+07 * 1.818998e+08 = 8.786616e+15

2^31*2^31 és 2^32*2^32 között: 9.369448e+07 * 9.369448e+07 = 8.778655e+15

Félprímek száma 2^62 és 2^64 között összesen: 9.982127e+16

Szóval nagyjából harmadannyi nagy-osztójú félprím van a tartományban, mint prím.

Átírtam úgy, hogy 2^n és 2^(n+Δ) az egyik tartomány, a másik pedig 2^(62-n) és 2^(64-n-Δ).

A tegnapi táblázatom Δ=1-nek felelt meg, azzal kb. 10^17 volt a félprímek száma.

Most próbáltam Δ=1/2, 1/4, 1/8 stb. értékekkel egészen 1/1024-ig. Ahogy finomodott a felosztás, úgy nőtt a kiírt félprímek száma (egyre kisebb mértékben), 1.88·10^17 körül lehet a határérték.

Érdekes, hogy a 2^Δ "széles" és a 2^(2-Δ) "széles" tartományban lévő prímek számának a szorzata közel állandó n értékétől függetlenül (10%-on belüli a változás). Ez a tegnapi táblázatban is látszik.

[A "szélesség" persze nem szélesség, pl. a kisebbik tartomány valódi szélessége nem 2^Δ, hanem 2^n ·(2^Δ - 1).]

A legjobb persze az lenne, ha nem egy 2^Δ "széles" tartományra, hanem minden egyes p prímre számolnánk ki a prímek számát a 2^62/p és 2^64/p közötti tartományban, és ezeket szummáznánk.