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/\ln (x),$

neu, a bod yn fanwl gywir, fod

$\underset{x\to +\mathrm{\infty }}{\lim }\frac{\pi (x)}{x/\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\lfloor \frac{x}{p_i}\rfloor +\sum _{i<j}\lfloor \frac{x}{p_i{p}_j}\rfloor -\sum _{i<j<k}\lfloor \frac{x}{p_i{p}_j{p}_k}\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[\frac{m}{p_n}\right],n-1),$

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}^{+\mathrm{\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}\le y\le \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\le \sqrt{m}}(\pi \left(\frac{m}{p}\right)-\pi (p)+1).$

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 (\frac{m}{p_b},b-1).$

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.