Algarvusesõel ja Ulami spiraal

Vaata, kuidas Eratosthenese sõel eemaldab kordarvud, või vaata algarve Ulami spiraalil.

Näidisarvutus — Algarvusesõel ja Ulami spiraal

π(100)	25 algarvu
N / ln N	21.7(13.1% viga)
Li(N)	29.1(16.3% viga)
Kaksikpaarid	8 paari
Suurim vahe	8

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Algarvusesõel ja Ulami spiraal

Paneel trükib kaht eri liiki arvu ja tasub need eristada, enne kui midagi muud lugema hakata. π(N) on loend — mitu algarvu sõel tegelikult püsti jättis, 25 kui N = 100 ja 95 kui N = 500, täpne ja ümardamata. Kaks rida selle all on sellesama loendi hinnangud. Algarvude teoreem väidab, et üks neist tabab piiril suhte õigesti; ta ei väida, et ta tabab arvu õigesti. Need on väga erinevad lubadused ja vahe paistab välja vearealt.

Mida iga sümbol tähendab

N: ülempiir, milleni sõelutakse, ja ainus sisend. Liugur ulatub 10000-ni.
π(N): algarvude arv, mis ei ületa N-i. Loendatud, mitte hinnatud — lihtsalt nii mitu ruutu, kui sõel maha ei tõmmanud.
N / ln N: selle loendi kõige lihtsam hinnang. Igal N-il, milleni see liugur ulatub, jääb see tõest allapoole.
Li(N): integraallogaritm ∫₂ᴺ dt/ln t, teravam hinnang. Igal N-il, milleni see liugur ulatub, jääb see tõest ülespoole.

Kust valem tuleb

Sõel ei küsi kunagi, kas arv on algarv. Ta alustab kahest ja kriipsutab maha kõik kahe kordsed, liigub järgmise veel püsti oleva arvuni, kriipsutab maha kõik selle kordsed ja kordab. Algarvulisust ei kontrollita; see on see, mis üle jääb.
Maha tuleb kriipsutada ainult algarvude kordseid kuni √N. Kui arv n ≤ N on kordarv, siis n = a·b, kus a ≤ b, seega a ≤ √n ≤ √N — igal kordarvul on tegur, mis on ruutjuurest väiksem või sellega võrdne, ja ta sai seega juba maha kriipsutatud, kui selle teguri kord kätte jõudis. Sajani sõelumiseks piisab kahe, kolme, viie ja seitsme käikudest.
Loenda ellujääjad ja saadki täpselt π(N). Just seepärast on ülemine rida fakt ja kaks alumist arvamused: sõel annab loendi oma töö kõrvalsaadusena.
Nüüd võrdle. Algarvude teoreem ütleb, et π(N) · ln N / N → 1, kui N kasvab. Pane tähele, mida see ei ütle: ühele lähenev suhe lubab protsentuaalsel veal jääda väga kauaks suureks — ja järgmine rida näitabki täpselt seda.

Kuidas nähtut lugeda

Loe kaht veaprotsenti kui võidujooksu ja muuda N-i. N = 100 juures juhib jäme hinnang: 13.1% Li 16.3% vastu. Mine N = 200 peale ja see pöördub — 17.9% 6.9% vastu — ega pöördu enam kunagi tagasi. Kõige tähelepanuväärsem on aga see, mida N/ln N ei tee. Kahe suurusjärgu jooksul on ta viga 14.8%, 13.1%, 15.3%, 13.8%, 12.2%: see kõigub ega parane peaaegu üldse. Li läheb samal vahemikul 16.3% pealt 2.8% peale. Mõlemad hinnangud rahuldavad algarvude teoreemi; kasutatav on neist vaid üks nendes suurusjärkudes, mida sa näha saad. Sama järjekindlad on ka märgid — N/ln N jääb siin igal N-il loendist allapoole ja Li ülespoole.

