Premiers consécutifs

zephir · July 2020

Bonsoir à tous.

C'est probablement un sujet récurrent. Soit $p$ un nombre premier. Je note $q$ le nombre premier suivant de $p$.
Je considère la conjecture : $q-p\le \ln(p)^2$ (logarithme népérien).
Il s'agit d'une forme forte de la conjecture de Cramer.
Comme j'ai calculé les 200 millions premiers nombres premiers, j'ai vérifié dessus cette inégalité.
Elle est donc vrai pour ceux là.

Voici ma demande : est-ce que quelqu'un dispose de plus de nombres premiers pour valider ou infirmer cette conjecture ?
Question subsidiaire qui s'adresse à tous et, en particulier au grand spécialiste noixdetoto (que je salue). Quel est l'état de l'art en la matière ?

Cordialement,
zephir.

noix de totos · July 2020

Bonjour Zephir et salut à toi aussi,

En 2009, D. Goldston, J. Pintz, and C. Yildirim montrent que $\displaystyle \liminf_{n \to \infty} \frac{p_{n+1}-p_n}{\log p_n} = 0$. Autrement dit il existe une infinité de couples $(p,q)$ de nombres premiers tels que $p<q$ et, pout tout $c > 0$, $q-p < c \log p$.

En 2014, Y. Zhang, reprenant et étendant les idées de G-P-Y et y associant un ancien travail dû à Bombieri, Friedlander et Iwaniec des années 80, montre que le résultat est vrai en remplaçant $\log p$ par une constante : il existe une infinité de couples $(p,q)$ de nombres premiers tels que $p<q$ et $q-p < 70 \times 10^6$. C'est la plus grosse avancée en théorie des nombres premiers de ces dernières années.

Peu de temps après, la constante a été abaissée : d'abord à $600$ par Maynard, puis à $246$ dans un projet Polymath.

Cela répond-il à ta question ?

zephir · July 2020

Merci pour ces informations dont je disposais.
Cela ne répond pas tout à fait à mes questions
La majoration que je propose est présumée vrai pour tout premier $p$ de successeur premier $q$.
Cette majoration est vrai pour les 200 millions premiers entiers. Est-elle vrai pour d'autres premiers
et jusqu'où.
Une démonstration à la Tao est-elle envisageable ?
Ce n'est pas un problème facile.

noix de totos · July 2020

Ce que je t'ai mis est le mieux que l'on ait dans ce type de problème aujourd'hui.

Dans l'état actuel des connaissances, du moins des miennes, il y a peu d'espoir de faire mieux dans un avenir prochain.

Poirot · July 2020

