Classification des nombres premiers : essai amateur

Discussions générales concernant les mathématiques et n'entrant pas dans les catégories suivantes.
[participation réservée aux utilisateurs inscrits]
Règles du forum
Merci de soigner la rédaction de vos messages et de consulter ce sujet avant de poster. Pensez également à utiliser la fonction recherche du forum.
Algibri

Classification des nombres premiers : essai amateur

Message non lu par Algibri »

J'ai mis au point une fonction et je souhaiterais partager mon idée.
La base de travail c'est une liste des nombres premiers (la plus exhaustive possible).
On opère de la manière suivante :
1. On prend le premier nombre premier, en l'occurence 2.
2. On calcule la factorielle immédiatement inférieure, 1! = 1
3. On l'ajoute à 2, cela donne 3.
4. On teste le nombre obtenu :
- s'il est premier, on le classe parmi les nombres premiers générés (en pratique on le barre comme dans le crible d'Ératosthène) et on réitère selon les mêmes séquences 1,2,3,4.
Le nombre 3 est premier,
5. On calcule la factorielle immédiatement inférieure, 2! = 2
6. On l'ajoute à 3, cela donne 5. etc...

- s'il est composé, on arrête et on retourne au premier nombre non encore éliminé.

La forme générale est P(n+1)= P(n) + k!

k! est la factorielle immédiatement inférieure à P(n)
Juste un exemple :
Quand je passe de 23 à 29, la factorielle change
11 donnera 17 (3!=6)
17 donnera 23 (3! est toujours inférieure à 23)
23 donnera 29 (29 devient supérieur à 4! on change de base)
29 donnera donc 29+24=53
etc...

Juste pour étayer ce que je viens de dire je donne une première liste :

Nombres générateurs : 2, 11, 31, 37, 41, 43, 47, 59, 73, 79,....
Nombres générés : 3, 5, 7, 13, 17, 19, 23, 29, 53, 61, 67, 71,...

On peut constater que certains nombres premiers sont classés comme générateurs mais ils sont en fait "stériles". Exemple le 41 qui donne un nombre composé (41+24=65).
D'autres sont prolifiques comme le 239 qui donne une séquence de 7 nombres premiers qui se suivent 359, 479, 599, 719, 839, 1559, 2279

Mon idée est de classer les générateurs par rang
rang 0 (stériles)
rang 1 on obtient un nombre premier
rang 2 on obtient 2 nombres premiers consécutivement
......
rang m on obtient m nombres premiers consécutivement

N'étant pas programmeur j'aurais aimé que quelqu'un un volontaire publie sur le site les nombres générateurs classés par rang de 0 à m.
Au moins 10.000 ... je suis curieux de voir comment ils se répartissent et mon intuition est que l'on peut obtenir une très longue de premiers générés par un seul sur la base de cette fonction (j'en teste une autre en attendant mais c'est long sur un tableur).

Merci pour toute aide et suggestions.
Arnaud
Modérateur honoraire
Modérateur honoraire
Messages : 7097
Inscription : lundi 28 août 2006, 13:18
Localisation : Allemagne
Contact :

Message non lu par Arnaud »

Bonjour Algibri,

Je ne sais pas comment tu es venu à cette idée, mais cela semble impressionnant.
Vu le niveau, je te conseille de mettre également un message sur le forum :

http://les-mathematiques.u-strasbg.fr/p ... _new.php?2

Des mathématiciens plus compétents pourront te répondre.

En tout cas, si cette fonction produit son effet, un autre problème apparait : classer les nombres "stériles" et les "prolifiques", enfin surtout les "stériles".
Arnaud
Un peu d'info - Pyromaths - Pas d'aide en MP (non plus)
Algibri

Message non lu par Algibri »

Arnaud a écrit :Bonjour Algibri,

Je ne sais pas comment tu es venu à cette idée, mais cela semble impressionnant.
Vu le niveau, je te conseille de mettre également un message sur le forum :

