Encadrement des premiers

christophe c · April 2020

J'ai des heures de vol en théorie des jeux à information parfaite. J'aimerais vous demander une borne effective pour la fonction célèbre:

$$ \pi :=[x\mapsto card([0,x]\cap NombresPremiers)]$$

afin d'élaborer des jeux pour enfants.

Bon, je sais bien pour l'avoir lu souvent sur le forum qu'on a, pour $x\to +\infty$,

$\pi(x) ln(x) / x \to 1$

$\pi(x) li(x) \to 1 $

et donc

$\pi (x) \times (1+1/2+1/3+1/4+....+1/PartieEntiere(x)) /x \to 1$

cette dernière étant intéressante parce que les autres fonctions proviennent de l'analyse, mais, y a-t-il, même un peu lâche (mais pas trop quand-même), des bornes $f,g$ accessibles aux enfants :

$$ \forall n\in \N: f(n)\leq \pi(n) \leq g(n)$$

?

Merci par avance.

Les jeux offrent d'amusantes preuves d'existence complètement non effectives, donc "exciting". Pour n'importe quel $A$ dit de parties, et $h: A\to S:=[1;2;3;4;5;...;n]$, il existe un (unique) $p\in S$ tel que

Lea gagne à coup sûr $h(partie)\leq p$ et Bob gagne à coup sûr $h(partie)\geq p$.

Evidemment, en pratique, dans $99.9\%$ des jeux, personne ne connait le $p$ du fait de l'alternance de quantificateurs qui est l'ADN des jeux.

noix de totos · April 2020

Pour tout réel $x > 0$, $\pi(x) < 1,26 \frac{x}{\log x}$ et pour tout $x \geqslant 17$, $\pi(x) \geqslant \frac{x}{\log x}$.

Si le logarithme ne convient pas, tu peux le remplacer comme tu l'as fait, par exemple
$$\frac{1}{2} \sum_{k=1}^n \frac{1}{k} \leqslant \log n \leqslant \sum_{k=1}^n \frac{1}{k} \quad \left( n \geqslant 2 \right).$$
Ainsi, pour $n \geqslant 17$
$$n \left(\sum_{k=1}^n \frac{1}{k}\right)^{-1} \leqslant \pi(n) \leqslant 2,52 n \left(\sum_{k=1}^n \frac{1}{k} \right)^{-1}.$$
Ça va, ça ?

christophe c · April 2020

Ah oui, c'est vraiment génial, ça fait un bel encadrement de Schmilblick entre n et 3n (le 2.52, dans un premier temps, on va dire que.... :-D )

Grand MERCI!

noix de totos · April 2020

De rien. Tu te mets donc à l'arithmétique, maintenant ?

christophe c · April 2020

Pardon, je me sers de ce post, comme je l'ai mis dans shtam, pour évaluer des écritures:

$u_n:=n / (1+1/2+..+1/n)$
[size=x-small]u_{n+1} = (n+1) \times ((n/u_n) + 1/(n+1)) =
((n^2+n) / u_n )+ 1. Ah ouais, quand-même :-S[/size]
$ (1+1/2+..+1/n) = n / u_n$

$1+1/2+..+1/(n+1) = n / u_n + (1/(n+1)) = (n(n+1) + u_n ) / ((n+1) u_n) $

$u_{n+1} = \frac{n+1}{n / u_n + (1/(n+1))}$

$u_{n+1} = \frac{(n+1) \times [ (n+1) u_n ] }{n(n+1) + u_n }$

$u_{n+1} = \frac{ (n+1)^2 u_n }{n(n+1) + (n+1)(u_n /(n+1)) }$

$u_{n+1} = \frac{ (n+1) u_n }{n+ (u_n /(n+1)) }$