Eeldab: Et N on piisavalt väike, et teda tervikuna läbi sõeluda: loend on täpne seetõttu, et iga arv kuni N-ini tõesti hoitakse ja kriipsutatakse, ning just sellepärast on lagi 10000, mitte 10¹⁰. Veaprotsendid võetakse π(N) suhtes, seega mõõdavad nad hinnanguid ega mõõda kunagi loendit.
Ei kehti, kui: Li(N) > π(N) kehtib igal N-il, milleni see lehekülg ulatub, ja see näeb välja nagu seadus. Seda ta ei ole. Littlewood tõestas 1914. aastal, et vahe vahetab märki lõpmata palju kordi, seega leidub N-e, kus Li alahindab — ja sajandi jooksul pole keegi ühtki neist ette näidanud. Bays ja Hudson surusid esimese ületuskoha 1999. aastal alla umbes 1.4×10³¹⁶ ja kitsamaks pole see sellest saati läinud. See lehekülg näitab sulle seega mustrit, mille kohta on tõestatud, et see pole üldkehtiv, ja ükski liuguri asend ei ulatu vastunäiteni. Just see vahe nähtava ja tõese vahel ongi selle teema aus kuju.

Hõrenemine, mida ruudustikus näed, on see osa, mida keegi ei suuda tõestada 🖖

Algarvude täpset jaotust juhivad Riemanni dzeetafunktsiooni ζ(s) nullkohad. Kõik 10¹³ teadaolevat mittetriviaalset nullkohta asuvad kriitilisel sirgel Re(s) = 1/2. Selle tõestamine kõigi nullkohtade jaoks annaks kõige täpsemad võimalikud piirid algarvude loendamiseks — ja tooks 1 miljoni dollari suuruse Millenniumi auhinna. 2025. aasta seisuga on see tõestamata.

Sõelu, ära kontrolli 🖖

Eratosthenese sõel leiab algarvud väljajätmise, mitte iga arvu kontrollimise teel. Alusta arvust 2, kriipsuta maha kõik selle kordsed, hüppa järgmise ellujäänud arvu juurde ja korda; mis kunagi maha ei kriipsutata, on algarv. Nutikas nipp: et sõeluda kõik arvud kuni n, tuleb eemaldada vaid algarvude kordsed kuni √n. Nii piisab kõige alla 100 jaoks arvude 2, 3, 5 ja 7 kordsete mahakriipsutamisest.

Ulami igavuse kritseldus 🖖

1963. aastal kritseldas matemaatik Stanisław Ulam ettekande ajal igavusest täisarvud ruudukujulisse spiraali ja märkis ära algarvud — ilmusid üllatavalt selged diagonaaltriibud. Need diagonaalid järgivad algarvurikkaid ruutvalemeid nagu Euleri n² + n + 41, mis annab algarvu iga n korral vahemikus 0 kuni 39. Miks mõned diagonaalid nii tihedaks jäävad, pole siiani täielikult mõistetud.

Ülesanded täielikult lahendatud

Alla 100 jääva 25 algarvu käsitsi sõelumine 5 sammu
Alla 100 on 25 algarvu. Sõelu need käsitsi välja — see nõuab vähem tööd kui võiks arvata — ning seejärel testi algarvuteoreemi valimil, mis on selle jaoks kaugele liiga väike.
1. Sõela ajasääst on põhjus, miks see on oma nime väärt. Kui n ≤ 100 on kordnarv, tegurdub see kujul ab ning väiksem tegur ei saa ületada väärtust √100 = 10. Seega eemaldab iga algarvu kordsete mahatõmbamine kuni arvuni 10 eranditult kõik kordnarvud: kogu töö teevad ära neli algarvu.
  
  $n \leq 100 composite ⟹ n = ab with min (a, b) \leq 100 = 10$
2. Tõmba maha arvu 2, 3, 5 ja 7 kordsed, alustades igaühe puhul selle ruudust, sest kõik sellest väiksem on juba eemaldatud. Järele jääb kakskümmend viis arvu.
  
  $strike multiples of 2, 3, 5, 7 from 4 upward ⟹ π (100) = 25$
3. Algarvuteoreemi kohaselt on algarvude arv asümptootiliselt N/ln N. Kui N = 100, on see 21,7.
  
  $π (N) \sim \frac{N}{ln N} : \frac{100}{ln 100} = \frac{100}{4.6052} = 21.7$