@zephir : les premiers dans le résultat de Goldston, Pintz et Yildirim (dont j'ai écorché le nom) sont bien consécutifs.

@ndt : attention, il faudrait lire "pour tout $c > 0$, il existe une infinité de nombres premiers tels que...".

LEG · July 2020

Bonjour
si cela t'amuse voici une liste de nombre premiers de la Famille 1 modulo 30 < 3 000 000 000
tu trouveras toujours des nombres premiers avec l'écart minimum de 30, et il y en a surement une infinité

je joins le derniers fichier, moins volumineux ...tu peux recalculer ta formule sur un écart minimum de 30 en utilisant une famille sur les 8 , elles sont disjointes et de même densité....L'algorithme est identique pour les 8 familles il fonction avec un groupe de 8 nombres premiers $\in(7 ; 31)$

je peux te faire parvenir le programme ("et la page d'instruction très simple") par mp et ton mail.
Ce qui te permettra de choisir les familles que tu veux " " et montrer que pour toute famille sur les 8 , il y a toujours deux premiers consécutif avec un écart de 30 " "

noix de totos · July 2020

Oui, ma phrase est mal écrite : il faut lire pour tout $c > 0$, il existe une infinité de nombres premiers $p < q$ tels que $q-p < c \log p$.

L'important dans cette phrase est le "$> 0$", car le théorème des nombres premiers montre que cette assertion est vraie pour tout $c \geqslant 1$.

Autre chose : on n'est pas obligé d'aller chercher des modèles aussi compliqués que Cramer pour obtenir des informations sur $p_{n+1} - p_n$. La démarche ci-dessous, peu connue, n'utilise que le fait, dont on a parlé récemment dans un fil de Christophe C, que la somme des inverses des nombres premiers diverge.

On utilise le lemme suivant :

Lemme. Soit $(u_n)$ une suite de réels strictement positifs telle que $\sum_n \frac{1}{u_n}$ diverge. Alors, pour toute suite $(v_n)$ de réels strictement positifs et tout entier naturel $n_0$, il existe un entier $n_1>n_0$ tel que
$$v_{n_1} u_{n_1+1} - v_{n_1+1} u_{n_1} < u_{n_1}.$$

On applique ça à $u_n = p_n$ la suite des nombres premiers et $v_n=n$, pour en déduire qu'il existe une infinité d'entiers $n$ pour lesquels l'inégalité
$$\frac{p_{n+1}-p_n}{p_n} < \frac{2}{n}$$
est valide. En particulier, $\displaystyle \liminf_{n \to \infty} \frac{p_{n+1}-p_n}{p_n} = 0$.

En prenant $v_n = n \log n$, on en déduit qu'il existe une infinité d'entiers $n$ suffisamment grands pour lesquels l'inégalité
$$p_{n+1}-p_n <(n+1) \log(n+1) - n \log n +1$$
est valide.

Etc.

zephir · July 2020

@noix de toto:
Le résultat du lemme aurait pu être écrit sous la forme plus sympathique : $$\forall n>0, \exists k>n\ $:\$ \dfrac {v_k}{u_k}-\dfrac {v_{k+1}}{u_{k+1}}<\frac 1 {u_{k+1}}$$ Dont la négation entraîne trivialement la convergence de la série de TG $\frac 1 {u_n}$.

Le dernier résultat connu sur les constantes $C$ telle que : $$\forall n>0, \exists k>n\ $:\$ p_{k+1}-p_k\le C$$ est : $C\leq 300$. As-tu une idée de la manière par laquelle ce résultat a été obtenu ?
Est-ce un raffinement du crible de Selberg ?

Cordialement,
zephir

noix de totos · July 2020

Oui, c'est la démonstration du lemme.

Quant à $C$, on peut prendre $C=246$, comme indiqué dans mon $1$er message. Elle est effectivement due à un raffinement du crible de Selberg et de calculs numériques intensifs, étendant ainsi la méthode de Maynard qui simplifiait celle de Zhang.

Ce projet Polymath montre aussi que la meilleure borne possible que l"on peut atteindre sous ces considérations de crible est $\displaystyle \liminf_{n \to \infty} \left( p_{n+1} - p_n \right) \leqslant 6$, pour laquelle on suppose l'hypothèse d'Elliott-Halberstam généralisée.

Sans condition, les auteurs montrent aussi que, pour tout $m \in \mathbb{Z}_{\geqslant 1}$, $\displaystyle \liminf_{n \to \infty} \left( p_{n+m} - p_n \right) \ll m e^{3,82165 \dotsc m}$, où la constante impliquée est absolue, et donnent des résultats explicites pour $m \in \{1,2,3,4,5\}$. Par exemple, $\displaystyle \liminf_{n \to \infty} \left( p_{n+5} - p_n \right) \leqslant 80 \, 550 \, 202 \, 480$.

zephir · August 2020

Bonsoir
Je réveille ce fil car j'ai réussi à tester l'inégalité $A = \ln(p)^2+1-(q-p)>0$ sur le premier milliard de nombres premiers.
Sur chaque tranche d'un million, à partir du second, j'ai calculé $\min(A)$.
Les résultats sont dans le tableau joint, en 3eme colonne.
La seconde colonne est le temps de calcul, en secondes.
La première est le rand du million.
Rappel : $p$ est un nombre premier et $q$ est le nombre premier suivant de $p$.

La question demeure : est-ce que $A\geq0$ est vrai pour tout $p$ ?
J'ai tendance à penser que oui. Et vous ?
Cordialement,
zephir.

P.S. le fichier des nombres premiers fait un peu plus de 13 GO, donc non transmissible.
temps total en secondes = 100095.625
nombre de nombres premiers = 1000000000
milliardième nombre premier = 22801595381

LEG · August 2020

Bonjour
Si ça t'intéresse
voici le nombre de nombres premiers par famille inférieur au milliardième nombre premier = 22 801 763 531
sans compter 2,3 et 5.

zephir · August 2020

Bonjour LEG,
et merci pour tes infos.
Je constate que nous n'avons pas le même milliardième nombre premier.
Peux-tu expliquer ton"par famille". Je suppose que cela a une incidence sur ta méthode
de détermination des nombres premiers.
Ma méthode est simple : je commence par stocker le premier million de nombres premiers puis,
pour chaque entier impair $q$, je teste sa divisibilité par les premiers $\le \sqrt q$.
tant que $q<10^9$

edit : remplacer "tant que $q<10^9$" par "tant que nombre de premier $<10^9$".

lourrran · August 2020

zephir,
Si tu fais come tu dis, tu trouves les nombres premiers inférieurs à 1 Md, et non les 1 Md premiers nombres premiers.
Cette petite imprécision (ou le petit bug caché dans cette imprécision) pourrait expliquer la différence.

zephir · August 2020

Désolé, je fais bien "nombre de premiers inférieur à $10^9$. Je rectifie mon erreur.
Je viens de faire une vérification du fichier des nombres premiers. Il y en a bien un milliard et le dernier est bien :$22801595381$.
Je pense que Leg a fait une recherche par famille et son dernier nombre premier est au delà du milliardième.
Je vais chercher son rang exact.

LEG · August 2020

Re @zephir
effectivement on a pas le même milliardième , je pense qu'il y a une erreur dans ton algorithme
mon algorithme est une variante d'Ératosthène , et largement démontré ..donc à mon niveau pas possible qui il y ait une erreur...

1) par famille(i) le crible utilise les 8 premiers $p\in{7;31}$ et les premier $P\leqslant\sqrt{N = 15k}$

