Eratoszthenész szitája: mekkora p-ig kell elmenni, hogy a számok 1%-a maradjon meg?
Eratoszthenész szitáját alkalmazzuk egy nagyon nagy n-ig (n->végtelen):
Kihúzzuk a számok közül minden 2., 3., 5., 7., 11., ... p-edik számot.
Addig folytatjuk, amíg már csak a számok 1%-a marad meg (n/100 db).
Lefuttattam egy programot ami prod (1 - 1/p_i) -t számolja:
(1-1/2)*(1-1/3)*(1-1/5)**(1-1/7)*(1-1/11)*...*(1-1/p) = arány
és tényleg azt hozta ki, amit írtam. (Szóval semmi szép eredmény.)
arány ; tényleges arány ; p ; p^arány
0.050 , 0.049999598146088 , 75037 , 1.75292677
0.049 , 0.048999985363708 , 94351 , 1.75292195
0.048 , 0.047999955045051 , 119981 , 1.75306250
0.047 , 0.046999931190586 , 153649 , 1.75293938
0.046 , 0.045999851474745 , 199483 , 1.75305552
0.045 , 0.044999853985406 , 261791 , 1.75310514
0.044 , 0.043999884825558 , 347443 , 1.75306846
0.043 , 0.042999998480360 , 468067 , 1.75316683
0.042 , 0.041999956271394 , 638567 , 1.75314837
0.041 , 0.040999983768324 , 884537 , 1.75313498
0.040 , 0.039999974176138 , 1246379 , 1.75317797
0.039 , 0.038999987943570 , 1786831 , 1.75319917
0.038 , 0.037999987944659 , 2609777 , 1.75319785
0.037 , 0.036999996383157 , 3890743 , 1.75319896
0.036 , 0.035999994069233 , 5930923 , 1.75320380
0.035 , 0.034999999010487 , 9261089 , 1.75320690
0.034 , 0.033999997903421 , 14845487 , 1.75321110
0.033 , 0.032999999512210 , 24488437 , 1.75321717
0.032 , 0.031999999672540 , 41677261 , 1.75322144
0.031 , 0.030999999787978 , 73401271 , 1.75322159
0.030 , 0.029999999986618 , 134253593 , 1.75322550
0.029 , 0.028999999956412 , 255975793 , 1.75322546
0.028 , 0.027999999996392 , 511112981 , 1.75322831
0.027 , 0.026999999989901 , 1074112321 , 1.75322777
0.026 , 0.025999999998754 , 2390040803 , 1.75322857
#10:"Az lenne a korrekt ha p értékének meghatározása mellett n-t is megmondanánk hozzá."
Ezt írtam: "egy nagyon nagy n-ig (n->végtelen)", meg hogy összetettek is maradnak.
De legyen konkrétan e^1000000 (vagy googolplex=10^10^100, ez tényleg majdnem mindegy,)
tehát nem csak e^100-ig nézzük, hanem sokkal-sokkal tovább.
válasza:#10: A kérdező által felvetett probléma egzakt módon: mely legkisebb p_n prímszámra teljesül, hogy
produktum_i=1..n (1 - 1/p_i) <= x [ahol x az eredeti kérdés szerint 0.01, de mostanra már a kérdezőt is az általános x érdekli]
A produktum Erasztoszthenész szitájának működési elvét tükrözi. Első lépésben kiszórja a természetes számok felét. Második lépésben kiszórja a maradék harmadát. Harmadik lépésben kiszórja a maradék ötödét, és így tovább.
n lépés után a ki nem szitált természetes számok aránya:
1/2 * 2/3 * 4/5 * ... * (1 - 1/p_n), azaz a fenti produktumos kifejezés.
Mi ezt először megpróbáltuk úgy megközelíteni, hogy milyen n (vagy p_n) tájékán lesz x a prímszámok aránya (hiszen azok végsősoron Erasztothenész szitája révén keletkeznek), de aztán a kisebb-nagyobb javításaink ellenére se tudtunk épkézláb, a valós helyzetet tükröző becslést adni rá.
Elég sanszosnak tűnik, hogy egy p_n = e^(c/x) jellegű becslés lesz a nyerő, de c-re eddig nem tudtunk választ adni: eleinte mindketten 1-et mondtunk, aztán a gyökös észrevétel után 1/2-et, de a kérdező által empirikusan becsült érték eközben elég stabilan 0.5615-nek mutatkozott. És egyelőre még nem fejtettük meg, hogy miért.
Ilyenkor szokott jönni az, hogy megpróbáljuk kiszámolni minél több jegyig, megnézzük hogy előállítható-e más, nevezetes számokból, stb. És akkor kiderül, hogy a kérdező nagyon is jó úton járt: a szám nem más mint e^-gamma ahol gamma az Euler-Mascheroni-konstans. Végül kiderül, hogy sajnos ma se találtuk fel a spanyolviaszt:
De legalább végre megvan a megoldás!
Kapcsolódó kérdések:
Minden jog fenntartva © 2025, 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!