Pirminių skaičių teorema: kas tai, formulė n/ln(n) ir istorija
Sužinokite pirminių skaičių teoremą: paaiškinimas, formulė n/ln(n), reikšmė skaičiavimuose ir istorija nuo Gauso iki 1896 m. įrodymo.
Pirminio skaičiaus teorema yra skaičių teorijos teorema, apibūdinanti, kaip išsidėsto pirminiai skaičiai tarp natūraliųjų skaičių. Teorema teigia, kad skaičių kiekis, mažesnis arba lygus n (žymimas π(n)), asimptotiškai elgiasi kaip n/ln(n). Kitaip sakant, π(n) ≍ n / ln(n), arba formaliai
limn→∞ π(n) / (n / ln n) = 1.
Iš to seka, jog tankis (tikimybė), kad atsitiktinis pakankamai didelis skaičius yra pirminis, yra maždaug 1 / ln(n), o ne n/ln(n). Taigi, jei renkamės skaičių apytiksliai dydžio n, tikimybė, kad jis bus pirminis, yra maždaug 1/ln(n). Todėl vidutinis atstumas (tarpas) tarp iš eilės einančių pirminių skaičių tarp pirmųjų N natūraliųjų skaičių yra maždaug ln(N).
Formulė ir geresnės aproksimacijos
Grubus apytikslis skaičiaus pirminių skaičių skaičius iki n yra n/ln(n), bet tam tikroms paskaitoms geresnė yra logaritminė integralė li(n) = ∫_2^n dt / ln t, kuri duoda tikslesnę aproksimaciją: π(n) ~ li(n). Tačiau pagrindinė ir paprastesnė teoreminė forma, dažnai vadinama „pirminių skaičių teorema“, yra π(n) ~ n / ln n.
Istorija ir įrodymai
Penkiolikmetis Carlas Friedrichas Gaussas apie 1793 m. neprisiminė formalios formulės, bet pasiūlė mintį, kad pirminių skaičių tankis susijęs su logaritmais. Adrienas‑Marie Legendre'as 1798 m. taip pat pateikė panašią hipotezę ir netgi pasiūlė konkretesnę formulę su konstantomis. Iki XIX a. antros pusės Chebyshev parodė užuominas ir ribas, kurios rodė, kad π(n) turi tos pačios eilės augimą kaip n/ln n, bet pilną įrodymą pateikė Žakas Hadamaras (Jacques Hadamard) ir Šarlis Žanas de La Vallée Poussin 1896 m. Jų įrodymas panaudojo kompleksinę analizę ir Riemanno zeta funkcijos savybes — svarbiausia buvo įrodyti, kad ζ(s) neturi nulių plokštumoje Re(s) = 1, kas leido užtikrinti reikiamą asimptotinį elgesį.
Įrodymo idėja (trumpai)
- Analitiniai metodai: pagrindinis įrankis yra Riemanno zeta funkcija ζ(s) ir jos analizė kompleksinėje plokštumoje.
- Chebyshev rodmenys ir funkcijos θ(x), ψ(x) (susijusios su pirminių logaritmais) naudojamos siekiant pereiti tarp suminių funkcijų ir pirminių skaičių skaičiaus π(x).
- Hadamard ir de La Vallée Poussin rodė, kad ζ(s) ≠ 0 kai Re(s)=1, o tai leido gauti reikiamas asimptotes ir baigti įrodymą.
Klaidos termai ir Riemanno hipotezė
Nors pagrindinis teiginys π(x) ~ x/ln x yra jau visapusiškai įrodytas, svarbi matematikos dalis yra, kiek tiksliai π(x) skiriasi nuo x/ln x arba li(x). Riemanno hipotezė, jeigu ji būtų įrodyta, duotų daug griežtesnius arba „optimalius“ klaidos termus (pvz., reikšmingai mažesnis maksimumo dydis). Be RH, yra gauti įvairūs vienareikšmiški, bet silpnesni netiesioginiai ir eksponentiniai klaidos termų įverčiai naudojant pažangius analizės metodus.
Pavyzdžiai ir praktinė reikšmė
Išeinant iš tankio 1/ln(n), gauname praktinių pavyzdžių, svarbių, pavyzdžiui, kriptografijai (kai generuojami dideli atsitiktiniai pirminiai skaičiai):
- Tikimybė, kad atsitiktinis ~n dydžio skaičius bus pirminis, yra apytiksliai 1/ln(n).
- Skaičiams, turintiems k dešimčių (skaityt skaitmenų skaičių), n apytikriai 10^(k-1). Todėl tikimybė, kad atsitiktinis k‑skaitmenų skaičius bus pirminis, yra apytiksliai 1/(k ln 10). Pavyzdžiui, tarp skaičių, turinčių ne daugiau kaip 1000 skaitmenų, tikimybė būti pirminiu yra apie 1/ln(10^1000) = 1/(1000 ln 10) ≈ 1/2302,6, t. y. maždaug vienas iš 2300. Tarp skaičių su ne daugiau kaip 2000 skaitmenų analogiškai – maždaug vienas iš 4605 (ln(10^2000) ≈ 4605,2).
- Vidutinis tarpats tarp dviejų greta esančių pirminių, kai skaičiai dideli, yra apie ln(n); tai paaiškina, kodėl pirminių tarpai didėja, nors jie ir toliau pasitaiko be aiškaus periodiškumo.
Pirminių skaičių teorema — vienas iš kertinių rezultatais skaičių teorijoje — suteikia pagrindą daugeliui praktinių taikymų (pvz., saugumo protokoluose) ir yra atspirties taškas giliau suprasti pirminių skaičių pasiskirstymą bei ryšius su kompleksine analize ir zeta funkcijos teorija.
Klausimai ir atsakymai
K: Kas yra pirminių skaičių teorema?
A: Pirminių skaičių teorema - tai skaičių teorijos teorema, paaiškinanti, kaip pirminiai skaičiai pasiskirsto skaičių intervale.
K: Ar pirminiai skaičiai tolygiai pasiskirstę skaičių intervale?
A: Ne, pirminiai skaičiai nėra tolygiai pasiskirstę skaičių intervale.
K: Ką įformina pirminių skaičių teorema?
A: Pirminių skaičių teorema įformina idėją, kad tikimybė pataikyti pirminį skaičių tarp 1 ir tam tikro skaičiaus mažėja didėjant skaičiams.
K: Kokia tikimybė, kad tarp 1 ir tam tikro skaičiaus pataikysime pirminį skaičių?
Atsakymas: Tikimybė, kad tarp 1 ir tam tikro skaičiaus pataikysime pirminį skaičių, yra maždaug n/ln(n), kur ln(n) yra natūraliojo logaritmo funkcija.
K: Ar tikimybė pataikyti pirminį skaičių, turintį 2n skaitmenų, yra didesnė už tikimybę pataikyti pirminį skaičių, turintį n skaitmenų?
Atsakymas: Ne, tikimybė pataikyti pirminį skaičių su 2n skaitmenų yra maždaug perpus mažesnė nei su n skaitmenų.
K: Kas įrodė pirminių skaičių teoremą?
A: Žakas Hadamaras ir Šarlis Žanas de La Valė Puzenas pirminių skaičių teoremą įrodė 1896 m., praėjus daugiau nei šimtmečiui po to, kai 1793 m. Gausas įtarė ryšį tarp pirminių skaičių ir logaritmų.
K: Koks yra vidutinis tarpas tarp iš eilės einančių pirmųjų N sveikųjų skaičių?
Atsakymas: Vidutinis tarpas tarp pirmųjų N sveikųjų skaičių yra apytiksliai lygus ln(N).
Ieškoti