Test prvočíselnosti
Přihlásit se
Test prvočíselnosti (7/9) · 6:46

Prvočíselná věta: hustota prvočísel Jak můžeme odhadnout počet prvočísel na zadaném intervalu?

Navazuje na Moderní šifrování.
Představte si přirozená čísla uspořádaná do spirály. Prvočísla jsme obarvili na modro a složená čísla ponechali černá. Naskýtá se zajímavá otázka: „Kolik je prvočísel v porovnání se složenými čísly?“ Podívejme se na to nejdříve z širšího pohledu. Povšimněte si, že barva prvočísel je hustá uprostřed, směrem ven postupně řídne, ale nikdy nezmizí docela. Já o tom rád uvažuji takto: Představte si uprostřed nekonečně vysoký strom. Z něj se na zem snášejí listy představující prvočísla a na zemi se nepředvídatelným způsobem usazují: nejhustěji u paty stromu, ale jak se od stromu vzdalujeme listů ubývá, ačkoliv pořád nějaké potkáváme. A totéž se přesně děje, když postupujeme k větším číslům. Stále nalézáme další prvočísla, ale jejich počet postupně klesá, čím dál se od stromu podíváme. Vraťme se k naší otázce: Kolik existuje prvočísel menších než nějaké přirozené číslo ‚x‘? Když si uděláme tabulku, vidíme, že počet prvočísel se neustále zvětšuje. Ale jak hledáme dál, nacházíme jich méně a méně. Pojďme si nakreslit graf s počtem prvočísel na svislé ose a rozsahem hledání (‚x‘) na vodorovné ose. Když pohled oddálíme až k miliardám, všimněte si, že se křivka nikdy nenarovná. Pořád roste, i když nepatrně. Zamysleme se nejdříve nad hustotou prvočísel menších než číslo ‚x‘. Hustotu získáme tak, že vydělíme počet prvočísel rozsahem hledání (‚x‘). Mezi prvními 100 přirozenými čísly najdeme 25 prvočísel, čili 25 %. Podobně mezi prvními 10 000 čísly najdeme 1229 prvočísel, 12,29 % je prvočísel. Mezi prvním milionem čísel najdeme 7,84 % prvočísel a prvočísel menších než 100 milionů je 5,76 %. Jak pokračujeme dále, tato hustota klesá, přestože pomaleji a pomaleji. Tady vidíte graf s rozsahem hledání na vodorovné ose a hustotou prvočísel na ose svislé. Všimněte si, že při vzdalování prvočísla tvoří stále menší zastoupení čísel. Překvapivě se tento vztah vyskytuje i v přírodě. Najdeme ho v galaxiích, bouřích, květech a dokonce i uvnitř našich těl jako uspořádání nejmenšího odporu známého jako „logaritmická spirála“. Jak se spirála otáčí, neustále se vzdaluje od středu. Zní to neuvěřitelně, ale rychlost otáčení logaritmické spirály je svázána s hustotou prvočísel. A to následovně: Sledujme počet otáček, které si označíme ‚φ‘ („fí“), a vzdálenost od středu, tu označme ‚r‘. Když nakreslíme graf závislosti ‚φ‘ na ‚r‘, uvidíme, že je popsán přirozeným logaritmem. To znamená, že přirozený logaritmus vzdálenosti má vztah k počtu otáček. Graf přirozeného logaritmu se obvykle zapisuje pomocí proměnných ‚x‘ a ‚y‘, kde ‚y‘ se rovná přirozenému logaritmu ‚x' (neboli y = ln x). Za povšimnutí stojí, že graf klesá podobně zvolna jako hustota prvočísel. Jako poslední krok převrátíme vztah a na svislou osu vyneseme 1/(ln x) místo ‚y‘. A jak oddalujeme pohled, před očima se nám zjeví stejná křivka, jako když jsme vykreslili hustotu prvočísel. Ověřme si to přiložením obou grafů k sobě. Zelená křivka znázorňuje y = 1/(ln x), červená hustotu prvočísel menších než ‚x‘. Jak se vzdalujeme, křivky se přibližují. Když jdeme k větším číslům, zelená křivka je lepším odhadem červené. Tomu se říká „asymptotický zákon o rozložení prvočísel“. Dostali jsme rovnici, která nám přesně řekne, jaká je hustota prvočísel - bez počítání. Hustota prvočísel menších než přirozené číslo ‚x‘ je přibližně 1/(ln x). Řekněme, že potřebujeme zjistit hustotu prvočísel mezi 1 a 100 biliony. Hračka. 1/ln(100 000 000 000 000) = 3.1 %. Porovnejme výsledek s opravdu spočítanými prvočísly, kterých je 3,2 %. To se liší jen o 0,1 %. A jak ověřujeme větší a větší čísla, rozdíl se blíží k nule. Uvědomte si, že můžeme tento vztah pro hustotu prvočísel použít k odhadu počtu prvočísel menších než ‚x‘. Počet prvočísel je plocha pod křivkou hustoty, což lze zjednodušit, pokud hustotu považujeme za konstatní. Počet prvočísel se rovná součinu velikosti a hustoty neboli x / (ln x). A to je prvočíselná věta. Zde vidíte modrou křivku y = x / (ln x) a žlutou křivku, která vyjadřuje skutečný počet prvočísel. Když graf oddálíme, tyto křivky se v nekonečnu nakonec spojí v jednu. A to je vše. Máme rovnici, která nám přibližně předpoví, kolik je prvočísel menších než nějaká hodnota – a bez počítání. Kupříkladu bychom chtěli vědět, kolik je prvočísel menších než 100 bilionů. 100 bilionů děleno přirozeným logaritmem 100 bilionů = 3,1 bilionu. Porovnejme to se skutečným počtem - 3,2 bilionu. Odpověď je z více než 96,87 procent přesná – dokonce i u takto relativně malých čísel. Zopakujme si to: Pokud hledáme až po nějaké číslo ‚x‘, hustota prvočísel činí přibližně 1 / (ln x) A počet prvočísel je přibližně x / ln(x). To je prvočíselná věta.
video