Ffwythiant cyfri rhifau cysefin

Oddi ar Wicipedia
Neidio i: llywio, chwilio

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[golygu]

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

 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)[golygu]

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_1p_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_ip_j}\right\rfloor - \sum_{i<j<k}\left\lfloor\frac{x}{p_ip_jp_k}\right\rfloor + \cdots,

yw nifer y cyfanrifau sy'n llai nag x ac 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_1p_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}\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}}\left(\pi\left(\frac mp\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[golygu]

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 nfed rhif cysefin, pn.

 
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 nfed rhif cysefin.