Bonjour à tous,
Revoilà des premiers...
Vous avez remarqué que l'écart entre deux nombres premiers est souvent 2 ,mais presque autant 4 .
Une course est organisée pour connaitre le vainqueur de ces écarts.
Ainsi pour p <100 :
le classement donne 1 er 2 8
2 d 4 7
Quel l sera le classement pour p<1000 ,10 000 ,100 000,1 000 000.
Sur un plus grand nombre que constate-t-on?
salut
d'après ce que je comprends il faut savoir qui de l'écart de 2 ou de 4 l'emporte sur la liste de premiers considérés
un algo naïf :
def compte (n) :
d = q = 0
for p in prime (n - 2) :
if p + 2 isprime : d += 1
if p + 4 isprime : q += 1
return d, q
-pour une liste de nombres premiers compris entre 1 et100
l'écart de 2 apparait le plus grand nombre de fois --> ( 8 fois)
-pour une liste de nombres premiers compris entre 1 et10000
l'écart de 6 apparait le plus grand nombre de fois --> ( 299 fois)
-pour une liste de nombres premiers compris entre 1 et100000
l'écart de 6 apparait le plus grand nombre de fois --> ( 1940 fois)
-pour une liste de nombres premiers compris entre 1 et1000000
...mon pc en peut plus...:D
def compte (n) :
d = q = 0
for p in prime (n - 2) :
if p + 2 isprime : d += 1
if p + 4 isprime : q += 1
return d, q
if p + 2 isprime : d += 1
if p + 4 isprime : q += 1
Voici mon implémentation
Code (très sous-optimal):
je ne comprends pas ... vraiment quel est le pb ...
pour p premier si p + 2 et p + 4 sont tous deux premiers je compte +1 au nombre de +2 et au nombre de +4
et au tour suivant j'aurai donc p + 2 premier et donc encore un +2 puisque p + 4 est aussi premier
et je compte donc bien tous les cas où les paires (p, p + 2) et (p, p + 4) sont constituées de nombres premiers
si p, p + 2 et p + 4 sont premiers j'ai bien deux fois un +2 et une fois un +4
... mais je comprends aussi ce que tu veux dire : si on a un +4 on ne doit pas avoir un +2 (pas de premier entre p et p + 4)
En fait on est en train de répondre à deux questions différentes
Ton code répond à la question : "combien de paires (p,p+2) de premiers et combien de paires (p,p+4) de premiers y a-t-il au total ?"
Le mien à la question : combien de paires de premiers consécutifs ont un écart de 2 ? un écart de 4 ?
En l'occurrence, p, p+2 et p+4 ne peuvent pas être premiers tous les 3 , sauf pour le triplet (3,5,7).
Mais pour le triplet (11, 13, 17), on doit compter 13-11=2, 17-13=4, mais on ne s'intéresse pas à 17-11=6.
En d'autres mots, si on regarde les 10000 plus petits nombres premiers impairs, la somme de tous nos compteurs doit donner 9999.
Je reprends l'exemple des p<100
écart2 écart 4
3 5 7 11
5 7 13 17
11 13 19 23
17 19 37 41
29 31 43 47
41 43 67 71
59 61 79 83
71 73
2 gagne par 8 à 7
A vous pour les autres tranches depuis le début.
J'avais compris la question un peu autrement... Est-ce que l'écart le plus fréquent est 2, ou 4 , ou pourquoi pas 6, 8, 10 ...
Et du coup, j'ai adapté un peu le code de Ulmiere :
def erathostene(n):
primes = [2,3]
tmp = [True,True]+[not not (i%3)*(i%5) for i in range(7,n+1,2)]
# i represente 2*i+3 pour i entre 0 et n//2
i,k = 1,1
limi = len(tmp)
while True:
p = 6*k-1
i = 3*k-2
if tmp[i]:
primes.append(p)
j = i+p
while j < limi:
tmp[j] = False
j += p
p += 2
i += 1
if i < limi and tmp[i]:
primes.append(p)
j = i+p
while j < limi:
tmp[j] = False
j += p
i += 2
while True:
if i >=limi or tmp[i]:
break
i += 1
if i >=limi or tmp[i]:
break
i += 2
if i >=limi:
break
k = (i+2)//3
return primes
def course(primes, limit):
d,q, q2, q3 ,q4 = 0,0,0,0,0
if not len(primes):
return [(2,0),(4,0)]
prevp = primes[0]
if prevp > limit:
return [(2,0),(4,0)]
# boucle pour éviter de parcourir deux fois le tableau de premiers
for i in range(1,len(primes)):
p = primes[i]
if p> limit:
break
diff = p-prevp
d += diff == 2
q += diff == 4
q2 += diff == 6
q3 += diff == 8
q4 += diff == 10
prevp = p
return sorted([(2,d),(4,q),(6,q2),(8,q3),(10,q4)], reverse=True, key=lambda x:x[1])
def main(n):
primes = erathostene(n)
pow_n = len(str(n))-1
for i in range(pow_n+1):
print("10**%d :"%i, course(primes,10**i))
main(10**8)
je ne comprends pas la construction de votre liste de premiers ...
et en particulier ce double not not ...
ni la phrase : i représente 2i + 3 ...
J'ai fait confiance à Ulmiere, je n'avais même pas remarqué ce not not ! (et je continue de lui faire confiance)
Quand j'ai vu un endroit où il comptait les cas 'diff=2' ou 'diff=4', j'ai modifié cette section, sans toucher au reste.
Intuitivement,on sait que l'écart 2 domine dans le petits nombres
puis se calme nettement après 1000.
Ce qui est curieux c'est la course que se font 2 et 4 est sans fin
jusqu'à preuve du contraire ,ainsi
les bons résultats trouvés par Ulmiere et ty 59847 se poursuivent ainsi :
écart 2 4
10^2 8 7
10^3 40 35
10^4 205 204
10^5 1 224 1 215
10^6 8 169 8 143
10^7 58 980 58 621
10^8 440 312 440 258
10^9 3 424 506 3 424 679
10^10 27 412 679 27 409 998
10^11 224 376 048 224 373 161
10^12 1 870 585 220 1 870 585 458
Dans le chapitre des écarts :
On sait aussi que les écarts champions se succèdent ainsi 6
se distingue longtemps.
A ma connaissance l'écart champion actuel semble 30.
2x3=6
puis 2x3x5=30
puis certainement 2x3x5x7 , puis 2x3x5x7x11 ... ... mais à partir de quel seuil ?
J'ai fait exprès de tout écrire de manière impérative pour bien clarifier l'algo mais j'ai oublié cette partie
Commençons déjà par le commentaire. J'aurais peut-être dû écrire "i represente 2*j+3 pour j entre 0 et n//2".
A chaque fois que vous stockez un entier en Python, c'est 24 octets de mémoire que vous consommez d'office et la consommation augmente avec la taille des entiers, qui peut être arbitrairement grande. Comme les premiers ne peuvent être qu'impairs (sauf 2), il est inutile de prendre de la place pour les entiers pairs !
Si je veux représenter les entiers impairs de [0,10], je peux écrire u = [1,3,5,7,9] et dans ma boucle les récupérer : mon_entier = u[i]
Mais c'est un peu mieux de faire u = [0,1,2,3,4,5] puis mon_entier = 1 + 2*u[i].
En fait, là où ça devient le plus intéressant, c'est quand je remplace la liste [0,1,2,3,4,5] par l'itérateur range(6), qui lui ne consomme presque aucune mémoire, mais ici je simplifie
Il y a aussi autre chose, c'est que dans le cas de [0,1,2,3,4,5] les indices sont successifs. L'opération qui incrémente un bigint est bien plus rapide que la somme arbitraire puisqu'il n'y a pas de calcul de retenue à faire. Parce que x+1 = -(-x-1) = -(~x) où ~ est la négation binaire, c'est-à-dire que la réprésentation de binaire de ~x est la même que celle de x, mais en inversant les 1 et les 0. Ensuite la négation arithmétique est très rapide aussi (soit gérée dans une variable à part, soit en tant que bit de poids fort de l'entier, mais dans le deux cas, c'est très rapide).
Pour le not not maintenant. J'aurais pu écrire i%3 > 0 and i%5 > 0 à la place. C'est logiquement équivalent à (i%3)*(i%5) > 0 puisque Z est intègre, mais la différence c'est que la première forme n'évalue pas i%5 si i%3 == 0 et renvoie directement False (short-circuit evaluation en anglais) et donc est plus efficace. J'ai écrit la deuxième parce que j'avais d'autres idées plus efficaces en tête et qui s'appuyaient sur le calcul du produit des modulos mais j'ai finalement décidé de faire des choses plus simples et j'ai oublié de faire cette petite optimisation.
Le double not sert à convertir une valeur en booléen. not not 34 est interprété comme not ( not 34 ).
34 est un entier non nul donc il vaudrait True et not 34 renvoie False, puis not not 34 renvoie not False, c'est à dire True. J'aurais pu faire bool(34) aussi, mais je crois (pas sûr) que ça ne fonctionnerait pas pour les gens qui sont encore sur Python 2
merci Ulmiere ... j'avais compris quelques bricoles mais la construction de tes premiers me reste tout de même obscure ...
sans vouloir prendre de ton temps ce que je comprends :
primes est la liste de premiers (que tu construis au fur et à mesure)
tmp est (au départ) la liste des V correspondant aux entiers impairs non multiples de 3 et 5 (et on peut donc avoir un V pour un impair éventuellement non premier
et c'est ce que tu contrôles ensuite ... mais ça me reste pas clair
il est évident que p est de la forme 6k 1
mais par exemple pourquoi n'est-ce pas :
Voici le même code (au not not près), commenté
J'espère que c'est compréhensible
def erathostene(n):
primes = [2,3]
tmp = [True,True]+[i%3!=0 and i%5!=0 for i in range(7,n+1,2)]
# i represente 2*j+3 pour j entre 0 et n//2 (1)
# tmp est le clible lui-même. On l'initialise à
# [crible(3), crible(5)] + [crible(7),..., crible(n)]
# avec un pas de deux à chaque fois
# à ce stade on a éliminé les multiples de 2, 3, et 5
# le prochain dont il faut éliminer les multiples est 7
# tous les premiers s'écrivent 6k-1, 6k+1 ou 6k+3
i,k = 1,1
# l'initialisation en i ne sert à rien, j'ai oublié de l'enlever
# par contre celle en k permet de commencer à p = 5
# c'est pour ça que j'ai initialisé p à [2,3] et pas à [2] ou [2,3,5]
# j'initialise à 5 et pas à 7 parce que j'ai décidé de travailler avec des 6k-1,6k+1,6k+3
# et non avec des 6k+1,6k+3,6k+5
limi = len(tmp)
# limi pourrait être directement initialisé à sa valeur en fonction de n et tmp alloué avec une taille de limi
# puis remplit. Mais on fait les choses à l'envers ici et puisqu'on a déjà un tableau, on lit sa longueur
while True:
p = 6*k-1
i = 3*k-2 # combien vaut le 2*i+3 évoqué en (1) ? 6k-4+3 = 6k-1 = p
if tmp[i]: # si l'entier p = 2*i+3 est premier, on élimine tous ses multiples <= n
primes.append(p)
j = i+p
while j < limi:
tmp[j] = False
j += p
p += 2 # p = 6k+1
i += 1 # i = 3k-1 et 2*i+3 = 6k-2 + 3 = 6k+1 = p
if i < limi and tmp[i]: # on s'assure que p <= n et si p est premier on élimine ses multiples
primes.append(p)
j = i+p
while j < limi:
tmp[j] = False
j += p
# maintenant, on cherche le prochain premier, pour pouvoir éliminer ses multiples
i += 2 # i = 3k+1 et 2*i+3 = 6k+2+3 = 6k+5 correspond à 6(k+1)-1
# c'est à dire à recommencer l'opération avec k <- k+1
# mais peut-être que 6k+5 n'est pas premier, c'est à ça que sert à la boucle suivante
# on pourrait aussi la lancer avant de faire p = 6k-1 et i = 3k-2
# et d'ailleurs, ça montre au passage que le premier if tmp[i] est toujorus satisfait
# je l'ai laissé pour pouvoir commencer à un indice k autre que 1
while True:
if i >=limi or tmp[i]:
break
i += 1
if i >=limi or tmp[i]:
break
i += 2
if i >=limi:
break
# une fois qu'on a trouvé un i tel que p = 2i+3 <= n premier, on affecte à k la bonne valeur pour que i = 3k-2 au prochain tour de boucle
# il faut quand même remarquer que
# si i = 3K-2, ((3K-2)+2)/3 = 3K/3 = K
# si i = 3K-1, ((3K-1)+2)/3 = (3K+1)/3 = K aussi puisque 1 < 1.5
# et bien-sûr, si i = 3K+1, ((3K+1)+2)/3 = (3K+3)/3 = K+1
# tout baigne
k = (i+2)//3
return primes
Bravo aux programmeurs...
Plus scolairement,ce qui m'interpelle ce sont les écarts 2 et 4 qui
comme vous pouvez le constater ont des scores voisins dans les
décomptes actuels.
A mon avis au delà compte tenu de la rareté grandissante des premiers 4 devrait logiquement lâcher 2 mais de là à le prouver
Non,
2 et 4 devraient continuer à rester à quasi-égalité ad vitam aeternam.
Regardons les nombres qui ne sont multiples ni de 2, ni 3, ni 5, ni 7 , ni 11.
On a donc un cycle de longueur 2*3*5*7*11=2310.
Dans ce cycle, on a 135 intervalles de longueur 2, et 135 de longueur 4. ( je compte l'intervalle entre 2309 et 2311).
Exactement le même nombre. Et je pense que ça n'est pas une coïncidence.
Et je pense que si on continue (cycle de longueur2310*13, et les nombres qui n'ont aucun diviseur inférieur ou égal à 13), on aura toujours cette égalité.
Ca doit pouvoir se démontrer.
Pour 2310, je regarde les nombres qui n'ont pas de diviseur inférieur ou égal à 11. Ces nombres ne sont pas tous premiers, loin de là.
Mais les nombres composés viennent 'piocher' de façon parfaitement régulière dans cet échantillon. Je dis bien régulière, et pas aléatoire.
C'est le crible d'Eratostène, qui est régulier par construction.
L'autre truc, tu dis que 4 devrait à un moment dominer 2.
Non.
En regardant les nombres jusqu'à un certain seuil (2310), et en regardant les nombres n'ayant aucun diviseur inférieur ou égal à 11, j'ai un parfait équilibre.
Puis je supprime les multiples de 13.
Je vais avoir des couples avec un écart 2 qui sautent, d'autres avec un écart 4 qui sautent, mais j'ai une certitude, c'est que les couples avec un écart 2 qui sautent ne deviennent pas des couples avec un écart 4. JAMAIS.
Par contre , les configurations (p, p+2, p+6) ou (p, p+4,p+6) qui deviennent (p,p+6), c'est possible.
On admet donc que 2 et 4 restent inséparables mais avec une nette tendance à la baisse par rapport aux autres champions: 6 ; 30 ; ??
Bonjour,
On n'a encore aucune démonstration de la conjecture des nombres premiers jumeaux : aucune démonstration qu'il existe une infinité de nombres premiers tels que soit aussi premier.
Alors, espérer démontrer quelque chose sur la prédominance de l'écart 2 par rapport à l'écart 4 ou vice-versa ...
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :