Welcome, Guest. Please login or register.

Autor Subiect: Formulă pi(n)  (Citit de 3348 ori)

0 Membri şi 1 Vizitator vizualizează acest subiect.

curiosul

  • Vizitator
Formulă pi(n)
« : Februarie 12, 2016, 09:02:24 a.m. »
În prima parte în subiectul
http://www.scientia.ro/forum/index.php/topic,5055.0.html
este dedusă o formulă pentru estimarea funcției \pi(n),
care determină numărul de numere prime mai mici egale cu n,
și anume  \pi(n)\approx n\left [\prod_{k=1}^{i}\left(\frac{p_{k}-1}{p_{k}}\right )\right] , unde p_{i}\leq \sqrt{n}< p_{i+1} .

Deschid acest subiect în care o să prezint anumite modalități pentru estimarea erorii formulei, deși în stadiul în care le-am analizat până acum sunt nefinalizate și probabil mai conțin și greșeli, sperând că mă poate  ajuta cineva să stabilesc eroarea de aproximare.

Folosind partea întreagă a unor fracții se poate determina valoarea exactă a funcției \pi(n).

Fie u\leq n , iar numărul de numere divizibile cu u mai mici/egale cu n este exact \left[\frac{n}{u}\right], unde parantezele pătrate semnifică partea întreagă a fracției.

Numărul de numere divizibile cu 2, mai mici/egale cu n, este \left[\frac{n}{2}\right].

Numărul de numere divizibile cu 3, dar nedivizibile cu 2, mai mici/egale cu n, este \left[\frac{n}{3}\right]-\left[\frac{n}{2\cdot3}\right].

Numărul de numere divizibile cu 5, dar nedivizibile cu 2 sau/și 3, mai mici/egale cu n, este \left[\frac{n}{5}\right]-\left[\frac{n}{2\cdot5}\right]-\left(\left[\frac{n}{3\cdot5}\right]-\left[\frac{n}{2\cdot 3\cdot5}\right]\right).

Numărul de numere divizibile cu 7, dar nedivizibile cu 2,3 sau/și 5, mai mici/egale cu n, este
\left[\frac{n}{7}\right]-\left[\frac{n}{2\cdot7}\right]-\left(\left[\frac{n}{3\cdot7}\right]-\left[\frac{n}{2\cdot 3\cdot7}\right]\right)-\left(\left[\frac{n}{5\cdot7}\right]-\left[\frac{n}{2\cdot5\cdot7}\right]-\left(\left[\frac{n}{3\cdot5\cdot7}\right]-\left[\frac{n}{2\cdot 3\cdot 5\cdot7}\right]\right)\right).

Exprimând în această manieră toate numerele divizibile cu p_{k}, dar nedivizibile cu niciun număr prim mai mic decât p_{k}, pentru toate primele i numere prime, unde p_{i}\leq \sqrt{n}< p_{i+1}, atunci \pi(n)-i+1 este egal cu

n-\left[\frac{n}{2}\right]-\left(\left[\frac{n}{3}\right]-\left[\frac{n}{2\cdot3}\right]\right)-\left(\left[\frac{n}{5}\right]-\left[\frac{n}{2\cdot5}\right]-\left(\left[\frac{n}{3\cdot5}\right]-\left[\frac{n}{2\cdot 3\cdot5}\right]\right)\right)
-\left(\left[\frac{n}{7}\right]-\left[\frac{n}{2\cdot7}\right]-\left(\left[\frac{n}{3\cdot7}\right]-\left[\frac{n}{2\cdot 3\cdot7}\right]\right)-\left(\left[\frac{n}{5\cdot7}\right]-\left[\frac{n}{2\cdot5\cdot7}\right]-\left(\left[\frac{n}{3\cdot5\cdot7}\right]-\left[\frac{n}{2\cdot 3\cdot 5\cdot7}\right]\right)\right)\right)

-\cdot\cdot\cdot

Numărul 1 nu este prim, dar nici divizibil cu niciun număr prim 2, 3, 5, 7,...,p_{i}, iar primele i numere prime 2, 3, 5, 7,...,p_{i} au fost eliminate ca și numere divizibile cu ele însele, motiv pentru care din valoarea exactă a lui \pi(n) trebuie scăzut i-1.

