Fonction donnant 10 premiers nombres premiers dans l'ordre ?

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
Tangi
Messages: 5
Enregistré le: 30 Oct 2022, 01:47

fonction donnant 10 premiers nombres premiers dans l'ordre ?

par Tangi » 31 Oct 2022, 14:29

Bonjour,
Je cherche en programmation à trouver des fonctions à une variable et calculables rapidement, donnant les n premiers nombres premiers dans l'ordre. f(1)=2;f(2)=3;f(3)=5 etc. Y a-t-il sur le web de la lecture sur ce sujet, ou des résultats comme on en trouve pour les polynômes, où on pourrait voir les fonctions trouvées et jusqu'à quel n f(n) donne le nième nombre premier sans erreur ? Je bloque rapidement de mon côté, et je suis persuadé qu'il y a des choses là-dessus étant donné le nombre d'études sur les nombres premiers :)
Pourtant je rien trouvé sur le web, à part des résultats sur la recherche de polynômes qui donnerait le plus grand nombre de nombres premiers, du plus grand nombre premier etc.
Merci beaucoup pour votre aide,
Tangi



lyceen95
Membre Complexe
Messages: 2255
Enregistré le: 15 Juin 2019, 00:42

Re: fonction donnant 10 premiers nombres premiers dans l'ord

par lyceen95 » 31 Oct 2022, 16:07

Pour n relativement petit (moins de 1000), un tableau avec la liste des nombres premiers, ce n'est pas très gourmand en mémoire, et ça suffit.
Pour n plus grand, le bon vieux crible d'Eratosthène reste à ma connaissance un bon outil.
Tu peux aussi avoir une liste avec des trous.
Par exemple on sait que le 1000ème nombre premier est XXX, le 2000ème est YYY, le 3000ème est ZZZ, etc.
Et donc, si on demande le 1950ème, tu pars du 2000ème, et tu testes les nombres immédiatement inférieurs, il faut remonter 50 nombres premiers en arrière, ça doit être assez rapide.

Mais ça revient toujours au même, on a calculé au préalable tous les nombres premiers jusqu'à une certaine limite. On n'a pas tout mémorisé, parce qu'on avait des contraintes, et on reconstitue cette liste.

Tangi
Messages: 5
Enregistré le: 30 Oct 2022, 01:47

Re: fonction donnant 10 premiers nombres premiers dans l'ord

par Tangi » 31 Oct 2022, 16:53

Merci lyceen95 pour ta réponse, mais j'ai sûrement mal posé ma question. Je ne cherche pas de méthode pour tester des nombres premiers plus ou moins rapidement, et mon but n'est pas de stocker ces nombres non plus.
Je recherche des fonctions f(n), n étant dans N*, qui donnent les n premiers nombres premiers dans l'ordre jusqu'à un certain rang n.
Deux exemples :
f(n)=n+1 donne les bons résultats pour n de 1 à 2
f(n)=2+[n ln(n)] est une des fonctions donnant les 4 premiers nombres premiers dans l'ordre, pour n de 1 à 4. (la partie entre crochets représente la partie entière)
Il y a surement du monde ayant recherché des fonctions pour que celles-ci donnent de bons résultats jusqu'à un n relativement grand, mais je n'ai aucune idée jusqu'où cela va et je ne trouve aucune ressource là-dessus sur le web.
J'espère que ma question est plus claire, merci encore pour votre aide.
Modifié en dernier par Tangi le 31 Oct 2022, 17:08, modifié 1 fois.

Avatar de l’utilisateur
WillyCagnes
Membre Transcendant
Messages: 3752
Enregistré le: 21 Sep 2013, 20:58

Re: fonction donnant 10 premiers nombres premiers dans l'ord

par WillyCagnes » 31 Oct 2022, 17:05

bonjour,

voir ce lien pour t'aider
https://fr.wikipedia.org/wiki/Formules_ ... s_premiers

P(n) = n2 + n + 41 est premier pour tous les nombres entiers positifs strictement inférieurs à 40

Tangi
Messages: 5
Enregistré le: 30 Oct 2022, 01:47

Re: fonction donnant 10 premiers nombres premiers dans l'ord

par Tangi » 31 Oct 2022, 17:12

Merci WillyCagnes, j'avais déjà regardé cette page, mais hélas elle ne répond pas à ma question. Les fonctions que je recherche donnent les bons résultats dans l'ordre, P(1) dans ton exemple ne donne pas le premier nombre premier mais 43.

lyceen95
Membre Complexe
Messages: 2255
Enregistré le: 15 Juin 2019, 00:42

Re: fonction donnant 10 premiers nombres premiers dans l'ord

par lyceen95 » 31 Oct 2022, 17:47

C'est sans espoir.

On peut construire une fonction totalement artificielle qui va donner les 10 premiers , si tu y tiens, je peux te la construire.
Pareil pour les 100 premiers, je peux te la trouver. Pareil pour les 5000 premiers si tu y tiens (en théorie, je sais faire, en pratique, ça va être horriblement long pour te la donner).
Mais dans tous ces cas, les outils que je vais utiliser n'ont aucun rapport avec les nombres premiers.
Par exemple, si tu demandes une fonction qui donne (2,3,5,7,11,13,18,19,23,29) (et donc 18 au lieu de 17), j'utiliserai exactement la même démarche que pour (2,3,5,7,11,13,17,19,23,29)