4. See on 13% võrra liiga väike, mis on asümptootilise tulemuse puhul arvu 100 juures täiesti ootuspärane. Teistpidi vaadatuna on see siin siiski kasulik: algarvude tihedus arvu N lähedal on 1/ln N, seega on umbes 22% arvudest 100 lähedal algarvud, võrreldes 7,2%-ga miljoni lähedal. Algarvude tihedus väheneb logaritmiliselt, mis on tõepoolest väga aeglane.
  
  $\frac{25 - 21.7}{25} = 13.1%, \frac{1}{ln 100} = 21.7% vs \frac{1}{ln 1 0 ^{6}} = 7.2%$
5. Vahed klapivad. Keskmine vahe alla 100 on 100/25 = 4 ja suurim on 8 — jada 89-st 97-ni. Kaks korda keskmine ja mitte halvem.
  
  $mean gap = \frac{100}{25} = 4, largest = 97 - 89 = 8$
Vastus

Sõel annab tulemuseks π(100) = 25 ning tööriist kuvab hinnanguks 21,7, mis on 13,1% liiga väike. See viga ei tähenda teoreemi puudulikkust; see näitab piltlikult teoreemi koonduvuse kiirust, ja see koondumine on teadaolevalt aeglane — suurenda N arvu 10 000-ni (neli suurusjärku võrra) ja hinnang on ikka veel kahekohalise protsendi võrra liiga väike. Igas skaalas peab paika tiheduse näit. Üks arv 4,6-st arvu 100 lähedal on algarv, üks 13,8-st miljoni lähedal, ning kuna logaritm kasvab nii aeglaselt, ei lõpe algarvud kunagi otsa ega muutugi päris haruldaseks.

$π (100) = 25 from four primes; \frac{N}{ln N} = 21.7 (13.1% low)$
Ilmne hinnang 8 kaksikpaarile alla 100 6 sammu
Paneel loeb 100-st väiksemaid algarve 25 ja kaksikpaare 8. Esimese arvu jaoks on kuulus hinnang, mis jääb 13 % piiresse. Proovi teise jaoks ilmset hinnangut — ja vaata, kuidas see eksib teguri võrra, millel on nimi.
1. Võta lähtekohaks trükitud loend ja trükitud hinnang: N lähedal on arv algarv tõenäosusega umbes 1/ln N, ja N = 100 juures on see ligikaudu 0,2171.
  
  $π (100) = 25, \frac{N}{ln N} = \frac{100}{4.6052} = 21.7$
2. Nüüd eelda, et n ja n+2 on sõltumatud. Kui kumbki on algarv tõenäosusega 1/ln N, siis mõlemad selle ruuduga.
  
  $P_{1} \approx \frac{1}{ln N} = 0.2171 ⟹ P_{2} \approx P_{1}^{2} = \frac{1}{( ln N ) ^{2}}$
3. Korruta N-ga ja võrdle tööriistaga. Hinnang annab 100-st väiksemaid kaksikpaare 4,72; sõel leidis 8. See pole veidi mööda — see on 40 % puudu.
  
  $N P_{2} = \frac{100}{21.208} = 4.72 ⟷ π_{2} (100) = 8$
4. Sõltumatus on vale samm, ja üksainus algarv näitab miks. Võta paaritu algarv p: juhuslik n langeb p tõttu välja ühel juhul p-st, aga paar langeb välja alati, kui n või n+2 jagub p-ga — see on kaks jääki p-st. Ellujäämismäär on seega (p−2)/p, mitte (p−1)/p ruut, nagu sõltumatus eeldas.
  
  $p > 2 : n \equiv 0 \lor n + 2 \equiv 0 (mod p) ⟹ \frac{p - 2}{p} \neq = (\frac{p - 1}{p})^{2}$
5. Korruta see parand üle kõigi paaritute algarvude ja see koondub konstandiks. Kahekordsena on see 1,3203, ja rakendatuna tõstab see hinnangu 6,23-ni.
  
  $2 C_{2} = 2 p > 2 \prod \frac{p ( p - 2 )}{( p - 1 ) ^{2}} = 1.3203 ⟹ 1.3203 \times 4.72 = 6.23$
6. N = 100 juures ikka alla 8 — hinnang on asümptootiline ja 100 on väike arv. See koondub: 156 paari alla 10⁴, 6917 alla 10⁶.
  
  $N = 1 0^{4} : 156 N = 1 0^{6} : 6917$
Vastus

Naiivne arv on 4,72, parandatud 6,23 ja tõde on 8 — ning parandustegur 1,3203 on lõpmatu korrutis üle algarvude. See konstant on hind, mida makstakse sõltumatuse eeldamise eest seal, kus seda pole, ja tal on peaaegu iga selle valdkonna raske küsimuse kuju: algarvud on piisavalt juhuslikud, et heuristika töötaks, ja piisavalt struktuursed, et see vajaks parandit, mida keegi ei oska nullist tuletada. Algarvukaksikute hüpotees ütleb, et sellel hinnangul ei saa paarid kunagi otsa, ja see on siiani lahtine.

$π_{2} (N) \sim 2 C_{2} \frac{N}{( ln N ) ^{2}}, 2 C_{2} = 1.3203 : 4.72 \to 6.23 ⟷ 8$

Allikad (4)

Why the page’s most convincing pattern is not a law — the difference changes sign infinitely often: J. E. Littlewood, "Sur la distribution des nombres premiers." Comptes Rendus de l’Académie des Sciences, Paris 158, 1869–1872, 1914. No DOI: the volume predates them.
How far the first sign change has been pinned down, and where the 1.4×10³¹⁶ comes from: C. Bays & R. H. Hudson, "A new bound for the smallest x with π(x) > li(x)." Mathematics of Computation 69, 1285–1296, 1999.
How far the Riemann hypothesis has actually been verified — note this is a bound on height, a different measure from a count of zeros: D. J. Platt & T. S. Trudgian, "The Riemann hypothesis is true up to 3·10^12." Bulletin of the London Mathematical Society 53, 792–797, 2021.
The prize, and its official problem statement: Clay Mathematics Institute, Millennium Prize Problems — the Riemann Hypothesis.

42Mathi meeskond · Uuendatud 2026-06-20

Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud. Toimetamispõhimõtted · Parandused

Kõik Matemaatika õppetunnid →

Näiteülesanded

Väike (100) - Sõelu arvuni 100 ning võidab jäme hinnang: N/ln N annab 21,7, eksides 13,1%, samas kui Li(100) = 29,1 eksib 16,3%. See on ainus eelseadistus, kus nii juhtub. Mine arvuni 500 ja Li viga langeb 6,2% tasemele. N/ln N püsib samal ajal 15,3% juures ning jääbki sinna.
Keskmine (500) - Alla 500 on 95 algarvu ja 24 kaksikalgarvude paari. Suurim vahe on 14 – lõigul 113 kuni 127 ei leidu ühtegi algarvu. See rekord püsib arvuni 523, kus avaneb vahe pikkusega 18. Rekordvahe ei kasva arvuga N ühtlaselt. Ta ootab.
Külmad veerud - Alla 900 leidub 154 algarvu ja 35 kaksikalgarvude paari. Jätka arvuni 1000 ning leiad veel 14 algarvu, kuid mitte ühtegi uut kaksikute paari. Viimaseks jäävad 881 ja 883. Kaksikalgarvud harvenevad algarvudest kiiremini. Kas need kunagi ka lõppevad, on siiani lahtine küsimus.
Ulam 400 - Samad 78 algarvu mis ruudustikurežiimis, paigutatuna ümber ruutspiraalile. Arvude juures ei muutunud midagi. Diagonaalsed vöödid tulenevad sellest, kuhu spiraal iga täisarvu asetab. Just seepärast võibki pilt viidata mustrile, mida aritmeetika pole kinnitanud.
Algarvude teoreem (1000) - π(1000) = 168. N/ln N annab 144,8, eksides 13,8%. Li(1000) annab 177,0, eksides 5,3%. Mõlemad vastavad algarvuteoreemile. Iga N juures, milleni see tööriist ulatub, on aga päriselt kasu vaid ühest. Seejuures jääb Li tegelikust arvust alati kõrgemale.