$u_{n+1} = \frac{ (nu_n + u_n }{n + (u_n /(n+1)) }$

$u_{n+1} = \frac{ ((n+1)nu_n + (n+1)u_n }{(n+1)n + u_n }$

$u_{n+1} = \frac{ ((n+1)^2u_n }{(n+1)n + u_n }$

$u_{n+1} = \frac{ (n+1)^3 n + (n+1)^2u_n - (n+1)^3 n }{(n+1)n + u_n }$

$u_{n+1} = (n+1)^2 - \frac{ (n+1)^3 n }{(n+1)n + u_n }$

Ouais, bref, en tout cas, merci à MC, j'avais fait une coquille (et peut-être encore)

christophe c · April 2020

Sans vouloir te décevoir, non, car je ne suis pas ADN-compatible avec. Je me mets à synthétiser (doucement) ce que j'ai "globalement" compris des indécidabilités diverses mais aussi des DECIDABILITES diverses, pour tenter des classifications, ou des traductions de problèmes en d'autres, afin de permettre de dire à Dupont de la spécialité X que le problème de Durand de la spécialité Y est équivalent au problème P de la spécialité X.

christophe c · April 2020

Bon je suis incapable bien évidemment de relier ça avec $ln$, mais je viens de mettre un point d'honneur à me faire une heuristique à la rigueur prés.

La voici (vivie shtam): quand $a,b$ sont supergrands et superproche, ils ne partagent que trop peu de diviseurs premiers, et donc $f(ab)=f(a)+f(b)$ où $f$ envoie $x$ sur le nombre de diviseurs premier de $x$. Après par connexité "ultrafltrante", et compactification, on a bien une densité locale en $\frac{1}{f(x)}$ et donc $\pi (x) = \int (1/f(x))dx $. Mais je ne vois aucune raison pour trouver le $a$ tel que $f= a\times ln$ (qui selon le TNP vaut 1)

Menfin, ça me va pour ce soir, j'ai l'impression d'être moins dépendant de messages divins :-D

noix de totos · April 2020

Christophe C a écrit:

Mais je ne vois aucune raison pour trouver le $a$ tel que...

Il n'y a effectivement aucune raison : si tu comptes tes facteurs premiers sans multiplicité (ou avec, ça ne change pas grand-chose ici, de toute façon), ta fonction $f$ n'est rien d'autre que celle que l'on nomme chez nous $\omega$, définie sur $\mathbb{Z}_{\geqslant 1}$ par $\omega(1) = 0$ et, pour tout enier $n \geqslant 2$, $\omega(n) = \displaystyle \sum_{p \mid n} 1$, où je rappelle que, chez nous, tout produit ou somme indicé par $p$ ne porte que sur les nombres premiers.

Il est facile de voir que cette fonction arithmétique est additive, c'est-à-dire que $\omega(mn) = \omega(m) + \omega(n)$ dès que $\textrm{pgcd}(m,n) = 1$ (pour les puristes, elle est même fortement additive, i.e. additive plus l'option $\omega(p^a) = \omega(p)$), mais elle n'a pas grand-chose à voir avec le logarithme, ayant un comportement beaucoup plus erratique.

La seule chose que l'on puisse vraiment dire, c'est trouver une majoration qui soit "au plus près" de son comportement. Il y a plus de 30 ans, Robin montrait que, pour tout entier $n \geqslant 3$
$$\omega(n) \leqslant 1,3841 \frac{\log n}{\log \log n}.$$
C'est le seul lien qu'on peut lui trouver avec le $\log$ de manière formelle.

christophe c · April 2020

Merci beaucoup. C'est bizarre, je suis relativement étonné, car du fait que j'ai "volontairement" négligé les multiplicités dans mon heuristique (ie le fait que compter un même nombre plusieurs fois), je l'aurais vu plus grande $log(n)$ et non pas plus petite.

Un premier $p$ est compté $n/p$ fois, lorsque je prend la somme des $\omega(i), i\leq n$. Donc cette somme donne non pas a priori le nombre de nombres premiers plus petits que $n$, mais le nombre obtenue quand on additionne les $n/p$ (je ne sais pourquoi, j'avais fait "fois p")

(Edit: grosse bêtise $\to$ p\times (n/p) = n )

quand $p$ parcourt les premiers sous $n$, autrement dit la somme des $1/p$, le tout fois $n$ à la fin.

Si, faisant semblant de "penser nombres réels et continuité", je dérive

$$x\mapsto (ln(ln(x))) x $$

(ici je consulte l'oracle forum-souvenirs et sort du chapeau que la somme précédente tourne autour de $ln\circ ln$

Ca donne :

$$ \frac{1}{xln(x)} \times x + ln(ln(x)) = \frac{1}{ln(x)} + ln(ln(x)) $$

J'ai un peu réfléchi, mais faut que je poste pour pouvoir voir la fenêtre d'avant du post de NdT

Bon, à suivre, je pense que comme d'habitude j'ai buggué vues les croissances que je suis en train d'évoquer, je vais y réfléchir sans poster intempestivement à la volée ( :-X j'en ai raz le bol de mal calculer, je comprends la passion de Rescassol par exemple pour le calcul, mais je dois regarder assis dans les gradins)

christophe c · April 2020

Ah mais que je suis bête. Je vais éditer, pardon !!!!!

christophe c · April 2020

Et bin, oui, il y a une étrange division par $ln(ln(x))$. Bon après "me souvenir que" la somme des $1/p$ quand $p$ parcourt les premiers plus petits que $n$ tourne à $ln(ln(n))$, ce n'est pas ce qu'on peut appeler un fort argument scientifique :-D

noix de totos · April 2020

Ce n'est peut-être pas un "fort argument scientifique", mais c'est quand même la bonne raison. Donc, au moins heuristiquement, tu as la bonne explication, ce qui est déjà pas mal.

Et comme j'ai repris la main, la fonction "duale" de $\omega$ est la fonction $\Omega$, définie par $\Omega(1)=0$ et, pour tout entier $n \geqslant 2$, $\Omega(n)$ est le nombre de facteurs premiers de $n$ comptés avec leurs multiplicités.

Exemple. $\omega(8) =1$ mais $\Omega(8)=3$.

Cette fonction se rapproche plus du logarithme puisqu'elle est complètement additive, c'est-à-dire que la relation $\Omega(mn)= \Omega(m) + \Omega(n)$ est vraie quels que soient les entiers positifs $m$ et $n$, qu'ils soient premiers entre eux ou non. Et là, pour le coup, seule la majoration triviale
$$\Omega(n) \leqslant \frac{\log n}{\log 2}$$
est disponible. Elle est d'ailleurs atteinte si $n$ est une puissance de $2$.

christophe c · April 2020

Merci beaucoup! Au fond, c'est très attirant cette science, parce qu'on y gère de manière industrielle des preuves non constructives (ie on prouve qu'une proba n'est pas nulle et ça donne une existence, :-D tout ce que détestent les constructivistes et que j'adore!!!)

christophe c · April 2020

Oups, je m'aperçois d'un malentendu, je ne parlais pas de cette multiplicité là.

Je parlais du nombre de fois où un nombre premier $p<n$ est compté quand on somme les $\omega(i)$ pour $i\leq n$.

Si je note $S(n)$ cette somme, alors pour le coup, on a vraiment $S$ qui croît comme $K \int ln$ heuristiquement. Où je n'ai pas vraiment d'heuristique pour trouver $K$.

noix de totos · April 2020

Pas sûr que je comprenne bien ton problème, mais, pour info
$$\omega(1) + \dotsb + \omega(n) = n \left(\log \log n + 0,261497 \dotsc \right) + O \left( \frac{n}{\log n} \right).$$

Poirot · April 2020

CC a écrit:

Je parlais du nombre de fois où un nombre premier $p<n$ est compté quand on somme les $\omega(i)$ pour $i \leq n$n.

J'interprète ça comme le nombre d'entiers $\leq n$ divisibles par $p$ et dans ce cas c'est $\left\lfloor \frac{n}{p}\right\rfloor$ mais ça me semble trop simple et pas grand-chose à voir avec les estimations dont il parle. Si on somme ça sur tous les $p \leq n$, on tombe sur quelque chose d'équivalent à $n \log \log n$, j'imagine que c'est comme ça qu'on montre la dernière estimation donnée par ndt.

noix de totos · April 2020

Oui, c'est ce que j'ai pensé aussi.

christophe c · April 2020

Je confirme et merci pour l'évaluation. Et oui, je me suis mal exprimé, j'aurais dû évoquer "un graphe d'adjacence", avec des arêtes ORIENTEES, flèches allant d'un nombre premier à ses multiples. La somme est alors la somme des degrés du graphes (où on ne compte, pour chaque sommet que les flèches entrantes).

:-D Ca montre aussi par commutativité ce que donnent le comptage des flèches sortantes. Bon, bof, je ne sais pas si c'est souvent évoqué.

C'est marrant j'ai quand-même pas été terrible dans mon estimation (que je voyais en $x\mapsto xln(x)$ plutôt qu'en $x\mapsto xln(ln(x)$)

Ca montre que mon approche "heuristique" est encore très grossière.

De toute façon, il "se trouve" qu'on parle presque de la même chose essentiellement, puisque les facteurs premiers de $a\times b$, ont leur puissances ajoutées quand ils sont en commun et que la petite $\omega$ à laquelle je m'intéressais est effectivement "non très pertinente"

christophe c · April 2020

Je shtamise quelques minutes. Je voudrais montrer comment je viens de réaliser seul que "ça a des chances" d'être facile de trouver si un nombre est premier (bon, on sait que ça l'est depuis longtemps, mais ce sont des articles de recherche)

$A:=\Z/n\Z$, c'est un anneau fini. Vous pouvez "vivre dedans quelques temps et vous éclater. (Disons que $n$ est un nombre de 1000 chiffres).L'idée: vous faites semblant de croire que c'est un corps et vous tirez dessus capricieusement.

Je rappelle que PGCD est une opération très rapide.

Tout d'abord, vous vous placez aux alentours de la racine carrée de $n$, vous prenez un nombre $a,b$, et vous décrétez qu'ils
que $a+1,b+1$ sont inverses l'un de l'autre, ce qui vous fait écrire $ab+a+b=0$.. Cool, du coup $(b+1)a = -b$? Vous inversez $b+1$ avec $-c$, ce qui donne $a = bc$. En inversant $a$, via $d$, vous obtenez $1 = bcd$.

On vient de se trouver en quelque secondes tout plein de produits qui donne $1$ avec des facteurs aux alentours de la racine carrée de $n$. On peut aussi prendre un petit nombre $u$ disons tel que disons $2^u$ proche de $n$. On inverse, allez, disons $2^u-1$ au hasard :-D via $e$, ce qui donne $2^ue = 1+e$. Comme souvent, $2^u-1$ est divisible par plein de mondes (impairs), on vient d'inverser à la pelle tout tout plein de petits nombres dans $A$.

Franchement, c'est reposant. Rescassol pourrait apprécier. On continue comme ça jusqu'à tomber sur $0=1$ et on a décomposer $n$.

Je n'ai aucune idée de si l'algo probabiliste suit une idée de ce genre, mais franchement ça a le mérite d'être promu comme un truc reposant et non comme un galérien devoir d'école.

christophe c · April 2020

Cette façon de "se tourner les pouces" sans vraiment "penser" est marrante et semble d'ailleurs mettre quelque peu en danger la conjecture des premiers jumeaux

Prenons $a$ un grand nombre et appelons $b:=2a+1$. Amusons-nous à supposer $b$ premier. Soit $x$ proche de la racine carrée de $b$.

Il est inversible, soit $y$ son inverse modulo $b$. Ca donne $xy=1 = 2a$, avec $x,y$ proches en taille de $\sqrt{b}$ (au signe près)

J'ai donc factorisé $b-1$ ou $b+1=2a$ sans fatigue (sous l'hypothèse $b$ premier, ce qui permet de la mettre en disjonction "ou $b$ n'st pas premier") avec des nombres dont la taille est de l'ordre de $\sqrt{b}$ sauf erreur, c'est à dire très loin tous deux de $a,b$. Bin, sauf erreur, je suis bien content.

christophe c · April 2020

J'en reviens à "mon premier théorème officiel d'arithmétique", car je m'interroge, je pense qu'il peut y avoir une erreur bien cachée ci-dessus.

Je viens de prouver :

Théorème: pour tout nombre impair de 1000* chiffres $a$, je sais ou bien l'écrire comme un produit non trivial, ou bien écrire l'un des nombres $a+1; a-1$ sous forme d'un produit de deux nombres ayant environ 500 chiffres.

J'ai du mal à croire que je viens de prouver ça juste en écrivant des choses au hasard :-S . Si c'est vrai, ça ne peut qu'être connu, donc merci de me donner le nom de ce prodige étrange, apparemment peu diffusé par les arithméticiens. Et sinon, je rédigerai une preuve soignée pour voir si erreur

* j'ai pris 10000, mais ça peut être n'importe quoi d'assez grand.

Je ne sais pas si c'est vrai ou pas, mais l'erreur, elle, était bien grosse 8-)

christophe c · April 2020

:-S Appliqué à $N!$ ça donne que je factorise sans peine, ou bien $N! + 3$ ou trouve sans peine un nombre premier plus grand que $N$. donc doit y avoir une erreur.