Dacă nu luăm în calcul partea întreagă atunci valoarea estimată va fi \pi(n)\approx n\left [\prod_{k=1}^{i}\left(\frac{p_{k}-1}{p_{k}}\right )\right] , unde p_{i}\leq \sqrt{n}< p_{i+1} și ceea ce vreau eu să fac acum este să calculez eroarea de aproximare.
Folosind partea întreagă putem obține o valoare exactă a lui \pi(n), iar în concluzie trebuie să ajungem la o modalitate corectă prin care să eliminăm partea întreagă a fracțiilor, ajungând la o formă care permite compararea dintre \pi(n) și  n\left [\prod_{k=1}^{i}\left(\frac{p_{k}-1}{p_{k}}\right )\right].

În acest modalitate prezentată acum eu am procedat așa.

Putem demonstra că

\left[\frac{n}{u}\right]+\left[\frac{n+1}{u}\right]+\left[\frac{n+2}{u}\right]+\cdot\cdot\cdot+\left[\frac{n+u-1}{u}\right]=n

și să încercăm să utilizăm această egalitate.

Spre exemplu

\left[\frac{n}{3}\right]+\left[\frac{n+1}{3}\right]+\left[\frac{n+2}{3}\right]=n

\left[\frac{n+3}{3}\right]+\left[\frac{n+4}{3}\right]+\left[\frac{n+5}{3}\right]=n+3

\left[\frac{n+6}{3}\right]+\left[\frac{n+7}{3}\right]+\left[\frac{n+8}{3}\right]=n+6

...

iar dacă avem 3k fracții unde numărătorii sunt numere consecutive,
suma va fi n+(n+3)+(n+6)+...=kn+3\frac{(k-1)k}{2}

Dacă încercăm să utilizăm această modalitate pentru partea întragă a fracțiilor din valoarea lui \pi(n) , va trebui să găsim un număr astfel încât suma totală a termenilor  să fie divizibil cu oricare dintre numitorii fracțiilor respective.
Acest număr este \prod_{k=1}^{i}p_{k} și să notăm pentru simplificare \beta=\prod_{k=1}^{i}p_{k} .

În continuare, să considerăm funcția \gamma(x), o funcția care determină câte numere nondivizibile cu niciun număr prim 2, 3, 5, 7,...,p_{i} , sunt mai mici/egale cu x, cu excepția numărului 1.
Numărul exact al acestora va putea fi exact determinat folosind exact aceleași fracții și va avea exact aceeași expresie folosite pentru determinarea lui \pi(n), cu excepția că numitorul fracțiilor va fi x în loc de n și nu vom mai scădea numărul i.

În acest caz suma \gamma(n)+\gamma(n+1)+\gamma(n+2)+\cdot\cdot\cdot+\gamma(n+\beta -1) va conține \beta termeni, și de asemenea vor fi \beta termeni pentru fiecare fracție cu același numitor.

Să notăm pentru simplificare \alpha =\prod_{k=1}^{i}(p_{k}-1), și făcând calculele putem stabili că

\sum_{k=0}^{\beta -1}\gamma(n+k)=n\alpha +\frac{\alpha \beta}{2}.

Evident, \gamma(n)=\pi(n)+1 .
Fie q_{1}, q_{2}, q_{3}, ..., q_{m} astfel încât n+q_{1}, n+q_{2}, n+q_{3}, ..., n+q_{m} sunt numere nedivizibile cu niciun număr prim 2, 3, 5, 7,...,p_{i} , unde q_{m}\leq \beta -1 și m=\alpha-1

Aceasta înseamnă că
\gamma(n)=\pi(n)+1
\gamma(n+q_{1})=\pi(n)+2
\gamma(n+q_{2})=\pi(n)+3
\gamma(n+q_{3})=\pi(n)+4
...
de unde rezultă că

\sum_{k=0}^{\beta -1}\gamma(n+k)=\left(\pi(n)+1\right)\beta+\beta \left ( \alpha -1 \right )-\sum_{k=0}^{\alpha -1}\left(q_{k}-1\right)

și de asemenea că

n\alpha +\frac{\alpha \beta}{2}=\left(\pi(n)+1\right)\beta+\beta \left ( \alpha -1 \right )-\sum_{k=0}^{\alpha -1}\left(q_{k}-1\right)

Simplificând egalitatea cu \beta se obține că

n\frac{\alpha}{\beta } +\frac{\alpha}{2}=\pi(n)+ \alpha -\frac{\sum_{k=0}^{\alpha -1}\left(q_{k}-1\right)}{\beta}

Înlocuind valorile lui \alpha și \beta și rearanjând termenii obținem că