http://les-mathematiques.u-strasbg.fr/p ... _new.php?2

Des mathématiciens plus compétents pourront te répondre.

En tout cas, si cette fonction produit son effet, un autre problème apparait : classer les nombres "stériles" et les "prolifiques", enfin surtout les "stériles".
Merci pour le conseil mais c'est déjà fait.
J'ai publié ce texte sur le forum dont tu parles avant de venir le faire sur le vôtre.
J'attends toujours de l'aide, des suggestions, une critique constructive...
Je ne suis qu'un amateur qui se pose des questions.
Arnaud
Modérateur honoraire
Modérateur honoraire
Messages : 7097
Inscription : lundi 28 août 2006, 13:18
Localisation : Allemagne
Contact :

Message non lu par Arnaud »

Ok, je viens d'y voir ton message et effectivement cela n'a pas donné grand chose.

Il y a un point que je n'ai pas compris : comment choisis-tu les générateurs ?
Pour réaliser un programme, on doit faire un choix, et ce choix ne me semble pas explicite.
Arnaud
Un peu d'info - Pyromaths - Pas d'aide en MP (non plus)
Algibri

Message non lu par Algibri »

Arnaud a écrit :Ok, je viens d'y voir ton message et effectivement cela n'a pas donné grand chose.

Il y a un point que je n'ai pas compris : comment choisis-tu les générateurs ?
Pour réaliser un programme, on doit faire un choix, et ce choix ne me semble pas explicite.
Un nombre premier "générateur" est un nombre premier qui n'est pas généré par un autre sur la base de la règle P(n+1)= P(n)+k!

