Pi(n)

Averse
Averse
dans Arithmétique
Bonjour, $\pi(n)$ est le nombre de nombres premiers $\leq n$. Je ne comprends pas comment passer de $\pi(2n)-\pi(n)=O(n/\log(n))$ à $\pi(n)=O(n/\log(n))$.
La seule indication que j'ai est une majoration de $\pi(2^k)\leq C(\frac{2^k}{k}+\ldots+2+1)\leq\ldots\leq 4C\frac{2^k}{k}+C2^{k/2}$.

En fait en appliquant $\pi(2n)-\pi(n)\leq\frac{n\log(4)}{\log(n)}$ je trouve même : $\pi(2^k)\leq \frac{\log(4)}{\log(2)}\left(\frac{2^{k-1}}{k-1}+\ldots+2\right)+1$
Mais comment estimer $\pi(n)$ ensuite ?

Réponses

  • bosio frederic0
    bosio frederic0
    L'inégalite $\pi (2^k ) \leq 4C\frac{2^k }{k} + C. 2^{\frac{k}{2}}$ te donne immediatement le résultat. En effet, $2^{\frac{k}{2}}$ est un $o(\frac{2^k }{k})$, et il suffit pour un entier naturel quelconque $n$ de majorer $\pi (n)$ par $\pi $ de la puissance de $2$ qui lui est immédiatement supérieure.

    Remarque : $\frac{\ln (4)}{\ln (2)} = 2$.
  • Averse
    Averse
    Mais comment passer d'un $O(2^k/k)$ à un $O(n/\log(n))$ ??
    On sait que $n<2^k$ donc $\log(n)<k\log(2)$ donc $k>\log(n)$. Zut ! Je ne vois pas comment conclure.
  • bosio frederic0
    bosio frederic0
    Utilise $2^{k-1} \leq n \leq 2^k $.
  • borde
    borde
    On a $\displaystyle {\pi(n) - \pi(n/2) \leqslant \frac {C_1n}{2 \ln (n/2)}}$. En remplaçant $n$ par $n/2$, $n/4$,...,$n/2^{k-1}$ avec $k = [\ln n / \ln 2]$ et en additionnant tout, il vient : $$\pi(n) \leqslant C_2 n \sum_{j=1}^{k-1} \frac {1}{2^j \ln(n/2^j)} + C_3,$$ et on découpe la somme à $[k/2]$ ce qui permet de conclure.

    Borde.
  • Averse
    Averse
    Bonjour Borde, merci de m'expliquer. Pourquoi $C_3$ ne dépend pas de $n$ ?


    Sinon je ne comprend pas comment le monsieur qui a écrit ce que je lis a pu obtenir la deuxième majoration :
    $$\pi(2^k)\leq C\left(\frac{2^k}{k}+\frac{2^{k-1}}{k-1}+\ldots+2+1\right)
    \leq 2C\left(\frac{2^k}{k}+\ldots+\frac{2^{k/2}}{k}\right)+C\left(2^{k/2-1}+\ldots+2+1\right)$$

    Etant donné que $k$ n'est même supposé divisible par $2$ ?!?!
  • Averse
    Averse
    En fait en suivant l'idée montrée par Borde on a :
    $$\pi(n)-\pi(n/2^k)\leq C_1n\sum_{j=1}^{k-1}\frac{1}{2^j\ln(n/2^j)}$$
  • borde
    borde
    Rappelle-toi que $k=[\ln n/ \ln2]$ de sorte que $\displaystyle {1 \leqslant \frac {n}{2^k} < 2}$, et donc $\pi(n/2^k) \leqslant \pi(2) = 1$.

    Borde.
  • Averse
    Averse
    En fait $\pi(n/2^k)=0$.

    Pourquoi découper la somme ensuite ??
  • borde
    borde
    Je n'ai pas eu le temps d'estimer cette somme directement. Mais comme la fonction $j \mapsto 1/\ln(n/2^j)$ est croissante, découper la somme en 2 permet de conserver ce logarithme au dénominateur (c'est une technique fréquemment employée).

    Borde.
  • Averse
    Averse
    On essaie donc de montrer avec ce découpage que cette somme est un $O(n/\ln(n))$ ?

    Désolé d'insister mais je ne vois pas du tout l'intérêt de couper la somme.

    D'autre part est-ce que la majoration que j'ai introduite est arrangeable en remplaçant $k/2$ par $[k/2]$ ?

    Et peut-on vraiment passer d'un $O(2^k/k)$ à un $O(n/\ln(n))$ ?

    Merci d'avance.
  • Averse
    Averse
    Peut-on dire que si $T=O(2^k/k)$ et $2^{k-1}\leq n\leq 2^k$, $k-1\leq\frac{\ln(n)}{ln(2)}\leq k$, alors $T\frac{\ln(n)}{n}\leq T\frac{k\ln(2)}{2^{k-1}}=2T\frac{k\ln(2)}{2^k}$ et cette dernière expression est bornée quand $k$ devient grand donc quand $n$ devient grand. Donc $T=O(n/\ln(n))$.

    Désolé mais j'ai du mal à faire des estimations certainement élémentaires.
  • borde
    borde
    L'intérêt de couper la somme en 2 est de conserver le log au dénominateur. En effet, une majoration brutale du $1/\ln(n/2^j)$ avec $j \leqslant k-1$ donnerait au mieux un terme $\ll 1$. En revanche, si $j \leqslant k/2$, alors $1/\ln(n/2^j) \ll 1/\ln(n/2^{k/2}) \ll 1/ \ln n$. L'autre somme s'estime trivialement.

    Borde.
  • Averse
    Averse
    Merci, je pense avoir compris comment ça marche dans les deux approches.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 4

OShine +3 Invités