n\left [\prod_{k=1}^{i}\left(\frac{p_{k}-1}{p_{k}}\right )\right] -\frac{\prod_{k=1}^{i}\left(p_{k}-1\right)}{2}+\frac{\sum_{k=0}^{\alpha -1}\left(q_{k}-1\right)}{\prod_{k=1}^{i}p_{k}}=\pi(n)

În felul acesta, dacă nimic nu este greșit, am eliminat partea întreagă a fracțiilor din valoarea lui \pi(n) și am adus egalitatea la o expresie ce permite compararea dintre \pi(n) și  n\left [\prod_{k=1}^{i}\left(\frac{p_{k}-1}{p_{k}}\right )\right] .

Nu reușesc să stabilesc o relație pentru aceea sumă de la numărător și am scris toate astea în speranța că poate îmi dă cineva vreo idee.
Desigur, o analiză atentă pentru ceea ce am scris aici impune ceva timp și calcule suplimentare și mă îndoiesc că își dedică cineva timp pentru asta, dar oricum ceea ce am scris poate le dă idei și celorlalți care analizează acest tip de probleme și poate, cine știe, din ce-i corect scris se poate folosi ceva util.
« Ultima Modificare: Februarie 12, 2016, 09:06:45 a.m. de curiosul »

curiosul

  • Vizitator
Răspuns: Formulă pi(n)
« Răspuns #1 : Februarie 17, 2016, 07:08:56 p.m. »
O altă modalitate de a analiza eroarea maximă de aproximare pentru  \pi(n)\approx n\left [\prod_{k=1}^{i}\left(\frac{p_{k}-1}{p_{k}}\right )\right] , unde p_{i}\leq \sqrt{n}< p_{i+1} este următoarea.

Putem scrie n\left [\prod_{k=1}^{i}\left(\frac{p_{k}-1}{p_{k}}\right )\right]-2 sub forma

\left(n-p_{i}^{2}\right)\left [\prod_{k=1}^{i}\frac{p_{k}-1}{p_{k}}\right]+\left(p_{i}^{2}-p_{i-1}^{2}\right)\left [\prod_{k=1}^{i-1}\frac{p_{k}-1}{p_{k}}\right]+\left(p_{i-1}^{2}-p_{i-2}^{2}\right)\left [\prod_{k=1}^{i-2}\frac{p_{k}-1}{p_{k}}\right]+\cdot \cdot \cdot +\left(p_{2}^{2}-p_{1}^{2}\right)\frac{1}{2}-

-p_{i}\left [\prod_{k=1}^{i-1}\frac{p_{k}-1}{p_{k}}\right]-p_{i-1}\left [\prod_{k=1}^{i-2}\frac{p_{k}-1}{p_{k}}\right]-p_{i-2}\left [\prod_{k=1}^{i-3}\frac{p_{k}-1}{p_{k}}\right]-\cdot \cdot \cdot -p_{2}\frac{1}{2}

Deși este adevărat, nu reușesc însă să demonstrez că

\left(n-p_{i}^{2}\right)\left [\prod_{k=1}^{i}\frac{p_{k}-1}{p_{k}}\right]\geq\pi(n)-\pi(p_{i}^{2})

\left(p_{i}^{2}-p_{i-1}^{2}\right)\left [\prod_{k=1}^{i-1}\frac{p_{k}-1}{p_{k}}\right]\geq\pi(p_{i}^{2})-\pi(p_{i-1}^{2})

\left(p_{i-1}^{2}-p_{i-2}^{2}\right)\left [\prod_{k=1}^{i-2}\frac{p_{k}-1}{p_{k}}\right]\geq\pi(p_{i-1}^{2})-\pi(p_{i-2}^{2})

... \left(p_{2}^{2}-p_{1}^{2}\right)\frac{1}{2}\geq \pi(p_{2}^{2})-\pi(p_{1}^{2})

iar de aici ar rezulta că

n\left [\prod_{k=1}^{i}\left(\frac{p_{k}-1}{p_{k}}\right)\right]+\sum_{q=2}^{i}\left(p_{q}\left [\prod_{h=1}^{q-1}\frac{p_{h}-1}{p_{h}}\right]\right)> \pi(n)

și ar demonstra evident inegalitatea

n\left [\prod_{k=1}^{i}\left(\frac{p_{k}-1}{p_{k}}\right)\right]< \pi (n)< 2n\left[\prod_{k=1}^{i}\left(\frac{p_{k}-1}{p_{k}}\right)\right]

Am încercat să utilizez relația \pi(a)-\pi(b)\leq \pi(a-b), cu a>b , dar nu ajută la nimic.