2) la limite $N$ est donc dans ton cas, supérieur à ton premier $22 801 595 381$ et non à $q=10^9$

3) dans mon cas la limite exacte $N$ est $22801763550$ pour chaque $Fam(i)$ on crible modulo 30 ; ce qui ne change en rient ....

mon programme extrait en premier, les nombre premiers $P$ inférieur à la racine de cette limite $N$ avec le crible classique d'Ératosthène, afin de les utiliser avec les 8 premiers (i) $=p$

pour chaque fam(i) on fixe le tableau d'entiers en progression arithmétique de raison 30 que l'on va cribler.
soit : $N = (22801763550 // 30)$ ce qui te donne : 760 058 785 entiers impairs à cribler par $Fam (i)$

exemple pour la $Fam(1)$ où il faudra retrancher 1 au résultat car il a compter 1 qui n'est pas premier au lieu de commencer à 31:

>Allocation du Tableau en cours...
>Allocation Terminée!
>Calcul du tableau en cours...
>Calcul du tableau terminé!
>Le dernier nombre est:
22801763221
>trouvé à la position:
124997159

pour la $Fam(7)$

>Allocation du Tableau en cours...
>Allocation Terminée!
>Calcul du tableau en cours...
>Calcul du tableau terminé!
>Le dernier nombre est:
22801763527
>trouvé à la position:
125001682

etc ...etc pour les 6 autres $Fam$

la position est bien entendu le dernier nombre premier , donc le énième...
lorsque tu fais la somme des positions tu as bien $1 000 000 000$ de nombres premier soit environ 125 000 000 premiers par famille.

l'algorithme est identique pour les 8 familles , d'où : une même densité oscillatoire par famille avec de faible variation en fonction des limites $N$ fixées .
Ce qui permet de ne plus s'occuper des 2,3 et 5 avec leurs multiples qui représentent quand même 73,33.....% des entiers naturels avec seulement 2 nombres premiers impairs ....

Tu peux t'amuser d'ailleurs à refaire tes calculs par famille et tu verras que tu obtiendra les mêmes résultats quelque soit la $Fam(i)$ fixée. (" c'est ce que j'ai fais pour la conjecture de Goldbach, en utilisant qu'une famille ")

Je ne pense pas que cela soit difficile de modifier ta formule en ce sens ....si besoins est .

si cela t'intéresse je peux même t'indiquer le nombre de nombres premiers qu'il y a entre la limite $N$ fixée et $2N = 45603527100$
par Famille , donc il y en aura moins de 1 000 000 000 de toutes évidences.

mais cela te permettra de te rendre compte des légères différences oscillatoires par famille .

LEG · August 2020

@zefir , @ lourrran à raison

tu ne peux avoir 1 milliard de nombres premier avec la limite $n = 10^9$ car cela veut dire que tous les entiers $< 10^9$ sont premiers :-S

tu as surement demandé nombre de nombres premiers $< 10^9$

zephir · August 2020

Après calculs, je note :
$q1 = 22 801 595 381$ mon milliardième nombre premiers
$q2 = 22 801 763 531$ le milliardième de LEG
je joins un fichier .CSV qui contient en deuxième colonne les nombres premiers entre $q1$ et $q2$.
il y en a $7114$.
on a :$D=q2-q1$ . On remarque que $7114/D = 0.0423$ et $1/ln(q1) = 0.0419$

D'autre part, l'inégalité que je propose est bien réalisé pour ces $7115$ nombres premiers.
quelqu'un peut-il vérifier que les nombres en deuxième colonne de mon fichier sont bien tous premiers ?

Merci d'avance.
Cordialement,
zephir.

LEG · August 2020

@zephir
on va pas s'amuser à tester tes 7115 nombres premiers.

comment as tu calculé ton milliardième nombre premier ou ton milliard de nombres P...?

le crible d'Ératosthène te donne la quantité de nombres premiers $P\leqslant(N = 22 801 763 550 )$
dans le pdf joint tu as la quantité par famille avec le dernier premier par famille.

si ton premier était bien le milliardième en criblant jusqu'à cette limite il n'en manquerait pas 7116 !
donc prend $N = q_1 +1= 22801595382$ et crible avec Ératosthène jusqu'à cette limite N et tu verra si tu en a 1 milliard à 1 ou 2 près.

il y en a 999 992 884 et non un milliard , soit 7116 de moins (sans compter 2, 3 et 5)

zephir · August 2020

@leg :
Ma méthode de calcul est la suivante :
Je tabule les nombres premiers jusqu'à un million (de nombres premiers) et un million au carré vaut $10^{12}$ et nos deux milliardièmes sont inférieurs..
Ensuite je teste, pour chaque entier impair sa divisibilité par l'un de ces nombres premiers.
j'ai écrit un code en fortran en calculant en mode entier long (8 octets)
Cette méthode pourrait trouver premier des nombres qui ne le sont pas.
Il faut pour cela que la fonction modulo ne trouve pas 0 alors que c'est bien un zéro.

Mon fichier de nombres premiers (un par ligne) comporte un milliard de lignes.
donc, si ton assertion est exacte, je dois avoir dans mon fichier $7115$ nombres non premiers !
Possible mais peu probable.
Le crible d'Erathostène (orthographe ?) par famille pose quelques problèmes sur le décompte, puisque dans les huits familles on n'a pas le même nombre de premiers.
Peux-tu vérifier ta procédure de fin de comptage ?

LEG · August 2020

le crible d'Ératosthène que j'utilise à déjà été testé des centaines de fois depuis 2003 ...
il n'y a pas d'erreur de comptage puisqu'il crible par famille en progression arithmétique de raison 30, donc à la fin il compte simplement les nombres premiers de la famille qui est criblée, c'est tout .

Tu ne connais pas le programme...qui est utilisé.

Tu ne peux pas dire que dans ton fichier tu as 7115 nombres non premiers ! car ton milliardième nombre premier n'est pas le bon... !
Ta méthode est fausse, ce n'est pas précis comme le crible d'Ératosthène qui crible de 1 à N sans erreur en utilisant les nombres premiers $P\leqslant\sqrt {22801763550}$ c'est-à-dire $P\leqslant{151002}$

Et donc je ne vois ce que vient faire ton million de premiers, puisque avec 150 000 premiers au maximum c'est suffisant ...
Le dernier premier P à utiliser est : $150 991$ dans ton cas comme dans le mien !

Voici un exemple du début du fichier de la Fam(1) : 20 - 1 ("ils sont trop lourds à envoyer')
21611547091 118751901
21611547121 118751902
21611547541 118751903
21611547781 118751904
21611547871 118751905
21611547901 118751906
21611548141 118751907
21611548201 118751908
21611548561 118751909
21611548591 118751910
21611548771 118751911
21611549101 118751912
21611549131 118751913
21611549161 118751914
21611549341 118751915
21611549431 118751916
21611549461 118751917
21611549551 118751918
21611549821 118751919
21611549941 118751920
21611550001 118751921
21611550061 118751922
21611550091 118751923
21611550511 118751924
21611550601 118751925
21611550841 118751926
21611550991 118751927
21611551051 118751928
21611551081 118751929
21611551441 118751930
21611551531 118751931
21611551771 118751932
21611552101 118751933
...........
et ci-dessous la fin du fichier

22801756801 124997131
22801756921 124997132
22801757371 124997133
22801757401 124997134
22801757491 124997135
22801757731 124997136
22801758151 124997137
22801758211 124997138
22801758541 124997139
22801758571 124997140
22801758781 124997141
22801758841 124997142
22801759111 124997143
22801759471 124997144
22801759921 124997145
22801760161 124997146
22801760671 124997147
22801761001 124997148
22801761391 124997149
22801761511 124997150
22801761571 124997151
22801761721 124997152
22801761901 124997153
22801762171 124997154
22801762201 124997155
22801762441 124997156
22801762861 124997157
22801763041 124997158
22801763221 124 997 159 = la position qui est le nombre de nombres premiers dans cette famille pour N < 22 801 763 550.
La série est indicée en commençant par 2 correspondant à P = 31.
soit 124997158 premiers.Et voici le nombre de nombres premiers inférieurs à la racine de $N$ ; $150002$
Microsoft Windows XP [version 6.1.7601]
(C) Copyright 1985-2001 Microsoft Corp.

E:\executable algo P(30)>prime.exe -p 150002
Prime Number decomposition!
Serie 1 : OK
Number of prime numbers for serie 1 : 1721
Serie 7 : OK
Number of prime numbers for serie 7 : 1743
Serie 11 : OK
Number of prime numbers for serie 11 : 1747
Serie 13 : OK
Number of prime numbers for serie 13 : 1731
Serie 17 : OK
Number of prime numbers for serie 17 : 1726
Serie 19 : OK
Number of prime numbers for serie 19 : 1717
Serie 23 : OK
Number of prime numbers for serie 23 : 1738
Serie 29 : OK
Number of prime numbers for serie 29 : 1735

E:\executable algo P(30)> total 13858 nombres premiers
on est loin du million... ::o

Au cas où tu en as besoin pour ton programme je te joins les 8 fichiers des nombres P < racine de N.

zephir · August 2020

LEG a écrit:

tu ne connais pas le programme...qui est utilisé.

Je ne demande qu'à le connaître pour essayer de trouver la faille, s'il y en une.
Si tu veux bien me faire faire la connaissance de ton code.
Je suis en train de repasser mon fichier d'un milliard de nombres premiers pour vérifier.
En effet, mon milliardième étant plus petit que le tien, si je suis en erreur, je dois trouver dans ma liste des nombres non premiers (7115).

De nous deux, l'un des deux a tort. j'ai posté un fichier (newprm.csv) plus haut où je calcule par ma méthode les nombres premiers entre $q1$ et $q2$ en 2eme colonne.
question : sont-ils tous premiers et sont-ce les seuls dans l'intervalle ?
Si oui (comme je l'ai vérifié) alors mon code est correct, sinon ...

LEG · August 2020

Je ne demande qu'à le connaître pour essayer de trouver la faille, s'il y en une.

Rassure-toi si il y avait une erreur que ce soit à l'UQUAM (Montréal) université de Nice, l'iut de Grenoble, ou l'ESSI de Sophia Antipolis Nice, qui m'ont fait le programme...il y a longtemps qu'ils s'en seraient aperçu.

Je pourrais t'envoyer un petit exécutable par mail en message privé.
Il fonctionne sous dos avec la commande [cmd], cela te permettra de vérifier ton programme pour de petites limite N.
Ce que tu peux déjà faire avec les 8 fichiers csv que je t'ai joint.

Le programme que j'ai utilisé pour le milliardième premier < à la limite $N < 22 801 763 550$
c'est un programme Python fait par un prof de maths en retraite, et qui a été retranscrit en C++ par une personne de l'université de Grenoble, dont on ne peut mettre en doute son programme...:-D
(la limite de ce programme en deux parties va jusqu'à 15 000 000 000 000

Je peux aussi t'envoyer l'exécutable nb premier modulo 30 par famille il est en C++ mais je n'ai plus le source...
Il est simple à utiliser avec les instructions, pour une limite < 450 000 000 000. ce qui fait de gros fichiers de nombres premiers... dont tu as eu un extrait dans le post précédent.

Déjà calcule tes nombres premiers inférieur à $150 002$ et tu pourras regarder ce qui cloche dans ta méthode si ton nombre est différent du mien et si tes premiers ne correspondent pas aux miens pour cette limite. ("ce qui pourrait être le cas...")

Concernant ton fichier avec tes 7115 nombres, j'ai juste vérifié les nombres premiers de la fam (1) = 30k + 1 avec la fin de ma liste que je t'ai postée, ils correspondent bien aux miens donc je ne vois pas pourquoi cela serait différent pour les 7 autre familles ...

[Chaque phrase, tout comme chaque nom propre, commence toujours par une majuscule. AD]

LEG · August 2020

Bonjour

[Chaque phrase, tout comme chaque nom propre, commence toujours par une majuscule. AD] Ok AD, excuse moi.

@zephir
Voici un code en Python , "mais qui est limité à cause de la mémoire Python" pour $N = 27 000 000 000$ le temps est de 182 secondes ; il faut le retranscrire en C++ pour la même limite $N$ il met 2 secondes avec une limite $N$ de 7500 milliards; par contre cela t'expliquera très bien le déroulement de l'algorithme.

Pour reconstruire la valeur d'un nombre premier, tu prends l'indice (i) du rang de la cellule ou du nombre premier représenté par [1], que tu multiplies par 30 et tu rajoutes le premier terme $i_0$ de la $Fam(i)$ ; les indices sont numéroté de 0 à n // 30.

Exemple: $Fam(1)$ en progression arithmétique de raison 30 , limite $N = 3000$ ; tu as donc 100 indices $i$ de $0\: à \:99$ ; 3000 // 30 = 100

Illustration des nombres premiers :

Crible: [.1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1]
L'indice $i_8$ du nombre premier P vaut : $8*30 + 1 = 241$ .

( Bien entendu dans cette famille l'indice 0 = 1 n'est pas un nombre premier ). Ce qui donne 51 - 1 nombres premiers; le dernier premier est $99*30 + 1 = 2971$

from itertools import product
from time import time
from os import system
import math

def candidate_range(n):
    cur = 5
    incr = 2
    while cur < n+1:
        yield cur
        cur += incr
        incr ^= 6  # or incr = 6-incr, or however


def eratostene(n):
    n = int(n**0.5)  #(si on fusionne les deux cribles il faudra rentrer, int((2n)**0.5) pour Goldbach.
    prime_list =[2,3]
    sieve_list = [True] * (n+1)
    for each_number in candidate_range(n):
        if sieve_list[each_number]:
            prime_list.append(each_number)
            for multiple in range(each_number*each_number, n+1, each_number):
                sieve_list[multiple] = False
    #print(prime_list[3:])
    return prime_list[3:]  


def demander_N():
    n = input("Donnez N: ")
    n = int(n.strip().replace(" ", ""))
    n = int(30 * round(float(n)/30))
    return n


def E_Crible(premiers, n, fam):
    start_crible = time()
	
    # On génère un tableau de N/30 cases rempli de 1
    crible = n//30*[1]
    lencrible = len(crible)
    GM = [7,11,13,17,19,23,29,31]
    # On calcule les produits: j = a * b
    
    for a in premiers:
        for b in GM:
            j = a * b
            if j%30 == fam:
                index = j // 30  # Je calcule l'index et On crible directement à partir de l'index
        for idx in range(index, lencrible, a):  # index qui est réutilisé ici...
            crible[idx] = 0
        #print(index)
            
    total = sum(crible)  ## à la place on utilise ce tableau d'Ératosthène criblé, pour utiliser ce tableau dans le crible de Goldbacn, on return "crible:", crible
    print("crible:", crible)  
    print(f"Nombre premiers criblés famille {fam} : {total} ----- {int((time()-start_crible)*100)/100}")


def main():
    # On demande N a l'utilisateur
    n = demander_N()

    # On récupère les premiers de 7 à ?N
    premiers = eratostene(n)
    #print(f"nombres premiers entre 7 et (n**0.5): {len(premiers)}") # nombre de premiers qui criblent

    start_time = time()
    # On crible
    E_Crible(premiers, n, 1)  ## pour changer de Fami (i) on remplace la dernière valeur 1 par (1,7,11,13,17,19,23,29)
    temps = time()-start_time
    print(f"--- Temps total: {int(temps*100)/100} sec ---")


main()
system("pause")

Pour regarder les différents nombres ou index qui interviennent tu déverrouilles les print

Tu peux rajouter une fonction afin, qu'en fin de programme il te reconstruise la valeur des nombres premiers , mais ça prend de la mémoire et du temps .

Pour les deux exécutables en c+ tu m'envoies ton adresse mail par mp.

Stator · August 2020

D'après Caldwell :

"The 1,000,000,000th prime is 22,801,763,489"

LEG · August 2020

@Stator, c'est exact il correspond bien au dernier premier de la famille $29 + 30k$ du pdf que j'ai transmis plus haut.
est le premier $22801763531$ est le milliardième +1 nombre premier. en excluant 3 et 5.
Je ne connaissais pas ce site...il est bien.
Merci.

zephir · August 2020

leg a écrit:

total 13858 nombres premiers

ce que tu annonce comme nombre de nombre premiers $\leq 150001$
J'ai repris tes huit fichiers et le décompte des nombres premiers.
J'ai récupéré les premières colonnes de tes fichiers, je les ai mis dans une colonne excel.
Ils commence à 7, se termine à 150001 et il y en a, si j'en crois le tableau excel : 13846
J'ai d'autre part lu les entiers de mon fichier qui ne dépassent pas 150001 et je trouve : 13849
soit 3 de plus qui sont 2,3,5.
Il y a dans tes fichiers des premiers supérieurs à 150001
2 de plus dans F1, F7,F11,F17 et F23. Il y a un de plus dans F29.
Je joins le fichier ordonné des premiers <150002, extrait de tes fichiers.

Il semble donc possible que tu aies fait une erreur en phase terminale ?
J'ai d'autre part relancé le test de primalité de mon fichier de un milliard d'entiers. C'est long.
J'en suis à 838 millions, tous premiers.

zephir · August 2020

@leg : J'ai récupéré ton code python et je l'ai fait tourner. Il tourne et il est rapide. Je ne suis pas encore allé jusqu'à un milliard. J'ai juste vérifié le nombre de premiers des familles 1 et 7 jusqu'à 150002. Je trouve 1718 et 1741.

zephir · August 2020

@leg : cela se précise. Ton milliardième est en fait le milliardième + 3. Comme tu omet les nombres 2,3 et 5, le compte est bon.
Mon compte est donc faux. Il y a des nombres non premiers dans ma liste.
Je soupçonne un overflow dans le calcul de int(sqrt(real(I))) en fortran. I est un entier long (8octets). Que fait le compilateur ? Il ne me reste plus qu'à chercher quels sont les nombres non premiers de ma liste.

LEG · August 2020

@zephir

1_) : Attention les 8 fichiers du programme prime.exe te donne le nombre de nombre premiers inférieur à une limite mais avec parfois un ou deux nombres P supplémentaire. C'est le premier programme qui a été fait en 2000.
Il aurait fallu le refaire à l'époque mais, comme ça n'avait aucune importance, on l'a laissé comme ça.

2_) : Le premier fichier que j'ai mis sont les résultats du programme Nbpremier win32 qui lui ne fait pas d'erreur sauf une pour la fam(1) la seule erreur consiste dans le programme à compter le premier terme donc 1, N° d'indice 0, mais qui n'est pas premier pour la raison suivante : pour reconstruire une valeur tu multiplies le n° d'indice par 30 et tu rajoute le premier terme d'indice 0... c'est tout.

3_) Tu as vue que @stator à confirmer le milliardième premier $22,801,763,489$ qui est bien dans le fichier et que celui que j'indiquai avec une erreur de 1 ou 2 est bien le P = 22 801 763 531 qui est le milliardième + 1 en excluant 3 et 5.

4_) : Le code python que tu as est limité par fam (i) à $N = 29 100 000 000$ au delà il rame , la cause c'est la mémoire virtuelle de python..
Il te permet de regarder le comportement de l'algorithme par Famille , les index, les nombres premiers représentés par 1, le nombre de premiers de base qui interviennent dans le crible et la valeur de ces premiers .

Mais attention pour une limite $n = 3 000 000 000$ il va mettre du temps pour écrire = print les entiers 1......jusqu'à n//30. Donc tu désélectionne print , qui devient # print.

Je ne suis pas programmeur loin s'en faut, mais je connais bien mon algorithme modulo 30.

Si tu as besoins des nombres premiers inférieurs à 10 000 000 000 par exemple je pourrai joindre prime.exe ou nb premier
par mail , en passant par message privé.

Je ne sais pas si tu es programmeur, car le programme python fonctionne mieux en C++ et de loin....c'est celui que j'utilise pour connaître le nombre de premiers pour les limites $N > 30 000 000 000$ et il est juste...:-D

Mais ne te casse pas la tête pour extraire tout le milliard de nombres premier < 22 801 763 540 par famille; nb premier met 2 minutes, ensuite tu peux sauvegarder les nombres premiers, pars fichiers de 3 125 000 nombres...environ.

There are 1,000,000,003 primes less than or equal to 22,801,763,540. Je suppose qu'il compte 2,3 et 5. Référence du site de @pastor

LEG · August 2020

@zephir Tu n'est pas sortie de l'auberge pour chercher l'erreur ,..

Est ce que pour la petite valeur limite $ N < 150001$ des 8 fichiers csv ton algorithme montre des différences de nombres non premiers ? avec mes 8 fichiers CSV.?

Autre information pour mes programmes rentre toujours une valeur N = 30k à cause de la progression arithmétique de raison 30 , sinon effectivement le programme peut en donner 1 ou 2 de plus par famille..

voila le fichier fam 1 avec nbPremier $N \leqslant\:150 000$

Et un petit crible d'Ératosthène de nombres premiers pour $N\leqslant\sqrt{24000000000}$

import math
from time import time
from os import system

def Eratosthene(n):
    Tab=[]
    premiers=n*[True]
    premiers[0]=premiers[1]=False
    for p in range(2,n):
        if premiers[p]:
            Tab.append(p)
            for i in range(p*p,n,p):
                premiers[ i]=False
    return Tab

n=int(input("doner la valeur de n :"))  
T=Eratosthene(n)    
print(T)
system("pause")

zephir · August 2020

@leg : Merci pour ta contribution, mais nous nous sommes écarté du sujet.
Je m'intéresse à la majoration qui est dans mon premier message.
Je l'ai vérifié pour les nombres premiers $< q1$ (enfin, je pense)
pour les premiers entre $q1$ et $q2$ l'écart reste supérieur à $395$ (à fortiori positif) et il plafonne un peu en dessous de $600$.
Est-ce que cette majoration va nous jouer le coup du "nombre de skews" ?

