Existe-t-il une formule pour calculer tous les nombres premiers ?

[invite96929ba3]

J'avais entendu dire, que celle ci n'avait pas encore était trouvé, est ce vrai ?
-----

[Médiat]

Bonjour,

Il existe de nombreuses formules donnant la liste des nombres premiers, malheureusement, le temps de calcul est "terrifiant"

Formule de Minác et Willans par exemple.

Cf. : http://www.cnrs.fr/Cnrspresse/math2000/pdf/Maths10.pdf

Voir aussi la formule "Fractran" de Conway, ou un polynôme a 26 (si je me souviens bien) variables

[Deedee81]

Salut,

Voir aussi :
https://fr.wikipedia.org/wiki/Formul...mbres_premiers

[invite7c2548ec]

Bonjour;

Ou la plus célèbre Fonction zêta de Riemann.

Cordialement

[A voir en vidéo sur Futura]

[Deedee81]

Ou la plus célèbre Fonction zêta de Riemann.

Le lien est évident et connu, mais comment tu calcules la suite des nombres premiers en utilisant la fonction zêta de Riemann (puisque c'était ça la question, une formule pour calculer tous les nombres premiers) ????
Y a une méthode connue pour faire ça ? A partir des zéros de la fonction peut-être ?

[invite50cd5700]

Exact, c'est à partir des 0, mais on est très loin d'avoir résolu cette question,nous n'avons que la conjecture de Riemann où chaque zero aurait une partie réelle égale à -1/2

[Deedee81]

Salut,

Exact, c'est à partir des 0

D'accord merci.

Formule certainement plus efficace que celles un peu artificielle donnée plus haut. Mais aussi beaucoup plus difficile à calculer.

[Médiat]

Bonjour,

Je connais certains liens (il y en a de nombreux) de la fonction Zêta de Riemann avec les nombres premiers, en particulier sur leur répartition, mais comment cette fonction donne-t-elle une formule listant les nombres premiers ?

[Deedee81]

mais comment cette fonction donne-t-elle une formule listant les nombres premiers ?

Xardas54 disait qu'il y avait un lien avec les zéros de la fonction. Ce n'est pas le cas ?

[invite9dc7b526]

Si il y a bien un lien entre la liste des zéros non triviaux et la liste des nombres premiers. Mais je ne pense pas qu'il y ait une façon simple de calculer ces zéros donc on ne gagne rien.

[invite046e427d]

Bonjour,

Des doutes (preuve de l'HR et la liste de nombres premiers) sont évoqués dans cette discussions :
http://forums.futura-sciences.com/ma...-premiers.html
En ce qui me concerne je ne peux pas aller plus avant, je suis trop amateur.

Cdt.

[Médiat]

Bonjour,

Je repose ma question autrement : comment, à partir de la ion Zêta de Riemann, est-ce que je peux établir la liste des nombres premiers (à partir des solutions de Minac et Willans, de Wilson ou de Conway, et même du polynome à 26 variables (j'ai vérifié, c'est bien 26), je sais comment faire (même si c'est long)) mais avec Zêta, je ne sais pas (je parle d'un moyen pratique, sans tenir compte du temps de traitement) ...

[Deedee81]

Si il y a bien un lien entre la liste des zéros non triviaux et la liste des nombres premiers. Mais je ne pense pas qu'il y ait une façon simple de calculer ces zéros donc on ne gagne rien.

Est-il possible d'expliquer ce lien ? (ou s'il y a un site ? Wikipedia peut-être ? Mais pas un truc de 50 pages avant de voir le lien sinon je n'aurai pas le temps.... arg, j'ai réunion dans 10 minutes en plus, j'avais oublié, zuuuttt. Bon et bien, à demain.

[andretou]

Exact, c'est à partir des 0, mais on est très loin d'avoir résolu cette question,nous n'avons que la conjecture de Riemann où chaque zero aurait une partie réelle égale à -1/2

Si la conjecture de Riemann venait à être démontrée, que saurions-nous alors de plus sur les nombres premiers ?

[Deedee81]

Si la conjecture de Riemann venait à être démontrée, que saurions-nous alors de plus sur les nombres premiers ?

Sans doute pas grand chose en soi car la plupart du temps on pense qu'elle est correcte.
Donc ça transformerait simplement automatiquement en théorie une série de conjecture utilisant celle de Riemann.

Par contre il y a fort à parier que les outils développé pour démontrer la conjecture seraient intéressant pour eux-mêmes et apporteraient beaucoup. C'est exactement ce qui c'est produit avec Fermat-Wiles.

[invite9dc7b526]

Est-il possible d'expliquer ce lien ? (ou s'il y a un site ? Wikipedia peut-être ? Mais pas un truc de 50 pages avant de voir le lien sinon je n'aurai pas le temps.... arg, j'ai réunion dans 10 minutes en plus, j'avais oublié, zuuuttt. Bon et bien, à demain.

ce que je comprends, c'est qu'il n'y a pas de correspondance biunivoque "naturelle" entre les zéros de zeta et les nombres premiers (ce serait trop simple) mais qu'il existe une approximation de la fonction pi(x) (le nombre de premiers plus petits que x) qui est un développement en série dont chaque terme dépend d'un zéro. Si on a la liste complète (infinie) des zéros on connaît pi(x) parfaitement et donc on a la liste complète des nombres premiers. Si on ne connaît que les premiers zéros on a une approximation qui est suffisamment fine pour qu'on connaisse un certain nombre de premiers, mais pas les plus petits. Bref, déterminer les zéros séquentiellement produit des nombres premiers mais pas dans l'ordre. Donc ce n'est pas une méthode pratique de détermination des nombres premiers.

tout ce qui est écrit plus haut est à prendre avec précaution, c'est ce que je comprends de diverses lectures mais je suis loin d'être spécialiste de la question.

[andretou]

Sans doute pas grand chose en soi car la plupart du temps on pense qu'elle est correcte.
Donc ça transformerait simplement automatiquement en théorie une série de conjecture utilisant celle de Riemann.

Par contre il y a fort à parier que les outils développé pour démontrer la conjecture seraient intéressant pour eux-mêmes et apporteraient beaucoup. C'est exactement ce qui c'est produit avec Fermat-Wiles.

Actuellement, je crois comprendre qu'on connaît certaines formules qui nous donnent certains nombres premiers, mais on n'a pas de formule permettant de calculer TOUS les nombres premiers.
Si la conjecture de Riemann était démontrée, cela permettrait-il au moins de savoir si une telle formule existe ?

[Médiat]

on n'a pas de formule permettant de calculer TOUS les nombres premiers.

Vous n'avez pas lu le post #2 ?

[invite046e427d]

Salut,

Par contre il y a fort à parier que les outils développé pour démontrer la conjecture seraient intéressant pour eux-mêmes et apporteraient beaucoup. C'est exactement ce qui c'est produit avec Fermat-Wiles.

Je crois aussi que pour une question telle que l'HR, l'essentiel n'est pas vraiment la conclusion (les 0 sont tous alignés ou pas) mais le comment de cette conclusion, c'est-à dire les "outils développés" surtout s'ils sont nouveaux.
Cdt.

[andretou]

Vous n'avez pas lu le post #2 ?

Apparemment la seule formule qui donne tous les nombres premiers de manière exhaustive est celle de Minác et Willans dont il est dit qu'elle n'est pas utilisable...
Je reformule ma question : actuellement, je crois comprendre qu'on n'a pas de formule EFFICACE permettant de calculer TOUS les nombres premiers.
Si la conjecture de Riemann était démontrée, cela permettrait-il au moins de savoir si une telle formule efficace existe ?

[andretou]

Apparemment la seule formule qui donne tous les nombres premiers de manière exhaustive est celle de Minác et Willans dont il est dit qu'elle n'est pas utilisable...
Je reformule ma question : actuellement, je crois comprendre qu'on n'a pas de formule EFFICACE permettant de calculer TOUS les nombres premiers.
Si la conjecture de Riemann était démontrée, cela permettrait-il au moins de savoir si une telle formule efficace existe ?

En fait on sait théoriquement les calculer, mais en pratique on n'y arrive pas. Est-ce correct ?

[Seirios]

Je reformule ma question : actuellement, je crois comprendre qu'on n'a pas de formule EFFICACE permettant de calculer TOUS les nombres premiers.
Si la conjecture de Riemann était démontrée, cela permettrait-il au moins de savoir si une telle formule efficace existe ?

Cela dépendrait de la démonstration, comme il a été dit précédemment. À partir de la conclusion de la conjecture seule, on n'en déduirait pas grand chose. Il faudrait surtout savoir comment sont répartis ces zéros le long de cette fameuse droite.

En fait on sait théoriquement les calculer, mais en pratique on n'y arrive pas. Est-ce correct ?

Disons que les calculs nécessaires sont tellement longs qu'ils en perdent leur intérêt.

[invitebd98b571]

Apparemment la seule formule qui donne tous les nombres premiers de manière exhaustive est celle de Minác et Willans

Non, tout le monde peut inventer une formule, pas de souci pour cela. Par exemple, le n-ième nombre premier $P_n$ est

où
et prolongée par continuité

[andretou]

Non, tout le monde peut inventer une formule, pas de souci pour cela. Par exemple, le n-ième nombre premier $P_n$ est

où
et prolongée par continuité

C'est quand même assez extraordinaire de parvenir à relier les nombres premiers à la géométrie (par la fonction sinus) ! Qui a trouvé cette formule ? Comment arrive-t-on à un tel résultat ?

[Médiat]

C'est quand même assez extraordinaire de parvenir à relier les nombres premiers à la géométrie (par la fonction sinus) !

Pour x un nombre entier, les valeurs du sinus sont assez limitées et n'ont pas grand chose à voir avec la géométrie

[Deedee81]

Salut,

Une étude un peu bête :

Si l'on étend la définition de "formule" à "fonction programmée", il devient facile de donner une ch'tit formule donnant dans l'ordre tous les nombres premiers (même avec un algo simpliste et peu efficace, ça débite quand même assez bien).
Existe-t-il une définition officielle en math de "formule" ?

[invitebd98b571]

La formule que j'ai citée n'est pas compliquée : il faut juste savoir que, pour tout entier M >1, la somme (M-1)!+1 est multiple de M si et seulement M est premier.
La fonction f est là pour indiquer (de manière booléenne) si M est premier, la fonction g est là pour indiquer (de manière booléenne) si M est le n-ième.
Quand les deux conditions sont réunies, alors M.1.1 = M est le n-ème nombre premier.
Tous les termes de la série portant sur M>1 sont nuls sauf un seul, valant le n-ème nombre premier.
Il n'y aucun mystère, un peu d'astuce éventuellement, et peu d'intérêt dans tout ça.

[Médiat]

Bonjour Deedee,

Les logiciens ont répondu à cette question : http://forums.futura-sciences.com/ma...ml#post2553410

[Deedee81]

Les logiciens ont répondu à cette question : http://forums.futura-sciences.com/ma...ml#post2553410

Donc, selon ce que j'ai lu, pas d'itération par exemple. Mais la récursivité est autorisée il me semble, non ?
(il est possible de remplacer toute procédure itérative par une récursive)
Doit y avoir moyen de transformer un ch'tit programme en formule correctement formatée (c'est d'ailleurs dans l'esprit de la formule donnée par Prou_)

[Médiat]

Je donne un exemple dans AP (tiré de mon document sur l'arithmétique, http://forums.futura-sciences.com/ma...ml#post3958163) :

L'exponentiation peut être définie par récurrence : et

Et que l'on peut redéfinir par une formule

Soit le prédicat dont la sémantique est et défini par :





Où est la fonction de Gödel :