Le 4 mai 2021, la plateforme Yahoo Questions/Réponses fermera. Elle est désormais accessible en mode lecture seule. Aucune modification ne sera apportée aux autres sites ou services Yahoo, ni à votre compte Yahoo. Vous trouverez plus d’informations sur l'arrêt de Yahoo Questions/Réponses et sur le téléchargement de vos données sur cette page d'aide.
2 3 5 7 11 13 17 19 23 29 31 37 ... Auriez-vous la formule pour trouver le Nième ?
formule(N) = Nième nombre premier.
@théo : non, non, non, pas un programme, une formule mathématique directe.
@théo : une formule qu'on peut calculer facilement sans machine, avec un papier et un crayon.
@Oyubir : en est-on seulement certain qu'une telle formule n'existe pas ? Ou alors, ne l'a-t-on pas encore trouvée ?
@Oyubir : extraordinaire réponse. J'étais persuadé qu'on ne savait pas si une formule en O(1) comme tu dis existait ou pas. Donc c'est acté qu'une formule "simple" n'existe réellement pas. Il y a forcément au minimum un algorithme (n étapes), pas une formule sans itération où il suffit de remplacer n pour trouver le nombre premier correspondant.
7 réponses
- oyubirLv 6il y a 3 semainesRéponse favorite
Ben non, une telle formule n'existe pas.
(Si toutefois on parle bien de la liste des nombres premiers. Sinon, difficile de deviner).
On sait que Π(x) ~ x/ln(x), Π(x) étant le nombre de premiers inférieurs ou égal au nombre x.
Comme si x est le nième premier, Π(x)=n-1, on en tire donc que
n ~ x/ln(x) ⇒ n ln(x) ~ x ⇒ n ln(n ln(x)) ~ x
⇒ x ~ n.ln(n) + n ln(ln(n)) ~ n.ln(n)
Donc, le nième nombre premier est de l'ordre de n.ln(n). Et cette formule devient de plus en plus précise (en proportion) au fur et à mesure que n augmente.
Il existe des formules encore plus précises (par exemple les formules de Dusart qui plaisent tant à Koussay, qui ne négligent pas le terme en n.ln(ln(n)), et proposent des encadrements).
Par exemple, la formule n.ln(n) dit que le 13e, qui suit 37, est 13×ln(13) = 33.34, ce qui est en dessous de la vérité (le théorème de Rosser dit que c'est toujours en dessous de la vérité), mais pas déconnant.
La formule un poil plus précise avec n.ln(ln(n)) elle dit que le 13e est 45,59, ce qui cette fois est un poil trop.
Si on veut un encadrement, la version la plus basique de Dusart dit que le nième nombre premier (mais en commençant à compter à 2, cad en faisant comme si 1 était le 1er nombre premier) est compris entre
n.ln(n) + n.ln(ln(n)) - n
et
n.ln(n) + n.ln(ln(n)) - n/2
Donc, pour notre 13e, (le 14e pour cette formule donc) ça donne un encadrement entre 36,53 et 43,53, donc entre 37 et 43.
Cette formule n'est valable qu'à partir de n=4 (mais en dessous, on les connait par coeur).
Il existe des tas de variantes, de plus en plus précises, mais valables seulement au delà d'un certain seuil. Par exemple, pour tout n au delà de 40000, on sait que le nième nombre premier est compris entre
n.ln(n) + n.ln(ln(n)) - n
et
n.ln(n) + n.ln(ln(n)) - 0,948n
Ce qui ne fait donc qu'une marge d'erreur de ±2,6% autour du centre de cet intervalle.
Mais bon, non, il n'existe pas de formule permettant d'avoir le nième nombre premier. Seulement des tas de formules permettant de savoir plus ou moins précisément son ordre de grandeur.
EDIT (RÉPONSE À LA MAJ) :
Je voulais dire, par "n'existe pas", que personne ne peut répondre. Elle n'a pas été trouvée.
(Donc ce n'est pas seulement que personne sur Yahoo connait la formule. C'est qu'il n'y a pas de formule).
Sinon, on est certain qu'elle existe, d'une certaine façon.
Ce n'est pas un problème indécidable ou je ne sais quoi. La question "quel est le Nième nombre premier" a une réponse. Il suffit de compter.
La vraie question, c'est "y a-t-il une formule plus simple".
C'est plus un problème d'algorithmique. Combien d'étapes de calcul sont nécessaires pour dire quel est le nième nombre premier.
Et ça, et ben, on ne sait pas dire vraiment à quel point c'est compliqué. Mais on sait qu'une formule donnant le nième nombre premier nécessite un nombre d'étapes au moins égal à n.
En d'autres termes, dans le sens que vous donnez au terme formule (cf la réponse que vous avez faite à Theo. Qui consiste à dire "non, je ne veux pas les compter, je veux avoir une formule pour trouver le nième directement", ce qui laisse entendre, avec un simple calcul qui prend un temps constant. "Suffit de remplacer n par sa valeur dans la formule". C'est ce qu'on appelle O(1) en théorie de la complexité), là, je peux répondre "ça n'existe pas".
Il existe une formule. Il en existe peut être une plus simple que de faire la liste des nombres premiers et de les compter (ce qui est une formule). Mais il n'en existe pas en O(1). Quoi qu'il arrive, il faudra itérer un truc, et faire n étapes de calcul.
- il y a 3 semaines
Personne n'a trouvé pour le moment. Il est probable qu'une telle formule n'existe pas.
Ici, il y a plusieurs propositions de formule comme quoi aucune ne fait autorité...
Mais le plus incroyable est que l'on dit qu'il y aurait une infinité de nombre premiers.
- ƒritz le KaT ☮Lv 7il y a 2 semaines
Si le chiffre proposé n 'est pas divisible par tous les chiffres qui le précédent il est considéré comme premier .
Voilà la formule .
Attelle toi à ton crayon et ton papier .
Si le chiffre est par exemple 7583
je le divise par tous les chiffres entre 1 et 7583
C 'est la formule la plus simple .
.
- Anonymeil y a 3 semaines
2 3 5 7 2 4 8 1 5 2 4
1 (37=1 )
le 9ème 5 2 3 5 7 2 4 8 1 5 2 4 1suite possible 5 2 4 1 2 3 dans cette demo les nombres a deux chiffres ont ete reduits à un chiffre
Source(s) : + - Aucune RéponseLv 7il y a 3 semaines
Hors sujet, mais voyant Oyubir passer, je me permets de lui suggérer − ainsi qu'aux autres − de rejoindre l'un des succédanés mis en place par certains intervenants.
Car ça va manquer des interventions de cette qualité.
- Anonymeil y a 3 semaines
La formule existe, il faut avec un papier et un crayon établir la liste des N nombres premiers, puis essayer de voir si les suivants sont premiers ou pas, toujours avec le papier et le crayon.
On peut limiter les nombres à tester par des astuces, comme éviter les nombres pair, les multiples de 5, et ceux de trois.
A la fin on a les N+1 nombres premiers.