Algorithme donnant les nombres premiers

Boécien
Boécien
Modifié (July 2023) dans Arithmétique
Inspiré par cet article. Un algorithme qui génère l'ensemble des nombres premiers $p \geq3$ dans l'ordre.
Soit $x_{1}=2$ et la formule de récurrence $$x_{n}=x_{n-1}+PPCM\left(x_{n-1},n\right)$$ alors pour $n\geq3$ on a $$PGCD(x_{n},n)=1\Leftrightarrow n\in P=\left\{ 3,5,7,11,...\right\}.$$
Quelqu'un voit comment le prouver ?
Voici un check test avec PARI-GP
x1=2;for(n=2,30,x2=x1+lcm(n,x1);x1=x2;if(gcd(n,x2)==1,print1(n,",")))
3,5,7,11,13,17,19,23,29,

Réponses

  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Modifié (July 2023)
    Cela a l'air sympa comme langage, c'est mature, les lib sont testées et relativement complètes. Je suis en train de voir si je peux simplifier ou affiner le chapitre 2.2.4. de https://vixra.org/pdf/2206.0068v1.pdf  C'est peut-être l'occasion de me mettre à un nouveau langage.
  • Boécien
    Boécien
    ???
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Modifié (July 2023)
    http://pari.math.u-bordeaux.fr/ 
    C'est bien, ou ce n'est pas encore vraiment ça.
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Modifié (July 2023)
  • Boécien
    Boécien
    Quel rapport avec ma question?
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
     a testé merci pour l'info

  • Chalk
    Chalk
    Modifié (July 2023)
    Aucun @Boécien mais tu as posté dans la rubrique shtam, du coup tu te retrouves avec les shtameurs qui polluent ton fil, et les autres intervenants qui n'ouvrent même pas ton post vu la rubrique dans lequel il apparaît.

    Si tu avais posté dans Arithmétique tu n'aurais eu aucun problème, tu es bon pour recommencer ton post  ;)
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Modifié (July 2023)
    Que cela n'a rien de magique, parce que tu t'arranges ou tu recherches à construire un entier avec tous les nombres premiers inférieurs à n
    (11:31) gp > x1=2;for(n=2,30,x2=x1+lcm(n,x1);x1=x2;if(gcd(n,x2)==1,print1(factor(x2)," ",factor(n),n,",")))
    Mat([2, 4]) Mat([3, 1])3,[2, 6; 3, 1] Mat([5, 1])5,[2, 10; 3, 1] Mat([7, 1])7,[2, 16; 3, 3] Mat([11, 1])11,[2, 18; 3, 3; 7, 1] Mat([13, 1])13,[2, 22; 3, 6; 7, 1] Mat([17, 1])17,[2, 25; 3, 6; 5, 1; 7, 1] Mat([19, 1])19,[2, 32; 3, 8; 5, 1; 7, 1] Mat([23, 1])23,[2, 38; 3, 10; 5, 2; 7, 2] Mat([29, 1])29,
    (11:32) gp >
    si pgcd(2*3*5*7;11)=1  11premier parque pgcd(2*3*5*7,(2,3,4,5,6,7,8,9,10)!=1...
  • raoul.S
    raoul.S
    @Boécien quelle idée de poster dans Shtam... :mrgreen:
  • Boécien
    Boécien
    Parce que ça parlait de premiers :)
  • Boécien
    Boécien
    Modifié (July 2023)
    Je reposte cette question dans la rubrique ad-hoc.
    Inspiré par cet article. Un algorithme qui génère l'ensemble des nombres premiers $p \geq3$ dans l'ordre.
    Soit $x_{1}=2$ et la formule de récurrence $$x_{n}=x_{n-1}+PPCM\left(x_{n-1},n\right)$$ alors pour $n\geq3$ on a $$PGCD(x_{n},n)=1\Leftrightarrow n\in P=\left\{ 3,5,7,11,...\right\}.$$
    Quelqu'un voit comment le prouver ?
    Voici un test avec PARI-GP
    x1=2;for(n=2,30,x2=x1+lcm(n,x1);x1=x2;if(gcd(n,x2)==1,print1(n,",")))
    3,5,7,11,13,17,19,23,29,
  • Keynes
    Keynes
    Modifié (July 2023)
    Bonjour n'est-ce  pas $PGCD(x_n,n-1)=1$
  • Boécien
    Boécien
    Modifié (July 2023)
    Non c'est bien ce que j'énonce. Un autre code pari-gp le confirme:
    v=vector(100000);
    x(n)=if(n<0,0,v[n]);
    v[1]=2;
    for(n=2,1000,v[n]=x(n-1)+lcm(x(n-1),n));
    for(n=2,100,if(gcd(x(n),n)==1,print1(n,",")))
    3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,
  • Bibix
    Bibix
    Modifié (July 2023)
    Bonsoir,
    On a ${\rm PGCD}(x_n, n) = {\rm PGCD}(x_{n-1}, n)$ donc ${\rm PGCD}(x_n, n) = 1 \Longleftrightarrow x_{n} = x_{n-1}(1+n) \Longleftrightarrow b_n = \frac{x_n}{x_{n-1}} - 1 = n$. Ça ressemble au $b_p = p$ de l'article. Mais il n'y a pas de preuve pour le sens non trivial, ça doit être un problème ouvert.
  • Boécien
    Boécien
    Merci Bibix. Oui c'est sans doute un peu tautologique en fait par rapport à l'article.
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Modifié (July 2023)
    p=2;n=3;
    while(true){
    if (pgcd(p,n)==1){p=p*n}
    n++
    }
    pgcd(  2         ,3)=1          3 premier
    pgcd( (2*3)    ,4) =2
    pgcd( (2*3     ,5) =1          5 premier
    pgcd( (2*3*5 ,6) =3
    pgcd( (2*3*5),7) =1           7 premier
    ...
    À partir du moment où tu testes toutes les valeurs de n  ou est la différence.

  • llorteLEG
    llorteLEG
    Modifié (July 2023)
    Hello @remy123456 ! 
    Ce lien pourra t'intéresser!
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Modifié (July 2023)
    Oui, tu as raison. Sinon, pour moi, c'est juste normal, car ce n'est pas PPCM (plus petit commun multiple) ppcm(15,21)=3, ppcm(1*3,1*5)=1 mais lcm(5,32)=160. Donc, tu te retrouves à additionner des morceaux de primorielle.
  • Dom
    Dom
    L’algorithme (crible) d’Ératosthène est déjà très bien fait. 
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Modifié (July 2023)
    Non, la question était pourquoi il y a une primorielle lorsque tu effectues une suite d'additions. L'algorithme qui sort tous les nombres premiers dans l'ordre est là pour appâter le chaland.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Français