Ştiri:

Vă rugăm să citiţi Regulamentul de utilizare a forumului Scientia în secţiunea intitulată "Regulamentul de utilizare a forumului. CITEŞTE-L!".

Main Menu

Formulă pi(n)

Creat de curiosul, Februarie 12, 2016, 09:02:24 AM

« precedentul - următorul »

0 Membri şi 1 Vizitator vizualizează acest subiect.

curiosul

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

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 [tex]\pi(n)[/tex].

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

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

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

Numărul de numere divizibile cu 5, dar nedivizibile cu 2 sau/și 3, mai mici/egale cu n, este [tex]\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)[/tex].

Numărul de numere divizibile cu 7, dar nedivizibile cu 2,3 sau/și 5, mai mici/egale cu n, este
[tex]\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)[/tex].

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

[tex]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)[/tex]
[tex]-\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)[/tex]

[tex]-\cdot\cdot\cdot[/tex]

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

Dacă nu luăm în calcul partea întreagă atunci valoarea estimată va fi [tex]\pi(n)\approx n\left [\prod_{k=1}^{i}\left(\frac{p_{k}-1}{p_{k}}\right )\right] [/tex], unde [tex]p_{i}\leq \sqrt{n}< p_{i+1}[/tex] ș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 [tex]\pi(n)[/tex], 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 [tex]\pi(n)[/tex] și  [tex]n\left [\prod_{k=1}^{i}\left(\frac{p_{k}-1}{p_{k}}\right )\right][/tex].

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

Putem demonstra că

[tex]\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[/tex]

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

Spre exemplu

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

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

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

...

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

Dacă încercăm să utilizăm această modalitate pentru partea întragă a fracțiilor din valoarea lui [tex]\pi(n)[/tex] , 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 [tex]\prod_{k=1}^{i}p_{k}[/tex] și să notăm pentru simplificare [tex]\beta=\prod_{k=1}^{i}p_{k}[/tex] .

În continuare, să considerăm funcția [tex]\gamma(x)[/tex], o funcția care determină câte numere nondivizibile cu niciun număr prim [tex]2, 3, 5, 7,...,p_{i}[/tex] , 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 [tex]\pi(n)[/tex], 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 [tex]\gamma(n)+\gamma(n+1)+\gamma(n+2)+\cdot\cdot\cdot+\gamma(n+\beta -1)[/tex] va conține [tex]\beta[/tex] termeni, și de asemenea vor fi [tex]\beta[/tex] termeni pentru fiecare fracție cu același numitor.

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

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

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

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

[tex]\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)[/tex]

și de asemenea că

[tex]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)[/tex]

Simplificând egalitatea cu [tex]\beta[/tex] se obține că

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

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

[tex]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) [/tex]

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

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.

curiosul

O altă modalitate de a analiza eroarea maximă de aproximare pentru [tex] \pi(n)\approx n\left [\prod_{k=1}^{i}\left(\frac{p_{k}-1}{p_{k}}\right )\right] [/tex] , unde [tex]p_{i}\leq \sqrt{n}< p_{i+1}[/tex] este următoarea.

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

[tex]\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}-[/tex]

[tex]-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}[/tex]

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

[tex]\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})[/tex]

[tex]\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})[/tex]

[tex]\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})[/tex]

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

iar de aici ar rezulta că

[tex]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)[/tex]

și ar demonstra evident inegalitatea

[tex]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][/tex]

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