Crible de nombres premiers

davidstr

Soit P_n=1+12n

Si P_n iest un carré parfait et sqrt(P_n) n'est pas divisible par un membre de la liste des nombres premiers

Alors sqrt(P_n) est premier

Le script en python

import gmpy2
from gmpy2 import mpz
listeprime=[]
listenonprime=[]
for i in range(2,10000):
 j=1+12*i
 if gmpy2.is_square(j):
  h=int(j**0.5)
  k=0
  for l in listeprime:
    if h%l==0:
     print(h,"not prime and have factor ",l)
     listenonprime.append(h)
  for l in listenonprime:
   if h==l:
    k=1
  if k!=1:
          print(h,"prime")
          listeprime.append(h)

davidstr

En fait c'est un crible qui élimine tous les multiples de deux et de trois....
C'est aussi sympa de voir que si p est premier alors p^2=1 mod 12

davidstr

p>=5

lourrran

Si $p$ est premier  et si $p > 3$ , alors $p^2=1$ mod $12$

gerard0

Bonjour.

Il y a une contradiction dans la phrase "Si P_n iest un carré parfait et sqrt(P_n) n'est pas divisible par un membre de la liste des nombres premiers, alors sqrt(P_n) est premier" (j'ai rétabli l'orthographe et la grammaire d'usage).

En effet, si sqrt(P_n) n'est pas dans la liste des nombres premiers, il ne peut pas être premier.

Manifestement, il y a un défaut de présentation; par exemple il manque la référence à cette liste de premiers.

Et pour fabriquer une liste de premier, il y a bien plus simple !!!

Autre remarque : "C'est aussi sympa de voir que si p est premier alors p^2=1 mod 12 p>=5". Oui, c'est la remarque connue depuis plus de 2300 ans que à part 2 et 3, tous les premiers sont de la forme 6n+1 ou 6n-1 dont les carrés sont 12(3n²+n)+1 et 12(3n²-n)+1.

Cordialement.

davidstr

Ce crible n'est peut être pas rapide mais voilà ce que j'ai découvert dans ma recherche.

Je me suis intéressé à l’indice n dans P_n=1+12n

pour lesquels sqrt(P_n) est premier

J’ai tracé n en fonction des entiers de 1 à 20000

J’ai tracé les résidus de cette régression toujours en fonction des entiers. Il sont remarquablement alternativement positifs et négatifs et très linéaires !!

lourrran

Tu construis une série de données. 
Puis tu fais une régression de cet ensemble de points par un polynôme.
Puis tu constates que les points sont équitablement répartis au-dessus et en-dessous de la courbe de régression.
Oui ! C'est le principe d'une courbe de régression, faire en sorte que les points soient équitablement répartis de part et d'autre de cette courbe.

Tu constates que plus $n$ grandit, plus l'erreur potentielle grandit. Ca, c'était complètement prévisible.
Et elle grandit en suivant une courbe parfaitement linéaire. ... 
Question : le triangle est 'plein', autrement dit, quand n vaut environ 16000, f(n) est un nombre entre -3000 et + 3000  Et à peu près tous les nombres entre -3000 et + 3000 sont rencontrés au moins une fois, ce qui fait que le triangle apparaît comme entièrement coloré.
C'est ça ?

Ta courbe de régression est de degré 4. Et le coefficient du terme de degré 4 est négatif.  
Ca ne laisse rien présager de bon. La courbe a une allure convexe (en forme de V),  et les limites en -infini et +infini sont négatives ?!

Ca veut juste dire que tu 'sur-interprètes'  des données qui sont construites sur-mesure.

davidstr

Tu as raison d'objecter sur la fonction de degré 4
j'ai corrélé sur du degré deux
et dans le deuxième graphique j'ai tracé que les point

Math Coss

Ayant un jour entendu parler du théorème des nombres premiers, je chercherais à interpoler par $cx \ln x$ pour une constante $c$ convenable.

lourrran

Ici, je ne sais pas ce que représente cette colonne D, avec cette merveilleuse alternance -4382 ; + 4380 etc etc
Mais c'est beaucoup trop régulier pour présenter un intérêt.

Déjà le tout début nous annonçait la couleur : si un nombre n'est divisible par aucun nombre premier , alors il est premier. 
C'est la définition des nombres premiers (après quelques corrections), mais c'était présenté comme une découverte magique !

Allez, je viens de découvrir une propriété moi aussi, et je vais la partager ici : si a+b est un nombre premier, alors b+a est aussi un nombre premier.

zeitnot

" si a+b est un nombre premier, alors b+a est aussi un nombre premier. "

Lourran tu spoiles les questions du CAPES 2023 !?

jelobreuil

Non, vraiment, Zeitnot ?

davidstr

Milles excuses, une erreur dans mon script que j'ai corrigé.

n=20000000
premier=[]
z=1
for i=(2:n)
    j=1+12*i
    if (j^0.5-int(j**0.5))==0
        h=int(j**0.5)
        k=0
        for l=(1:length(premier))
                if modulo(h,premier(l))==0
                    k=1
                    break
                end
        end
        if k~=1
            premier(z)=h
            indicen(z)=i
            k=0
            z=z+1
        end
    end
end

x=(1:(z-1))
x0=1
y0=indicen(x0)
x1=fix((z-1)/2)
y1=indicen(x1)
x2=z-1
y2=indicen(x2)
a=(1/(x2-x0))*((y2-y1)/(x2-x1)-(y1-y0)/(x1-x0))
b=(y1-y0)/(x1-x0)-a*(x1+x0)
c=y0-b*x0-a*x0^2
interpolation2degre=a*x.^2+b*x+c*ones(1,z-1)

residus=(indicen-interpolation2degre')
plot(x',[indicen interpolation2degre' residus],[2 -2 3])
legend(["indice n" "interpolation_du_second degré" "residus"])
figure()
plot(x',residus)
legend(["residus"])

davidstr

j'ai vu mieux avec le calcul des primes par scilab

premiers=primes((12*200000000000000+1)^0.5);
carre=premiers.^2;
n=(carre-1)./12
n=n((3:length(n)))

x=(1:(length(n)))
x0=1
y0=n(x0)
x1=fix(length(n)/2)
y1=n(x1)
x2=length(n)
y2=n(x2)
a=(1/(x2-x0))*((y2-y1)/(x2-x1)-(y1-y0)/(x1-x0))
b=(y1-y0)/(x1-x0)-a*(x1+x0)
c=y0-b*x0-a*x0^2
interpolation2degre=a*x.^2+b*x+c*ones(1,length(n))

residus=(n-interpolation2degre)
plot(x',[n' interpolation2degre' residus'],[2 -2 3])
legend(["indice n" "interpolation_du_second degré" "residus"])
scf(1)
plot(x',residus')
legend(["residus"])

davidstr

Vous pouvez allez voir ce lien https://www.researchgate.net/publication/359443297_Prime_numbers_crible_and_something_surprising

lourrran

Ca c'est du beau poisson d'avril... un truc préparé une semaine à l'avance, pour une publication le 1er avril.
Beaucoup de travail, juste pour faire une blague. Bravo.

davidstr

Pas du tout

davidstr

Vérifie avant de discréditer

lourrran

Vérifier quoi ? 

Tu calcules un truc, qui a un rapport avec les nombres premiers, et tu obtiens une courbe qui ressemble à une sinusoïde.  Et cette courbe, tu as décidé de l'appeler résidus.
Bon, pourquoi pas.  

Et par ailleurs, tu as une autre courbe, en rouge, que tu as également appelée résidus, et qui est quasiment une ligne droite.

Il doit y avoir un rapport entre ces 2 courbes, qui s'appellent toutes les 2 résidus.

Apparemment, tu trouves ça très intéressant.  Quand tu auras posté toutes tes courbes, tu comptes nous dire ce qu'elles représentent ? Ou tu comptes garder le secret pour toi ?

Pour l'instant, l'information que tu as donnée,  ce que tu as découvert, c'est que  :  

Si P_n iest un carré parfait et sqrt(P_n) n'est pas divisible par un membre de la liste des nombres premiers

Alors sqrt(P_n) est premier

Ce qui est la définition d'un nombre premier : si $U_n$ n'est pas divisible par un nombre plus petit que lui, alors $U_n$ est premier...

Après cette découverte, tu affiches des courbes. 
Tu nous dis aussi que si $p$ est premier, $p^2$ est de la forme $12k+1$ ... oui  c'est un exercice qu'on faisait au collège il y a 30 ans , découverte banale (et en plus, il faudrait corriger et préciser $p$ premier autre que 2 ou 3, passons sur ce point) ...

Entre des pseudo-découvertes, qui ne sont que des banalités, et des courbes qui représentent un truc mystérieux, où est l'intérêt de tout ça ?

davidstr

En fait je prends les nombres premiers
Je calcul le n tel que p^2=1+12n
Je trace ainsi les n

Et la courbe ax^2+BX+c

J'appelle résidus la différence entre ces deux courbes

Les résidus sont les mêmes

Heuristique

Tu traces les $n$, soit. Mais en fonction de quoi ?

Quelle est la fonction qui est tracée en bleu dans ton premier graphique ? Que représentent les abscisses et les ordonnées sur ton graphique ?

De ce que je comprends, si $x$ est la variable des abscisses, la fonction représentée en vert est $x \mapsto ax^2+bx+c$, OK.

Mais en bleu, tu représentes la fonction $x \mapsto n$, de quelle manière ce $n$ dépend-t-il de $x$ ?

davidstr

la courbe bleus des n a pour abscisse les entiers de 1 en 1 de la longueur de n

Finalement j'ai intercepté cette courbe bleu avec le modèle x donne 

lourrran

Dans ton dernier graphe, tu as un point qui vaut en gros x=2 500 000 et y=-8E11. 
On parle du 2 500 000 ème nombre premier ?  ou d'un nombre premier proche de 2 500 000 ? ou d'autre chose encore ? 
Et le y correspondant, le -8E11, c'est a priori un résidu, donc un écart entre 2 calculs. Quels calculs ?

Dom

Si j’ai bien compris : le reste serait plus approprié que le résidu. Mais je ne critique pas. 

davidstr

lourrran a dit :

Dans ton dernier graphe, tu as un point qui vaut en gros x=2 500 000 et y=-8E11. 
On parle du 2 500 000 ème nombre premier ?  ou d'un nombre premier proche de 2 500 000 ? ou d'autre chose encore ? 
Et le y correspondant, le -8E11, c'est a priori un résidu, donc un écart entre 2 calculs. Quels calculs ?

en effet mais n vaut alors 1.4E14

davidstr

on parle du 2 500 000 ème nombre premier qui vaut 1.4E14

lourrran

Ok, donc on sait ce que représente l'axe des abscisses.
Et l'axe des ordonnées, suspense ...

davidstr

lourrran

  L'axe des ordonnées représente n tel 1+12n=p^2.

[Inutile de reproduire le message précédent. AD]

lourrran

Non, l'axe des ordonnées du graphique de 11h43 ne représente pas ça. On n'aurait pas des valeurs négatives. 
Mais c'est compris. Cette courbe représente l'écart entre le $n$ en question et la parabole bla bla bla.

Ok ... et donc, la découverte du jour, c'est quoi ?   
- Le résidu suit une courbe régulière ?  oui, c'était 10000% prévisible.
- Le résidu suit une loi plus ou moins en $x^3$ ... oui.

Recherche les formules qui parlent de la densité des nombres premiers, celles qui sont connues depuis Legendre, il y a 200 ans, et tu pourras expliquer tes pseudo-résultats.

davidstr

Merci. On peut donc clore le sujet.