LEG · August 2020

@zephir je comprends , et bonne continuation.

zephir · August 2020

Retour pour signaler un problème d'arrondi qui explique pourquoi $q1<q2$.
Mon algorithme déclare premier un entier $n$ de la forme $p*p$, avec $p$ premier lorsque le
programme trouve $int(sqrt(real(n))) < p$, ce qui fait que la divisibilité par $p$ n'est pas testé.
Cela se produit $7112$ fois, ce qui explique qu'entre $q1$ et $q2$ on trouve $7114$ nombres premiers.
Reste $2$ non expliqué, non premier et déclaré premier.

Mon algorithme est très simple. Si je veux la liste des nombres premiers inférieurs à $N$, je liste les nombres premiers inférieurs à $\sqrt N$ et pour tout entier $n$, je teste sa divisibilité par les premiers (listés) plus petit que $\sqrt n$.
J'aimerai savoir quelle est la complexité de mon algorithme, en terme de nombre de divisions que je dois faire..
Pour cela, si je note $d_n$ le plus petit diviseur différent de $n$, cela reviens à chercher la somme des $\pi(d_k)$ pour $k\le n$. Quelqu'un a-t-il une estimation de ce nombre ?
Il vaut mieux peut-être ouvrir un nouveau fil pour cette question ?