Il faut prendre la liste depuis le début :
Le 2 génère 3,5,7.13,19, ....
après le 19 on obtient en appliquant la règle 25 qui est composé, on arrète et on élimine (comme dans le crible d'Ératosthène) les nombres 3, 5, 7, 13, et 19
On retourne à la liste et on prend le 11 qui n'a pas été éliminé et on lui applique la règle 11 + 3! = 17 (17 est premier on continue)
17 + 3! = 23 (idem)
23 +3! = 29 (idem)
29 + 4! = 53 (la base a changé puisque la factorielle immédiatement inférieure à 29 est 4! =24) 53 est premier on continue
53 + 4! = 77 (77 est composé, on arrête et on retourne à la liste des non éliminés
On prend donc le 31 et ainsi de suite.
Le programme est simple à confectionner par un programmeur. Il n'y a rien de complexe : une boucle, un compteur, un fichier de la liste des premiers que l'on éclate en deux au fur et à mesure.
On peut ajouter un module pour tester la primalité si on veut (à partir du moment où ce seront de grands nombres hors liste).
guiguiche
Modérateur général
Modérateur général
Messages : 8191
Inscription : vendredi 06 janvier 2006, 15:32
Statut actuel : Enseignant
Localisation : Le Mans
Contact :

Message non lu par guiguiche »

Algibri a écrit :Le programme est simple à confectionner par un programmeur. Il n'y a rien de complexe : une boucle, un compteur, un fichier de la liste des premiers que l'on éclate en deux au fur et à mesure.
Je ne comprends pas bien ce qui t'empêche de télécharger FreePascal (par exemple) pour le programmer toi même ? (je ne cherche aucune polémique, allusion à les-maths.net).
Honnêtement, bien que cela semble intéressant du point de vue de la programmation, je n'ai guère le temps de me pencher sur la question.
Pas d'aide par MP : les questions sont publiques, les réponses aussi.
Tu as apprécié l'aide qui t'a été fournie ? Alors n'hésite pas à rendre la pareille à quelqu'un d'autre.
Un peu d'autopromotion.
Arnaud
Modérateur honoraire
Modérateur honoraire
Messages : 7097
Inscription : lundi 28 août 2006, 13:18
Localisation : Allemagne
Contact :

Message non lu par Arnaud »

Algibri a écrit : On retourne à la liste et on prend le 11 qui n'a pas été éliminé et on lui applique la règle 11 + 3! = 17 (17 est premier on continue)
C'est un peu paradoxal, car finalement pour générer les nombres premiers, tu as besoin de leur liste.
Pour 11, c'est assez évident, mais quand on dépasse les 5000 ( voire 10 000 ), c'est beaucoup plus complexe.
Donc pour réaliser le programme, il faudrait déjà entrer ( ou générer ) tout le crible dans une liste et faire une comparaison.
Arnaud
Un peu d'info - Pyromaths - Pas d'aide en MP (non plus)
Algibri

Message non lu par Algibri »

guiguiche a écrit :
Algibri a écrit :Le programme est simple à confectionner par un programmeur. Il n'y a rien de complexe : une boucle, un compteur, un fichier de la liste des premiers que l'on éclate en deux au fur et à mesure.
Je ne comprends pas bien ce qui t'empêche de télécharger FreePascal (par exemple) pour le programmer toi même ? (je ne cherche aucune polémique, allusion à les-maths.net).
Honnêtement, bien que cela semble intéressant du point de vue de la programmation, je n'ai guère le temps de me pencher sur la question.
Je ne suis pas un programmeur.
Je sais comment fonctionne un programme, je peux concevoir un algorithme de bout en bout mais j'ai une nette aversion pour la programmation. C'est aussi simple que cela. Ce qui m'a rebuté c sont ces codes que tout le monde applique sans savoir exactement pourquoi. Comme quelqu'un qui aime lire et abhorre l'écriture.

Merci pour les commentaires.
Algibri

Message non lu par Algibri »

Arnaud a écrit :
Algibri a écrit : On retourne à la liste et on prend le 11 qui n'a pas été éliminé et on lui applique la règle 11 + 3! = 17 (17 est premier on continue)
C'est un peu paradoxal, car finalement pour générer les nombres premiers, tu as besoin de leur liste.
Pour 11, c'est assez évident, mais quand on dépasse les 5000 ( voire 10 000 ), c'est beaucoup plus complexe.
Donc pour réaliser le programme, il faudrait déjà entrer ( ou générer ) tout le crible dans une liste et faire une comparaison.
Il n'y a à mon avis aucun paradoxe. Je le dis au début de mon post :
"La base de travail c'est une liste des nombres premiers (la plus exhaustive possible)."
Ce que je cherche à comprendre ce sont les implications d'une telle opération sur la répartition des premiers entre "générateurs" et "générés".
J'aurais pu choisir P(n+1) = P(n) + 2^k (en optant pour le 2^k immédiatemment inférieur à P(n) ou n'importe quel nombre f(p(n)) qui donne un nombre pair comme résultat).
Si la fonction que j'ai choisie me permet de trouver des générateurs produisant consécutivement 1000 nombres premiers (par exemple et ce n'est qu'un exemple), je m'interrogerais sur le pourquoi.
Si en revanche la formule débouche sur un nombre généré limite (inférieur au record connu de 47 consécutivement premiers), je chercherais une autre fonction.
J'en teste une autre.
C'est juste un essai, une idée.
Si quelqu'un le programme et trouve une suite longue (supérieure à 47) je serais intéressé à le savoir.
Un matheux universitaire dans un laboratoire avec un équipement lourd peut tester de très grands nombres (avec des milliers de chiffres).
Moi, j'en suis incapable avec mon vieux pc.

Merci pour tout éclairage.
Helium

Message non lu par Helium »

Impressionant d'avoir pensé à cela tout seul!
Cependant, pour des nombres très grands, la calcul de factoriels n'est il pas trop complexe (même pour une machine)?
bibi6
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 461
Inscription : jeudi 23 novembre 2006, 20:12
Statut actuel : Enseignant
Localisation : 59 (Région St Amand les Eaux)

Message non lu par bibi6 »

Bonjour,

Pour passer le temps, je me suis amusé à voir ce que ça donnait...
Je suis parti de la liste de tous les nombres premiers (oui j'ai bien dit tous, même si je les calcule au fur et à mesure...) et à partir de chaque nombre premier qui n'a pas été trouvé, je génère par la formule suggérée:

Pour passer d'un nombre $p$ au suivant, considérer $k$ le nombre qui vérifie $k! \leq p < (k+1)!$, et ce nombre est $p + k!$

J'ai lancé l'artillerie sur les 100 premiers nombres premiers non générés par les précédents et au bout d'une bonne heure de calculs, je trouve ceci:

Code : Tout sélectionner

Génération au départ de 2:   3 5 7 13 19  --
Génération au départ de 11:  17 23 29 53  --
Génération au départ de 31:   --
Génération au départ de 37:  61  --
Génération au départ de 41:   --
Génération au départ de 43:  67  --
Génération au départ de 47:  71  --
Génération au départ de 59:  83 107 131 251  --
Génération au départ de 73:  97  --
Génération au départ de 79:  103 127  --
Génération au départ de 89:  113 137 257  --
Génération au départ de 101:   --
Génération au départ de 109:   --
Génération au départ de 139:   --
Génération au départ de 149:  269 389 509  --
Génération au départ de 151:  271  --
Génération au départ de 157:  277 397  --
Génération au départ de 163:  283  --
Génération au départ de 167:   --
Génération au départ de 173:  293  --
Génération au départ de 179:   --
Génération au départ de 181:   --
Génération au départ de 191:  311 431  --
Génération au départ de 193:  313 433  --
Génération au départ de 197:  317  --
Génération au départ de 199:   --
Génération au départ de 211:  331  --
Génération au départ de 223:   --
Génération au départ de 227:  347 467 587  --
Génération au départ de 229:  349  --
Génération au départ de 233:  353  --
Génération au départ de 239:  359 479 599 719 839 1559  --
Génération au départ de 241:   --
Génération au départ de 263:  383 503  --
Génération au départ de 281:  401 521 641 761 1481  --
Génération au départ de 307:   --
Génération au départ de 337:  457 577  --
Génération au départ de 367:  487 607 727 1447  --
Génération au départ de 373:   --
Génération au départ de 379:  499 619 739 1459 2179  --
Génération au départ de 409:   --
Génération au départ de 419:   --
Génération au départ de 421:  541 661  --
Génération au départ de 439:   --
Génération au départ de 443:  563 683  --
Génération au départ de 449:  569  --
Génération au départ de 461:   --
Génération au départ de 463:   --
Génération au départ de 491:   --
Génération au départ de 523:  643  --
Génération au départ de 547:   --
Génération au départ de 557:  677 797  --
Génération au départ de 571:  691 811 1531 2251 2971 3691  --
Génération au départ de 593:   --
Génération au départ de 601:   --
Génération au départ de 613:  733 1453  --
Génération au départ de 617:   --
Génération au départ de 631:  751 1471  --
Génération au départ de 647:   --
Génération au départ de 653:  773 1493 2213  --
Génération au départ de 659:   --
Génération au départ de 673:   --
Génération au départ de 701:  821  --
Génération au départ de 709:  829 1549 2269  --
Génération au départ de 743:   --
Génération au départ de 757:   --
Génération au départ de 769:  1489  --
Génération au départ de 787:   --
Génération au départ de 809:   --
Génération au départ de 823:  1543  --
Génération au départ de 827:   --
Génération au départ de 853:   --
Génération au départ de 857:   --
Génération au départ de 859:  1579  --
Génération au départ de 863:  1583  --
Génération au départ de 877:  1597  --
Génération au départ de 881:  1601  --
Génération au départ de 883:   --
Génération au départ de 887:  1607  --
Génération au départ de 907:  1627 2347 3067  --
Génération au départ de 911:   --
Génération au départ de 919:   --
Génération au départ de 929:   --
Génération au départ de 937:  1657 2377  --
Génération au départ de 941:   --
Génération au départ de 947:  1667  --
Génération au départ de 953:   --
Génération au départ de 967:   --
Génération au départ de 971:   --
Génération au départ de 977:  1697 2417 3137  --
Génération au départ de 983:   --
Génération au départ de 991:   --
Génération au départ de 997:   --
Génération au départ de 1009:   --
Génération au départ de 1013:  1733  --
Génération au départ de 1019:   --
Génération au départ de 1021:  1741  --
Génération au départ de 1031:   --
Génération au départ de 1033:  1753 2473  --
Génération au départ de 1039:  1759  --
- : unit = ()
Au vu de cela, je dirais qu'il y a de moins en moins de chances d'avoir des grands prolifiques, et de plus en plus de stériles. A confirmer pour des nombres plus grands.

Sinon, je rejoins tous ceux qui ont déjà répondu à ce post: fallait y penser.
Si le code source (en Caml) intéresse quelqu'un, je suis prêt à le poster. Pour le moment, je regarde à l'optimiser quelque peu.
Algibri

Message non lu par Algibri »

Au vu de cela, je dirais qu'il y a de moins en moins de chances d'avoir des grands prolifiques, et de plus en plus de stériles. A confirmer pour des nombres plus grands.

Sinon, je rejoins tous ceux qui ont déjà répondu à ce post: fallait y penser.
Si le code source (en Caml) intéresse quelqu'un, je suis prêt à le poster. Pour le moment, je regarde à l'optimiser quelque peu.
Merci pour le tableau et le programme.
Le nombre de stériles est effectivement de plus en plus important, je le prévoyais.
J'avais émis l'idée de retraiter les nombres stériles avec p + (k-1)! et ceux qui restent stériles avec p+(k-2)! etc... en les nommant générateurs d'ordre 1, 2, 3, etc... l'indice étant i avec k-i (i variant de 0 à k-1.
On aurait un tableau des nombres premiers par ordre.
Ce tableau permettrait de retrouver tous les nombres premiers générés

Un nombre premier générateur serait noté à partir de deux indices :
- l'ordre du générateur : i
- le nombre de premiers générés dans l'ordre qui peut varier de 1 à t (t étant le maximum de nombres générés je suis arrivé à 10 avec l'ordre 1).

[Edit Arnaud : j'ai supprimé le quote pour éviter les messages trop longs, et pour garder une bonne lisibilité de ton topic]
omnibus

Message non lu par omnibus »

Cette fonction m'a l'air plutôt intéressante, et je vais encore en rajouter une couche : fallait y penser !
Mais voilà, j'aurai aimé un petit éclaircicement :
La forme générale est P(n+1)= P(n) + k!
retraiter les nombres stériles avec p + (k-1)!
Comment obtenez-vous ces formules ? :?: :shock:
Pouriez-vous détailler ce que vous entendez par chacun de vos symboles (que veux dire k) ? Merci d'avance ... :?: :?: :?: :D
bibi6
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 461
Inscription : jeudi 23 novembre 2006, 20:12
Statut actuel : Enseignant
Localisation : 59 (Région St Amand les Eaux)

Message non lu par bibi6 »

Bonjour,

L'idée initiale d'Algibri est de savoir, étant donné un nombre premier, comment en générer d'autres, et combien.

Algibri a écrit :Ce que je cherche à comprendre ce sont les implications d'une telle opération sur la répartition des premiers entre "générateurs" et "générés".
Trivialement, pour passer d'un nombre premier à un autre, il faut lui ajouter un nombre pair. Maintenant, quoi comme nombre pair?

*Idée 1:
Pour passer d'un nombre $p$ au suivant, considérer $k$ le nombre qui vérifie $k! < p < (k+1)!$, et ce nombre est $p + k!$ .

Cela conduit au tableau que j'ai mis en code, et qui devrait être continué (moyennant le temps et l'optimisation du code...)

*Idée 2:
Algibri a écrit : J'aurais pu choisir P(n+1) = P(n) + 2^k (en optant pour le 2^k immédiatemment inférieur à P(n) ou n'importe quel nombre f(p(n)) qui donne un nombre pair comme résultat).
Si la fonction que j'ai choisie me permet de trouver des générateurs produisant consécutivement 1000 nombres premiers (par exemple et ce n'est qu'un exemple), je m'interrogerais sur le pourquoi.

Si en revanche la formule débouche sur un nombre généré limite (inférieur au record connu de 47 consécutivement premiers), je chercherais une autre fonction.
J'en teste une autre.
C'est juste un essai, une idée.

Une fois un tel traitement ("classification"), on peut continuer avec un nombre pair "un peu plus bas" (c'est ce qu'Algibri propose par sa "classification par ordre").

Tout cela ne sont que des idées, qu'on peut améliorer...
Rémi
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 168
Inscription : samedi 04 juin 2005, 19:39
Statut actuel : Autre

Message non lu par Rémi »

bibi6 a écrit :Trivialement, pour passer d'un nombre premier à un autre, il faut lui ajouter un nombre pair.
Est-ce vraiment si trivial que cela ?
Déjà 3-2=1 or 3 est premier, 2 est premier mais 1 n'est pas pair. Bon ensuite sachant tous nombres premiers différents de 2 est impair. Soit 2k+1 un nombre premier différent de deux et soit 2n+1 un autre nombre premier supérieur à 2k+1 alors 2n+1-(2k+1)=2*(n-k).

Ah ben ouais c'est trivial :D modulo qu'on s'interdise quand même le 2.

Bon ben j'ai pas apporté grand chose mais comme je l'ai tapé, je l'envoi.

Bon courage.
Framboise
Utilisateur chevronné
Utilisateur chevronné
Messages : 1172
Inscription : lundi 21 mai 2007, 13:57
Statut actuel : Autre
Localisation : Dordogne

Message non lu par Framboise »

J'ai le virus des sciences, ça se soigne ?
omnibus

Message non lu par omnibus »

J'ai compis la forme générale et je vous remercie de votre aide; j'aurai juste encore besoin d'une précision :
J'aurais pu choisir P(n+1) = P(n) + 2^k (en optant pour le 2^k immédiatemment inférieur à P(n) ou n'importe quel nombre f(p(n)) qui donne un nombre pair comme résultat).
Comment peut-il y avoir équivalence entre P(n)+2^k et P(n)+k! ? :shock: Merci d'avance... :?:
Algibri

