Ffwythiant cyfri rhifau cysefin

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 ${\displaystyle \pi (x)}$ (noder nad yw hyn yn cyfeirio i'r rhif π).

60 gwerth cyntaf π(n)

Hanes

Mae cyfradd tyfiant y ffwythiant yn ddiddorol iawn yng nghyd-destyn haniaeth rhifau. Cynosododd Gauss a Legendre yn yr 18g fod y cyfradd oddeutu

${\displaystyle x/\operatorname {ln} (x),\,}$

neu, a bod yn fanwl gywir, fod

${\displaystyle \lim _{x\rightarrow +\infty }{\frac {\pi (x)}{x/\operatorname {ln} (x)}}=1.\,}$

Dyma yw'r theorem rhifau cysefin.

Algorithmau i ganfod π(x)

Ffordd syml o ganfod ${\displaystyle \pi (x)}$, os nad yw ${\displaystyle x}$ yn rhy fawr, yw defnyddio gogr Eratosthenes i gynhyrchu'r rhifau cysefin sy'n llai na neu'n hafal ag ${\displaystyle x}$, ac yna'u cyfri.

Ddaw ddull coethach o ganfod ${\displaystyle \pi (x)}$ o du Legendre: cymerwn ${\displaystyle x}$, os yw ${\displaystyle p_{1}}$, ${\displaystyle p_{2}}$, …, ${\displaystyle p_{k}}$ yn rhifau cysefin an-hafal, yna

${\displaystyle \lfloor x\rfloor -\sum _{i}\left\lfloor {\frac {x}{p_{i}}}\right\rfloor +\sum _{i<j}\left\lfloor {\frac {x}{p_{i}p_{j}}}\right\rfloor -\sum _{i<j<k}\left\lfloor {\frac {x}{p_{i}p_{j}p_{k}}}\right\rfloor +\cdots ,}$

yw nifer y cyfanrifau sy'n llai nag ${\displaystyle x}$ a heb fod yn rhanadwy ag unrhyw ${\displaystyle p_{i}}$ (dynoda ${\displaystyle \lfloor \cdot \rfloor }$ y ffwythiant llawr). Mae'r rhif hwn felly'n hafal â

${\displaystyle \pi (x)-\pi \left({\sqrt {x}}\right)+1\,}$

lle mai ${\displaystyle p_{1},p_{2},\dots ,p_{k}}$ yw'r rhifau cysefin sy'n llai nau neu'n hafal ag ail isradd ${\displaystyle x}$.

Mewn cyfres o erthyglau a gyhoeddwyd rhwng 1870 a 1885, disgrifiodd Ernst Meissel dull cyfuniadol ymarferol o ganfod ${\displaystyle \pi (x)}$. Cymerwn mai ${\displaystyle p_{1}}$, ${\displaystyle p_{2}}$, …, ${\displaystyle p_{n}}$ yw'r ${\displaystyle n}$ rhif cysefin cyntaf, a dynodwn gyda ${\displaystyle \Phi (m,n)}$ nifer y rhifau naturiol sy'n llai na neu'n hafal ag ${\displaystyle m}$ nad ydynt yn rhanadwy ag unrhyw ${\displaystyle p_{i}}$. Yna mae

${\displaystyle \Phi (m,n)=\Phi (m,n-1)-\Phi \left(\left[{\frac {m}{p_{n}}}\right],n-1\right),\,}$

Cymerwn rif naturiol ${\displaystyle m}$: os mae ${\displaystyle n=\pi \left({\sqrt[{3}]{m}}\right)}$ a ${\displaystyle \mu =\pi \left({\sqrt {m}}\right)-n}$, yna mae

${\displaystyle \pi (m)=\Phi (m,n)+n(\mu +1)+{\frac {\mu ^{2}-\mu }{2}}-1-\sum _{k=1}^{\mu }\pi \left({\frac {m}{p_{n+k}}}\right).\,}$

Estynnwyd a symleiddwyd y dull hwn gan Derrick Henry Lehmer ym 1959. Diffiniwn, am ${\displaystyle m}$ real ac ${\displaystyle n}$ a ${\displaystyle k}$ naturiol, ${\displaystyle P_{k}(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 ${\displaystyle p_{n}}$. Ymhellach, gosodwn ${\displaystyle P_{0}(m,n)=1}$. Yna mae

${\displaystyle \Phi (m,n)=\sum _{k=0}^{+\infty }P_{k}(m,n),\,}$

lle dim ond nifer meidraidd o dermau an-sero sydd gan y swm. Gadewn i ${\displaystyle y}$ ddynodi cyfanrif sy'n bodlonni ${\displaystyle {\sqrt[{3}]{m}}\leq y\leq {\sqrt {m}}}$, and gosod ${\displaystyle n=\pi (y)}$. Yna mae ${\displaystyle P_{1}(m,n)=\pi (m)-n}$ a ${\displaystyle P_{k}(m,n)=0}$ pan mae ${\displaystyle k}$ ≥ 3. Felly mae

${\displaystyle \pi (m)=\Phi (m,n)+n-1-P_{2}(m,n).}$

Gellir cyfrifo ${\displaystyle P_{2}(m,n)}$ fel a ganlyn:

${\displaystyle P_{2}(m,n)=\sum _{y<p\leq {\sqrt {m}}}\left(\pi \left({\frac {m}{p}}\right)-\pi (p)+1\right).\,}$

Yn ogystal, gellir cyfrifo ${\displaystyle \Phi (m,n)}$ gyda'r rheolau canlynol:

1. ${\displaystyle \Phi (m,0)=\lfloor m\rfloor$ ;\,}
2. ${\displaystyle \Phi (m,b)=\Phi (m,b-1)-\Phi \left({\frac {m}{p_{b}}},b-1\right).\,}$

Anhafaleddau

Mae'r canlynol yn anhafaleddau defnyddiol ar gyfer π(x).

${\displaystyle \pi (x)>{\frac {x}{\log x}}}$ ar gyfer x ≥ 17.

${\displaystyle \pi (x)<1.25506{\frac {x}{\log x}}}$ ar gyfer x > 1.

${\displaystyle {\frac {x}{\log x+2}}<\pi (x)<{\frac {x}{\log x-4}}}$ ar gyfer x ≥ 55.

Mae'r canlynol yn anhafaleddau ar gyfer yr n^fed rhif cysefin, p_n.

${\displaystyle n\ \ln n+n\ln \ln n-n<p_{n}<n\ln n+n\ln \ln n}$ 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

${\displaystyle p_{n}=n\ln n+n\ln \ln n-n+{\frac {n\ln \ln n-2n}{\ln n}}+O\left({\frac {n(\ln \ln n)^{2}}{(\ln n)^{2}}}\right).}$

yn frasamcan ar gyfer yr n^fed rhif cysefin.