LEG · August 2020

Bonjour
@zephir (sauf erreur)

Je pense que ton programme comporte une erreur , par conséquent il vaudrait mieux que tu indiques le code de ton programme...

La complexité de ton algorithme dépend de la façon dont ton programme est effectué...

Si tu prends tous les entiers impairs supérieur au dernier nombre premier $P\leqslant\sqrt{N}$ et inférieur à $N$, et que tu testes leur divisibilité pour ensuite le classer dans ta liste $P_n > P$ si il est premier $P_{n+1}$, tu ne devrais pas avoir d'erreur...

Autre idée, pour aller plus vite, il te faudrait prendre uniquement les entiers naturels impairs non multiples de 3 et 5

En suivant le cycle {6.4.2.4.2.4.6.2} :

1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59,61,67.......etc...2999 <$N$ et bien sûr en commençant par le premier impair $n > P$ le dernier premier $P$ de ta liste de premiers de base qui te servent à cribler...
Ou en créant un tableau de 8 colonnes modulo 30:

1 , 7, 11 , 13 , 17,19 , 23 , 29
31,37,41,43 , 47, 49, 53, 59 ...etc...ce qui va plus vite à écrire

Par exemple $N=3000$ , $P\leqslant\sqrt{N} = 53$ tu commences avec $n$ tel que $P<n\leqslant\:N$ , donc 59, que tu vas tester avec tes 13 premiers; comme il est premier $P' > P$ ton programmes ne le marque pas 0, par exemple, et tu réitères avec $n + 1 = 61$...etc...etc.. jusqu'à la fin.

Mais ça va être long.....car l'algorithme n'est pas du tout optimisé...
Sauf si tu as déjà une liste de nombres premiers en base de donné par exemple les 500 000 000 premiers nombres premiers. Il ne t'en reste plus que la moitié à trouver...:-D

Ou alors je peux t'envoyer par mail, les 350 fichiers de nombres premiers, des 8 familles ....:-) ("mais ça ira plus vite avec l'exécutable nBpremier")
Il n'y a pas de site qui donne des bases de données > 10 000 000 de nombres premiers ?

LEG · August 2020

A l'époque on avait commis la même erreur , lorsque $n = P*P$ il était considéré comme premier dans le programme, on avait donc modifié le programme : afin que le premier teste de $n$ , était de le diviser par $P\leqslant\sqrt\:n$ .

Sinon tu peux faire retranscrire l'algorithme du code python en C++ et directement avec les entiers naturels au lieu des 1...à la fin le programme te restitue les nombres premiers. C'est le même principe de criblage que l'exécutable nBpremier , mais en plus rapide .

Pour te donner une idée nbPremier mod 30, pour $N = 450 000 000 000$ met environ 2h50 par famille et ensuite le temps de les écrire et sauvegarder dans des fichiers de 500 000 nombres.

Ératothène mod 30 en C++ (le python en question que j'ai posté) met environ 1 minute pour tester le nombre de premier par famille pour la même limite $N$; il y aurait donc que deux ou trois lignes de programme à modifier , pour qu'il restitue directement les nombres premiers pour ta limite $N = 22801763550$ dont tu sa besoin...

[Utilisateur supprimé] · August 2020

Bonjour

La conjecture de Cramer me fait penser à un petit th que j'avais pondu il y a quelque temps ,sur la différence de 2 nombres premier.

$2.3.5.7.11....p_n-p_y=a$ a te premier sss $a <p_n^2$ avec $p_y$ premier avec la primorelle bien sur

a partir de cela ,je construis une soustraction

$2.3.5.7.11....p_n-p_{y_{1}}=a_1$
$2.3.5.7.11....p_n-p_{y_{2}}=a_2$

$a_1-a_2=p_{y_{2}}-p_{y_{1}}$ et donc l’écart entre deux nombres première ne peux pas être unique

à ma connaissance, c'est le seul théorème qui exist ,sur les écartes de 2 nombres premier.
Bon d'un autre coté, je ne prêtant pas connaître tous les théorèmes, donc... il peut exister sous une autre forme.

cordialement remy

LEG · August 2020

@aumeunier: Tu devrais déjà écrire correctement les idioties que tu racontes, sur tous les sujets ouverts relatifs au nombres premiers ! Car là ça devient lourd !
C'est le théorème que tu as pondu : la différence entre deux nombres premiers tel que $p_n - p_y = a$ est un nombre premier ...::o si $a<P^2_n$.
Ensuite tu construis des différences ou tu calcules les différences pour dire que $a$ n'est pas unique par le théorème miraculeux du meunier ("qui doit rêver car meunier tu dors")...
Quand tu te réveilleras n'oublie pas de regarder si $a$ est un nombre pair....et comme il n'est pas unique, selon le théorème que tu as pondu, alors tu as trouvé une sacré fournée de nombres pairs premiers !
On se croirait dans la revue de Tintin est Milou avec "" Dupon et Dupon font de l'arithmètique "" je dirait même plus : que $a$ n'est pas unique....

[Utilisateur supprimé] · August 2020

Ou tu vois une idiotie nous sommes en math donc tu devrais pouvoir être plus précis non

donc

$2 \cdot 3 \cdot 5 \cdot 7 \cdot 11\cdots p_n-p_y=a$ ,$a$ est premier sss $a<p_n^2$ avec$ p_y$ premier avec la primorielle bien sur

pour démontrer cette relation, il suffit juste de comprendre qu'un entier composé a toujours un facteur premier inférieur a sa racine ici dans

$2 \cdot 3 \cdot 5 \cdot 7 \cdot 11\cdots p_n-p_y=a$ comme $p_y$ et premier avec la primorielle $a$ ne peut avoir aucun des facteurs présents dans la relation simple non,

bon ensuite tu augmentes la valeur de $p_y$ pour avoir un valeur $< p_n^2$
À l’arrivée tu viens de fabriquer un nombre premier

Ensuite, tu prends 2 relations différentes, tout en conservant la même primorielle et tu fais une soustraction puis tu conclus

donc perso je démontre, peux tu affirmer quelque chose avec quelque élément mathématique stp ?

Cordialement remy

LEG · August 2020

Commence par définir ta "primorelle" (est ce une nouvelle variété de chanterelles") car pour moi $p_n$ est le dernier premier de ta suite; $p_1,p_2,p_3...p_n$ le nième premier..d'où pour $p_n = 11$ ta différence $p_n - p_y = a$ est un nombre pair; simple non ?
Tu démontres rien du tout !

[Utilisateur supprimé] · August 2020

ousp excuse moi primorielle bien sur

Par contre je suis toujours à la recherche d'un théorème qui évoque la différence des nombres premiers, à l'époque j'avais fait des recherches et je n'avais rien trouvé

Cordialement remy

Premiers consécutifs

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 6