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 $\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

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

neu, a bod yn fanwl gywir, fod

$\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 $\pi (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 $\pi (x)$ o du Legendre: cymerwn $x$, os yw $p_{1}$, $p_{2}$, …, $p_{k}$ yn rhifau cysefin an-hafal, yna

$\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 $x$ a heb fod yn rhanadwy ag unrhyw $p_{i}$ (dynoda $\lfloor \cdot \rfloor$ y ffwythiant llawr). Mae'r rhif hwn felly'n hafal â

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

lle mai $p_{1},p_{2},\dots ,p_{k}$ 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 $\pi (x)$. Cymerwn mai $p_{1}$, $p_{2}$, …, $p_{n}$ yw'r $n$ rhif cysefin cyntaf, a dynodwn gyda $\Phi (m,n)$ nifer y rhifau naturiol sy'n llai na neu'n hafal ag $m$ nad ydynt yn rhanadwy ag unrhyw $p_{i}$. Yna mae

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

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

$\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 $m$ real ac $n$ a $k$ naturiol, $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 $p_{n}$. Ymhellach, gosodwn $P_{0}(m,n)=1$. Yna mae

$\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 $y$ ddynodi cyfanrif sy'n bodlonni ${\sqrt[{3}]{m}}\leq y\leq {\sqrt {m}}$, and gosod $n=\pi (y)$. Yna mae $P_{1}(m,n)=\pi (m)-n$ a $P_{k}(m,n)=0$ pan mae $k$ ≥ 3. Felly mae

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

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

$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 $\Phi (m,n)$ gyda'r rheolau canlynol:

1. $\Phi (m,0)=\lfloor m\rfloor ;\,$
2. $\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).

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

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

${\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.

$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

$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.