Tangi
Messages: 5
Enregistré le: 30 Oct 2022, 01:47

Re: fonction donnant 10 premiers nombres premiers dans l'ord

par Tangi » 31 Oct 2022, 19:25

Oui j'y tiens lyceen95, si tu as une fonction donnant les 100 premiers nombres premiers dans l'ordre avec une fonction à une variable et rapide, j'ai vraiment envie de la voir.
Mon souhait était justement de voir les fonctions trouvées jusqu'à présent, et de voir si certains en avaient trouvées des simples avec peu de termes, de la même manière qu'on peut trouver la liste des polynômes trouvés jusqu'à présent générant des nombres premiers dans le désordre entre telle et telle valeur de n, en recherchant les polynômes les plus simples possibles donnant le plus grand nombre de nombres premiers possibles. Et pour ces polynômes, il est clair qu'il s'agit de coefficients "artificiels", qui n'ont sûrement rien à voir avec les nombres premiers.
De même, on peut dire que les nombres 355 et 113 sont artificiels et n'ont rien à voir avec pi, mais il me semble intéressant quand même de savoir que 355/113 donne une précision sur 6 décimales de pi. Et ceci bien entendu en ayant conscience que c'est sans espoir de trouver une fraction qui donne pi :), mais cela n'empêche pas d'être intéressé par la recherche pour avoir une meilleure précision avec une fraction la plus simple possible, même si la démarche peut sembler naïve et s'éloigner de la recherche mathématique pure. C'est ce que je cherche pour les fonctions donnant les n premiers nombres premiers, et je suis étonné de ne trouver des publications ne s'intéressant qu'aux polynômes donnant des nombres premiers dans le désordre pour ce type de recherche. Mais je cherche toujours et je suis preneur de toute piste, merci à vous. :)

Rdvn
Membre Rationnel
Messages: 803
Enregistré le: 05 Sep 2018, 12:55

Re: fonction donnant 10 premiers nombres premiers dans l'ord

par Rdvn » 31 Oct 2022, 20:22

Bonsoir
Voici un article qui peut vous intéresser
Bon courage
https://www.cristal.univ-lille.fr/~jdelahay/pls/062.pdf

Tangi
Messages: 5
Enregistré le: 30 Oct 2022, 01:47

Re: fonction donnant 10 premiers nombres premiers dans l'ord

par Tangi » 31 Oct 2022, 21:09

Oui merci Rdvn, je l'avais déjà lu, il fait le point sur les recherches de formules sur les nombres premiers. Cela ne répond pas à ma question, mais je trouve cet article bien expliqué. Je précise que j'ai déjà parcouru beaucoup de résultats Google avant de poster sur le forum. Mais j'ai sûrement raté des pages, études ou publications déjà faites, et j'espérais que certains d'entre vous en auraient déjà croisées. Mais peut-être que ma recherche semble trop "inutile" et qu'il est normal que je ne trouve rien :)
Merci d'avoir pris le temps de me répondre, je vais continuer mes recherches.

lyceen95
Membre Complexe
Messages: 2255
Enregistré le: 15 Juin 2019, 00:42

Re: fonction donnant 10 premiers nombres premiers dans l'ord

par lyceen95 » 31 Oct 2022, 21:27

Voici une formule pour les 13 premiers nombres premiers.





Comment j'ai trouvé ces coefficients ?
On a 13 inconnues ( ces 13 coefficients) et on a 13 équations , par exemple pour la 13ème :
etc etc
Donc on trouve les 13 coefficients.
Si on veut un polynôme qui donne les 100 premiers nombres premiers, on généralise cette méthode.

Plus sérieusement, tu as ce site : https://pari.math.u-bordeaux.fr/gp.html
tu tapes par exemple primes(1000) dans la ligne prévue à cet effet, puis tu cliques sur 'Evaluate with PariGP', et tu obtiens instantanément les 1000 premiers nombres premiers.
Je n'ai pas la moindre idée de la méthode utilisée.

GaBuZoMeu
Habitué(e)
Messages: 6019
Enregistré le: 05 Mai 2019, 10:07

Re: fonction donnant 10 premiers nombres premiers dans l'ord

par GaBuZoMeu » 31 Oct 2022, 22:23

Bonsoir,

Petit tour de passe passe :





est bien sûr le coeffcient binomial .

Vous voyez bien entendu comment est fabriqué le tableau triangulaire, et comment est fabriqué à partir du côté gauche du tableau. Maintenant calculez pour allant de 1 à 6 ...
Bien entendu je me suis arrêté à 6, mais on peut augmenter le tableau triangulaire et allonger en , etc.

Bien entendu aussi cela n'a rien à voir avec les nombres premiers. On pourrait mettre en haut du triangle n'importe quel suite d'entiers.

lyceen95
Membre Complexe
Messages: 2255
Enregistré le: 15 Juin 2019, 00:42

Re: fonction donnant 10 premiers nombres premiers dans l'ord

par lyceen95 » 31 Oct 2022, 23:24

Merci GBZM d'avoir corrigé/complété ma méthode /mon arnaque.
Je me doutais qu'on pourrait trouver des coefficients rationnels mais je n'avais pas du tout la méthode.

GaBuZoMeu
Habitué(e)
Messages: 6019
Enregistré le: 05 Mai 2019, 10:07

Re: fonction donnant 10 premiers nombres premiers dans l'ord

par GaBuZoMeu » 01 Nov 2022, 10:13


 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 165 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite