Ffwythiant cyfri rhifau cysefin
Oddi wrth Wicipedia, y gwyddoniadur rhydd.
Mewn mathemateg, y ffwythiant cyfri rhifau cysefin yw'r ffwythiant sy'n rhoi nifer y rhifau cysefin sy'n llai na neu'n hafal â rhyw rif real x. Fe'i dynodir gan π(x) (noder nad yw hyn yn cyfeirio i'r rhif π).
[golygu] Hanes
Mae cyfradd tyfiant y ffwythiant yn ddiddorol iawn yng nghyd-destyn haniaeth rhifau. Cynosododd Gauss a Legendre yn yr 18fed ganrif fod y cyfradd oddeutu
neu, a bod yn fanwl gywir, fod
Dyma yw'r theorem rhifau cysefin.
[golygu] Algorithmau i ganfod π(x)
Ffordd syml o ganfod π(x), os nad yw x yn rhy fawr, yw defnyddio gogr Eratosthenes i gynhyrchu'r rhifau cysefin sy'n llai na neu'n hafal ag x, ac yna'u cyfri.
Ddaw ddull coethach o ganfod π(x) o du Legendre: cymerwn x, os yw p1, p2, …, pk yn rhifau cysefin an-hafal, yna
yw nifer y cyfanrifau sy'n llai nag x ac heb fod yn rhanadwy ag unrhyw pi (dynoda y ffwythiant llawr). Mae'r rhif hwn felly'n hafal â
lle mai yw'r rhifau cysefin sy'n llai nau neu'n hafal ag ail isradd x.
Mewn cyfres o erthyglau a gyhoeddwyd rhwng 1870 a 1885, disgrifiodd Ernst Meissel dull cyfuniadol ymarferol o ganfod π(x). Cymerwn mai p1, p2, …, pn yw'r n rhif cysefin cyntaf, a dynodwn gyda Φ(m,n) nifer y rhifau naturiol sy'n llai na neu'n hafal ag m nad ydynt yn rhanadwy ag unrhyw pi. Yna mae
Cymerwn rif naturiol m: os mae a
, yna mae
Estynnwyd a symleiddwyd y dull hwn gan Derrick Henry Lehmer ym 1959. Diffiniwn, am m real ac n a k naturiol, Pk(m,n) yn nifer y rhifau msy'n llai na neu'n hafal ag n gyda'n union k o ffactorau cysefin, pob un yn fwy na pn. Ymhellach, gosodwn P0(m,n) = 1. Yna mae
lle dim ond nifer meidraidd o dermau an-sero sydd gan y swm. Gadewn i y ddynodi cyfanrif sy'n bodlonni , and gosod n = π(y). Yna mae P1(m,n) = π(m) − n a Pk(m,n) = 0 pan mae k ≥ 3. Felly mae
- π(m) = Φ(m,n) + n − 1 − P2(m,n).
Gellir cyfrifo P2(m,n) fel a ganlyn:
Yn ogystal, gellir cyfrifo Φ(m,n) gyda'r rheolau canlynol:
[golygu] Anhafaleddau
Mae'r canlynol yn anhafaleddau defnyddiol ar gyfer π(x).
ar gyfer x ≥ 17.
ar gyfer x > 1.
ar gyfer x ≥ 55.
Mae'r canlynol yn anhafaleddau ar gyfer yr nfed rhif cysefin, pn.
ar gyfer n ≥ 6.
Mae'n anhafaledd ar y chwith yn ddilys ar gyfer n ≥ 1 a'r un ar y dde ar gyfer n ≥ 6.
Mae
yn frasamcan ar gyfer yr nfed rhif cysefin.