Message non lu par Algibri »

omnibus a écrit :J'ai compis la forme générale et je vous remercie de votre aide; j'aurai juste encore besoin d'une précision :
J'aurais pu choisir P(n+1) = P(n) + 2^k (en optant pour le 2^k immédiatemment inférieur à P(n) ou n'importe quel nombre f(p(n)) qui donne un nombre pair comme résultat).
Comment peut-il y avoir équivalence entre P(n)+2^k et P(n)+k! ? :shock: Merci d'avance... :?:
C'est une équivalence dans le sens où pour générer par addition un nombre premier à partir d'un autre, il faut un nombre pair.
2^k est pair
k! est pair

Il faut trouver une fonction qui donne comme résultat un nombre pair et qui en même temps permet de générer des suites longues de nombres premiers.
omnibus

Message non lu par omnibus »

Tout s'éclaircie, mais :
J'avais émis l'idée de retraiter les nombres stériles avec p + (k-1)! et ceux qui restent stériles avec p+(k-2)! etc...
si k! est pair, comment arrive-t'on à la formule p+ (k-1)!, qui est donc impair ? :?:
Dernière modification par omnibus le vendredi 29 juin 2007, 15:07, modifié 1 fois.
omnibus

Message non lu par omnibus »

P(n+1) = P(n) + 2^k
Les deux formules génèreraient-elles les mêmes nombres de nombres premiers pour un même indice n, pour tout n ? :?:
Répondre
  • Sujets similaires
    Réponses
    Vues
    Dernier message