Výpočet pravdepodobnosti náhodného výberu prvočísla

ROBERT BROOK / Getty Images

Teória čísel je odvetvím matematiky ktorý sa zaoberá množinou celých čísel. Trochu sa tým obmedzujeme, pretože priamo neštudujeme iné čísla, ako napríklad iracionálne. Avšak, iné typy reálne čísla sa používajú. Okrem toho má predmet pravdepodobnosti mnoho súvislostí a priesečníkov s teóriou čísel. Jedno z týchto spojení súvisí s distribúciou základné čísla. Konkrétnejšie sa môžeme opýtať, aká je pravdepodobnosť, že náhodne vybrané celé číslo od 1 do X je prvočíslo?

Predpoklady a definície

Ako pri každom matematickom probléme, je dôležité pochopiť nielen to, aké predpoklady sa vytvárajú, ale aj definície všetkých kľúčových pojmov v probléme. Pre tento problém uvažujeme kladné celé čísla, teda celé čísla 1, 2, 3, . . . do nejakého čísla X . Náhodne vyberáme jedno z týchto čísel, čiže všetky X z nich je rovnako pravdepodobné, že budú vybrané.

Snažíme sa určiť pravdepodobnosť, že sa vyberie prvočíslo. Preto musíme pochopiť definíciu prvočísla. Prvočíslo je kladné celé číslo, ktoré má práve dva faktory. To znamená, že jedinými deliteľmi prvočísel sú jedna a samotné číslo. Takže 2,3 a 5 sú prvočísla, ale 4, 8 a 12 nie sú prvočísla. Poznamenávame, že pretože v prvočísle musia byť dva faktory, číslo 1 je nie hlavný.

Riešenie pre nízke čísla

Riešenie tohto problému je pre nízke čísla jednoduché X . Všetko, čo musíme urobiť, je jednoducho spočítať čísla prvočísiel, ktoré sú menšie alebo rovné X . Počet prvočísel delíme menším alebo rovným X podľa čísla X .

Napríklad na nájdenie pravdepodobnosti, že je prvočíslo vybrané od 1 do 10, je potrebné vydeliť počet prvočísel od 1 do 10 10. Čísla 2, 3, 5, 7 sú prvočísla, takže pravdepodobnosť, že prvočíslo je vybrané je 4/10 = 40 %.

Pravdepodobnosť, že sa vyberie prvočíslo od 1 do 50, sa dá nájsť podobným spôsobom. Prvočísla, ktoré sú menšie ako 50, sú: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 a 47. Existuje 15 prvočísiel menších alebo rovných 50. Pravdepodobnosť, že sa náhodne vyberie prvočíslo, je teda 15/50 = 30 %.

Tento proces možno vykonať jednoduchým počítaním prvočísel, pokiaľ máme zoznam prvočísiel. Napríklad, existuje 25 prvočísel menších alebo rovných 100. (Pravdepodobnosť, že náhodne zvolené číslo od 1 do 100 je prvočíslo, je teda 25/100 = 25 %.) Ak však nemáme zoznam prvočísel, môže byť výpočtovo náročné určiť množinu prvočísel, ktoré sú menšie alebo rovné danému číslu X .

Veta o prvom čísle

Ak nemáte počet prvočísel, ktoré sú menšie alebo rovné X , potom existuje alternatívny spôsob riešenia tohto problému. Riešenie zahŕňa matematický výsledok známy ako teorém o prvočísle. Toto je vyhlásenie o celkovom rozložení prvočísel a môže sa použiť na aproximáciu pravdepodobnosti, ktorú sa snažíme určiť.

Veta o prvočísle hovorí, že existuje približne X / ln( X ) prvočísla, ktoré sú menšie alebo rovné X . Tu ln( X ) označuje prirodzený logaritmus X , alebo inými slovami logaritmus so základom číslo a . Ako hodnota X zvyšuje aproximácia zlepšuje sa v tom zmysle, že vidíme zníženie relatívnej chyby medzi počtom prvočísel menším ako X a výraz X / ln( X ).

Aplikácia vety o prvom čísle

Výsledok vety o prvočísle môžeme použiť na vyriešenie problému, ktorý sa snažíme riešiť. Podľa vety o prvočísle vieme, že existuje približne X / ln( X ) prvočísla, ktoré sú menšie alebo rovné X . Ďalej je ich celkom X kladné celé čísla menšie alebo rovné X . Preto pravdepodobnosť, že náhodne vybrané číslo v tomto rozsahu je prvočíslo, je ( X / ln( X ))/ X = 1 / ln( X ).

Príklad

Teraz môžeme tento výsledok použiť na aproximáciu pravdepodobnosti náhodného výberu prvočísla z prvého miliardy celé čísla. Vypočítame prirodzený logaritmus miliardy a vidíme, že ln(1 000 000 000) je približne 20,7 a 1/ln(1 000 000 000) je približne 0,0483. Máme teda asi 4,83 % pravdepodobnosť, že náhodne vyberieme prvočíslo z prvej miliardy celých čísel.