Engendrer des nombres premiers

Forums

» » » »

Engendrer des nombres premiers

Posté le 27-02-10 à 16:39

Posté par zakijam

Bonsoir

Je chereche des fonctions pour engendrer le maximum possible de nombres premiers.
Par exemple, la fonction d'Euler $f(n)=n^2-n+41$ qui donne 41 nombres premiers pour n= 1, 2, ..., 40
J'ai trouvé différentes polynômes qui donnent des nombres premiers pour des valeurs consécutives de n.

Maintenant, je voudrais bien trouver des fonctions quelconques, (pas des polynômes), qui donnent des nombres premiers , en faisant appel à la fonction partie entièr par exemple.
Je connais celle de Mills, de Wright, et de Wilson. Mais elles ne sont pas efficaces. Une application qui les utilise ne fonctionne pas rapidement.

Merci d'avance.

re : Engendrer des nombres premiers

Posté le 28-02-10 à 00:46

Posté par Foxdevil

Bonsoir,

Tu est très informé sur le sujet. Je vais te donner d'autres formules mais je tiens à te prévenir que l'intérêt pratique de n'importe quelle formule que nous connaissons actuellement est très limité. Ce n'est pas pour rien que les nombres premiers sont le fantasme arithmétique de l'humanité depuis la nuit des temps! On dirait que tu veux utiliser ces formules dans une application....ça a peu de chance de se révéler utile, car bien que ces formules soient belles, elles sont inutilisables et il y a franchement peu d'espoir qu'elles le soient un jour.

On a démontré qu'il existe une constante L (constante de Liouville-Erdös) telle que $[L\times 10^{n^{2}}]-[L\times10^{{(n-1)}^{2}}]\times10^{2n-1}$ (où [] est la partie entière) "génère" le n-ième nombre premier pour tout $n\ge1$ . La constante en question est L=0,200300005000000700000001100000000013....(chaque nombre premier est à la place n² après la virgule). Cette formule est sans intérêt car pour calculer les nombres premiers, on nécessite la constante L. Et pour avoir L, nous devons connaître les nombres premiers.....Cette formule ne fait que les extraire et ne génère rien du tout.

Une formule d'un passionné français nommé R.Yéléhada:
$t(n)=2+n[\frac{1}{1+\bigsum_{i=2}^{n+1}~[\frac{n+2}{i}-[\frac{n+1}{i}]]}]$ , n positif.
Formule améliorée en (grâce au théorème de théorème de Wilson) par J Minac en:
$t(n)=2+n[\frac{(n+1)!+1}{n+2}-[\frac{(n+1)!}{n+2}]]$ .
Ils ont encore tous les deux imaginé une autre formule, plus remarquable:
$p_n=1+\bigsum_{m=1}^{2^{n}}~[[\frac{n}{1+\bigsum_{j=2}^m~[\frac{(j-1)!+1}{j}-[\frac{(j-1)!}{j}]]}]^{\frac{1}{n}}]$
Et enfin dans le genre formule de taré, on a celle-ci (la justification de la formule n'est pas hors de portée):
$p_n=\bigsum_{m=2}^{n^2+1}~m\times({\frac{[\frac{\bigsum_{i=2}^m~[\frac{(i-1)!+1}{i}-[\frac{(i-1)!}{i}]]}{n}]+1-|[\frac{\bigsum_{i=2}^m~[\frac{(i-1)!+1}{i}-[\frac{(i-1)!}{i}]]}{n}]-1|}{2}-\frac{[\frac{\bigsum_{i=2}^{m-1}~[\frac{(i-1)!+1}{i}-[\frac{(i-1)!}{i}]]}{n}]+1-|[\frac{\bigsum_{i=2}^{m-1}~[\frac{(i-1)!+1}{i}-[\frac{(i-1)!}{i}]]}{n}]-1|}{2}})$ .

Où sinon niveau logique on a:
$p_n=min$ {m|#{ $i | 2\le i \le m$ et $\forall h (2 \le h \le i-1 \Longrightarrow i \neq h[\frac{i}{h}])$ }=n}.

Sinon, on a les formules de la fonction qui compte les nombres premiers inférieur à un entier m donné:
$\pi(m)=\bigsum_{j=2}^m~\frac{sin^2(\frac{\pi((j-1)!)^2}{j})}{sin^2(\frac{\pi}{j})}$
et
$\pi(m)=-1+\bigsum_{j=1}^m~[cos^2(\frac{\pi((j-1)!+1)}{j})]$

Il y a des formules approchées de la fonction de compte pour un réel x donné, dont certaines sont très précises (ce sont les formules qui auraient le plus d'utilité du point de vue pratique), mais qui sont liée à la très célèbre hypothèse de Riemann....

J'ai pris tout ça dans un livre très intéressant de Jean-Paul Delahaye dont je te donne la référence:

re : Engendrer des nombres premiers

Posté le 28-02-10 à 02:40

Posté par zakijam

Merci beaucoup, Mr Foxdevil. Comme vous l'avez deviné, je voudrais les utiliser dans une application. Les relations que vous venez d'écrire donnent des résultats lentement et les calculs s'arrêtent après un certain n.
Je voudrais bien savoir, est-ce qu'il y a d'autres relations utilisables (Computable)?

Merci encore une fois

re : Engendrer des nombres premiers

Posté le 28-02-10 à 20:13

Posté par Foxdevil

Non justement! Les formules de nombres premiers sont foison (bien qu'on pense généralement le contraire). Mais il n'en existe pas de connue qui soit utilisable. Soit ce cache un artifice derrière ces formules (exemple de liouville-erdös) soit elles sont trop lourdes. Ce n'est pas pour rien que l'hypothèse de Riemann a du subir les assauts répétés des plus grands mateux! Elle fournit la meilleur approximation du nombre de nombres premiers inférieur à un réel donné. Mais en dehors des approximations (qui seules peuvent avoir un quelconque intérêt pratique), il n'y a que des formules théoriques belles mais complètement inutilisables (à cause des sommes, factorielles etc...).

Tu peux à la rigueur en trouver d'à peine meilleures, mais ça ne sera pas un gros gain (globalement ça reste toujours un problème de calcul trop lourd)......et je n'en connais pas davantage....

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster

Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.

Ce topic

Imprimer
Réduire / Agrandir
Pour plus d'options, connectez vous !
Fiches de maths

arithmétique en post-bac
1 fiches de mathématiques sur "arithmétique" en post-bac disponibles.