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 π).

## 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,&nbsp;p_2,&nbsp;…,&nbsp;p_k yn rhifau cysefin an-hafal, yna

:\lfloor x\rfloor - \sum_{i}\left\lfloor\frac{x}{p_i}\right\rfloor + \sum_{i

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,&nbsp;p_2,&nbsp;…,&nbsp;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 *m*sy'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}\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&nbsp;≥&nbsp;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

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

#\Phi(m,0)=\lfloor m\rfloor;\,
#\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)  ar gyfer x > 1.

: 
\frac {x} {\log x + 2}  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   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.

Categori:Haniaeth rhifau
Categori:Rhifau cysefin