Milyen hosszú prímszám létezhet az alábbi algoritmussal?
Veszel egy kétjegyű prímet, és mindig 2-2 számjegyet mögé írsz, úgy, hogy a keletkezett 4,6,8,10, ... számjegyű számok mindegyike prím legyen.
Maximum milyen hosszig sikerülhet elmenni?
Pl.: 1103112107212303030967593141912181236103
11, 1103, 110311, 11031121, 1103112107, ... is prím.
Nem feladat, csak úgy eszembe jutott.
De azért van egy elméletem ezzel kapcsolatban.
Kétjegyű prímből 21 db van, ezekből a fentieknek megfelelően 224 db 4-jegyű készíthető, amelyekből 1749 db 6-jegyű, stb.
A sokszorozódás egyre kisebb, és szerintem kb. a 44-jegyűeknél éri el a csúcsát, ahol átlag minden 100. szám prím: 100/ln(5e43)=0.994
Innentől kezdve csökken a megfelelő 46,48,50, stb. jegyű megfelelő prímek száma, és 88-jegyű már kb. fele annyi, mint a 86-jegyű, 132-jegyű már kb. harmada annyi, mint a 130-jegyű.
Ezekből úgy saccolom kb. 150 hosszú körül lehet a leghosszabb.
válasza:A prímszámtétel szerint 1...n számok között kb. n/ln(n) db prím van. Annak a valószínűsége, hogy
- az első 100 számból 1-et kiválasztva prímet kapunk, kb. 1/ln(n)=1/4,6
- az első 10000 számból 1-et kiválasztva prímet kapunk, kb. 1/ln(100^2)=1/2*4,6
- az első 100^n számból 1-et kiválasztva prímet kapunk, kb. 1/ln(100^n)=1/n*4,6.
A keresett számnál ezeknek egyszerre kell teljesülnie. A jó kiválasztás valószínűsége 1/(4.6^n*n!).
100^n számból választhatunk, ezért várhatóan 100^n/(4.6^n*n!)=21,7^n/n! jó számunk lesz.
21,7^n/n!~1, ha n=56. (wolframalpha.com) A számjegyek száma 112. Ebben a környezetben, ha n 1-el nő, akkor a várható érték kb. 2,6-szor csökken. Hogy ennek alapján mikor mondhatjuk, hogy nem lesz nagyobb szám, az kérdéses. Pl. 118 jegyű szám csak 0,05 valószínűséggel lesz.
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
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!