Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#251 09-06-2018 15:31:21

LEG
Membre
Inscription : 19-09-2012
Messages : 269

Re : crible en python

yoshi a écrit :

Re,

La difficulté, elle est là ;

 if j%3!=0 and j%5!=0:
    fam =Dico[j%30]
    if Pf[fam] == 0:
        Pf[fam] = j

Parce qu'il n'y a pas un simple stockage des nombres j, ils sont rangés par famille, et un nombre n'est stocké dans une famille que s'il n'y figure pas déjà.

@+

C'est bien pour cela qu'il faut ranger l'index au fur et à mesure dans P8 liste nombres, et cribler pour ensuite reprendre le j suivant..etc une fois P8 criblé on passe à Pi suivant.

j%30 et Dico[j%30]
Si on garde les deux, on peut les obtenir d'un coup :
q,reste=divmod(j,30) :
Ce qui veut dire que le reste va indiquer la famille où on va placer l'index... afin de cribler

Ce qui implique qu'il faut que  fam =Dico[j%30] ou différemment donne le quotient = index avec le reste qui correspond à la famille de P8 ou Dico= {1:0,........29:7}

j'avais essayé si on suprime Pfam et Dico={1:0.....29:7} il ne reste que P8, qui devient l'un des 8 nombres {1,7,11,13,17,19,23,29}

cela ne change rien aux j

tu appelles les j au fur et à mesure, avec leur Pi, tu n'as que l'index à calculer
on veux que la famille p8=7

on écarte j = D_c{1,3,5,9}
p8=q,j%30 = on à l'index = quotient, et le reste correspondant à la famille p8 .

si j%30 != 7 on continue au j suivant se terminant par 7; il n'y a que 3 cas possibles: multiple de 3 se terminant par 7, fam p8=17[30 et celle que l'on crible p8 = 7

au niveau du stockage soit on a tous les j par rapport à n =30k puis on traite, ce qui se passe actuellement...

Ou alors, on peut même les faire au fur et à mesure de Pi et R appelé.. des que le j de P8=7 est traité avec son Pi,

on passe à Pi et R suivant , calcule des J , on traite ...etc
en tout et pour tout, pour chaque Pi et R on a au maximum 3 division...et des que le j%30 = 7 est trouvé, criblage et on passe à Pi suivant, ce qui raccourci encore les étapes...

On en revient à ce que tu as supposé ce matin...

Dernière modification par LEG (13-06-2018 16:43:03)

Hors ligne

#252 10-06-2018 08:58:52

LEG
Membre
Inscription : 19-09-2012
Messages : 269

Re : crible en python

Bonjour@Yoshi
hier j'ai oublié de te répondre à cette question:

un même nombre (je l'ai déjà vu) peut figurer dans deux familles ou plus...
Est-ce que cela signifie que le programme le traite ensuite plusieurs fois ? C'est à dire que, le rencontrant plusieurs fois, il intervient plusieurs fois dans la listes nombres pour écrire 0 dans un emplacement, alors même que c'est déjà fait ?

Bien sûr..C'est identique à Eratosthène modulo30...
les nombres premiers Pi repasserons plusieurs fois sur un même nombre n < n=30k, qui dans 2n se factorise par 2,3,4 ou plusieurs facteurs Pi, ils marqueront [0] alors que ce [0] est déjà marqué ...

Prend un simple exemple:
pour n = 30k = 4770; 2n = 9540

prends j = 41 il serra marqué [0] à l'index 1, par 7, 23 et 59; car 9499 se décompose en facteurs premiers {7,23,59} et: 7, 23, 59 vont commencer à cribler à partir de cet index = 1

Ensuite : prend maintenant 2n + 30 = 9570

et bien tu vas trouver 41+30 = 71 trois fois, car 9499 est toujours divisible par 7,23,59 donc 71 est congru à 9570 modulo 7,23,59 

7%9570 = 1 = j et j+5*14 = 71
23%9570 = 2 , +23 = 25 =  j, et + 46 = 71
59%9570 = 12 et + 59 = j = 71

Ce qui implique que : 7 , 23 et 59 vont marquer [0] dans la famille p8 = 11, mais: à l'index 2...soit : (71-11) / 30 = 2.

A partir de cet index = 2 , les trois Pi vont cribler la fam = 11, supposons que tu écartes les doublons, il n'y aura que le premier Pi = 7 qui va cribler , les deux autres :23 et 59 seront écartés d'où, le crible est faux et cela se traduit par une augmentation de [1] donc plus de nombres premiers de n à 2n...

C'est pour cela que je te disais, ce crible n'est que la réplique d'Eratosthène , mais dans les congruences et d'où ce n'est qu'un corollaire du TNP, du TFA et du théorème de Chebotarev sur la densité de premiers dans des suites arithmétique de raison 30...

[ Pour la petite histoire: C'est élémentaire mais pas étudié ...Dommage... Au moins grâce à ton programme on peut étudier plus loin ...la répartition des nombres premiers de n à 2n...Car cet outil arithmétique permet de prouver de façon incontestable ces trois corollaires...!]

Dernière modification par LEG (13-06-2018 16:35:24)

Hors ligne

#253 14-06-2018 08:01:39

LEG
Membre
Inscription : 19-09-2012
Messages : 269

Re : crible en python

Bonjour @Yoshi
Tu disais, que la difficulté post#254 ci-dessus était:

python a écrit :

if j%3!=0 and j%5!=0:
    fam =Dico[j%30]
    if Pf[fam] == 0:
        Pf[fam] = j

je pense que l'on peut la résoudre assez facilement.

étant donné que jusqu'à ce bloc s2,3. on peut traiter par famille..en modifiant dans initialisation

 for i in range(1):

   et en dessous Pfam=j; 

for j in range(1):

    #au lieu de (8)

Ainsi que dans dans

Dico={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}

.
il suffit de choisir la première famille que l'on veut cribler par exemple la famille p8=7 , je modifie:

Dico={7:0,1:1,11:2,13:3,17:4,19:5,23:6,29:7}

je passe la famille 7 en position 0, et 1 en position 1...

il suffit de modifier la partie s2 comme ceci on ne vérifie que si j%30==7, sinon au passe à j suivant:

if j%30==7:
                        if Pf[fam] == 0:
                           Pf[fam] = j

ce qui devrait donner:


for j in range(debut,fin,pas):
            Pf=Pfam[i]
            if j%30==7:
               fam =Dico[j%30]
               if Pf[fam] == 0:
                    Pf[fam] = j

        for j in range(1):
            debut_index=Pf[j]//10//3  
            Nombres_j=nombres[j]
            for index in range(debut_index, nbcell,pi):
                Nombres_j[index] = 0
 

Est ce qu'il faut supprimer des lignes en amont , qui ne sont plus utiles, afin de traiter que les j <= f au fur et à mesure ,et pour chaque Pi ....? ou est ce que l'on peut laisser comme tel ....?

ce qui éviterait d'utiliser Pfam, et même Dico={1:0,.....29:7}
On ne stockerait, que pour chaque Pi que sa  la liste de j <= f ; au fur et à mesure que cahque Pi crible la famille p8 = 7 ou autre ....

Non...?

{"par contre je ne sais pas comment il faut réécrire les lignes ou en supprimer.... ..."}

voila ce que j'ai essayé et modifié  :


 for j in range(debut,fin,pas):
            Pf=Pfam[i]
            if j%30==7:

               for j in range(1):
                   debut_index=j//10//3
                   Nombres_j=nombres[j]
                   for index in range(debut_index, nbcell,pi):
                       Nombres_j[index] = 0
 

Mais comme tu peux le voir,  cela crée une erreur et sans gain de temps...alors qu'il y a moins de division en principe:

G9Y le bon code
Donnez la valeur de n = 30k : 3 000 000 000
Phase d'initialisation: 0.32760071754455566 seconds ---
Famille de chaque Pi: : 0.390000581741333 secondes ---
Criblage des 8 familles: 12.480021953582764 seconds ---
Extraction des premiers n à 2*n : 0.7644011974334717 seconds ---

**  16887073 nombres trouvés en 13.962024450302124 secondes **
Appuyez sur une touche pour continuer...

G1Y code modifié:
Donnez la valeur de n = 30k : 3000000000
Phase d'initialisation: 0.3120005130767822 seconds ---
Famille de chaque Pi: : 12.870022773742676 secondes ---
Extraction des premiers n à 2*n : 0.8268013000488281 seconds ---

**  23137528 nombres trouvés en 14.008824586868286 secondes **
Appuyez sur une touche pour continuer...

***************************************************************************
Par contre en modifiant uniquement la ligne :

if j%3!=0 and j%5!=0:

par :

if j%30==7

ce qui permet de ne prendre que les j de la famille p8 = 7 et de sauter les autres..
Bien entendu en modifiant Dico={7:0.......etc 29:7} on met donc la famille p8 = 7 à l'indice 0 dans Dico.

On à le bon résultat dans les deux cribles G1 et G9, mais on ne gagne rien en temps..

Dernière modification par LEG (14-06-2018 10:00:05)

Hors ligne

#254 14-06-2018 08:26:18

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 930

Re : crible en python

Re,

Je vais revenir aux manettes.
Plus que le routage à faire...

Je réfléchis par petits bouts depuis un moment : je pense pouvoir mener à bien le boulot.
Jusqu'à présent le seul intérêt du stockage des nombres dans Pfam était d'éviter les doublons dans chaque famille. Ainsi, ton programme, une fois ce travail effectué, reprenait ces nombres famille par famille et les traitait ensuite.

J'ai un point d'interrogation : je me demande si en supprimant ce stockage, et pour de très grands nombres n, on ne va pas perdre un temps fou à refaire x fois supplémentaires le même travail de remplacement de 1 par des zéros.

Cela dit, je vais tâcher d'examiner soigneusement ce que tu proposes ci-dessus...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#255 14-06-2018 09:53:41

LEG
Membre
Inscription : 19-09-2012
Messages : 269

Re : crible en python

yoshi a écrit :

Re,

J'ai un point d'interrogation : je me demande si en supprimant ce stockage, et pour de très grands nombres n, on ne va pas perdre un temps fou à refaire x fois supplémentaires le même travail de remplacement de 1 par des zéros.

Cela dit, je vais tâcher d'examiner soigneusement ce que tu proposes ci-dessus...

@+

a_): les doublons le programme ne les évite pas car comme je te l'ai expliqué ci-dessus hier matin avec l'exemple de n= 4770
le programme repasse bien plusieurs fois sur un même 0 dans une famille ou d'autre en fonction de l'index de j relatif à son Pi qui crible

b_): Pour moi si on diminue le stockage qui prends du temps et de la mémoire; car il faut quand même rappeler les Pfam stockées pour les traiter, on gagne en limite que l'on peut cribler...

c_): actuellement le programme stock : pour une limite n fixée par exemple 3 000 000 .
tous les j <= f
(" relatif à leur Pi qui va cribler la liste Nombres_j , c'est à dire remplacer les [1] en [0] , les congrus à 2n%Pi ")

puis il classe les j dans Pfam par rapport à l'ordre de Dico={1:0,......etc..29:7}

Ensuite il rappelle les Pfam relatif à chaque Pi pour les traiter , c'est à dire calculer l'index i , le positionner dans P8 la liste Nombre_j [index] = 0,
afin que Pi crible de i à n/30 , ie; remplacer les [1] par [0] par pas de Pi...

d'où pourquoi on perdrait un temps fou....?

d_):
si on traite qu'une famille, par exemple Dico={7:0} on sait qu'il faut vérifier :

if j%30 == 7

et de calculer son index:

 for j in range(1):
            debut_index=j//10//3  
            Nombres_j=nombres[j]
            for index in range(debut_index, nbcell,pi):
                Nombres_j[index] = 0

On devrait diviser le temps de 13 secondes environ, par 5 , pour n = 3 000 000 000....

Dernière modification par LEG (14-06-2018 10:35:58)

Hors ligne

#256 15-06-2018 11:00:11

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 930

Re : crible en python

Re,

Je suis un têtu et je poursuis mon idée :


from time import time
from os import system
from collections import OrderedDict

## V. 6.0 ##

def eratostene(n):
    n = int((2*n)**0.5)
    m = (n-1) // 2
    limite=1+n
    b = [True]*m
    premiers = [2]
    for i,p in enumerate(range(3,limite,2)):
        if b[i]:
            premiers.append(p)
            j = 2*i*i + 6*i + 3
            debut,pas=j,2*i+3
            for j in range(debut,m,pas):
                b[j] = False
    debut=i
    for i in range(debut,m):
        if b[i]:
            premiers.append(p)
        p += 2
    return premiers[3:]

def Crible_mod30(n):
    # INITIALISATION
    start_i= time()
    Primes_init = eratostene(n)
    nn,nbcell,nbcl=n*2,n//30,n//30-1
    nombres=[]
    for i in range(8):
        nombres.append([1]*nbcell)
    Pfam,P8=[],[1, 7, 11, 13, 17, 19, 23, 29]
    Dico=OrderedDict={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}
    s_1=time()-start_i
    #print("Phase d'initialisation: %s seconds ---" % s_1)

    # FAMILLES POUR CHAQUE Pi
    start_time = time()
    for i,pi in enumerate(Primes_init):      
        r=nn%pi
        debut,fin,pas=r+pi*(1-r%2),1+r+pi*29,pi*2
        Fam,cpt=[0,0,0,0,0,0,0,0],-1
        for j in range(debut,fin,pas):    
            if j%3!=0 and j%5!=0:
                fam =Dico[j%30]
                if Fam[fam] == 0:
                    Fam[fam] = j
                    cpt+=1
                    debut_index=Fam[cpt]//10//3
                    Nombres_cpt=nombres[cpt]
                    for index in range(debut_index, nbcell,pi):
                        Nombres_cpt[index] = 0
    s_23=time()-start_time

    # CALCUL DES NOMRES PREMIERS ENTRE n ET 2*n
    start_time = time()
    total = 0
    for sous_liste in nombres:
        total+=sum(sous_liste)      
    s_4=time() - start_time
    s=s_1+s_23+s_4
    print("Extraction des premiers n à 2*n : %s seconds ---" % s_4)
    return total,s

n=240
nbr,s= Crible_mod30(n)
print ("\n** ",nbr,"nombres trouvés en %s secondes" % s ,"**")
system("pause")

Il me reste un "détail" à régler :
j'obtiens seulement 38 nbs premiers au lieu de 40..
Je n'ai pas encore trouvé pourquoi...

Je ne stocke plus l'intégralité de Pfam, seulement Pfam[i'] que j'ai appelé Fam...
J'ai contrôlé un par un tous les Fam obtenus : ils sont bons...
Comme dans la dernière version propre, dans le Criblage des familles on redémarrait avec for j in range(8) et comme, là, j est encore un des nombres stockés dans Fam j'ai introduis un compteur cpt que j'initialise à -1...
J'ai vérifié pour chaque Fam le cpt associé : il est bien à 7...
Je pense que l'erreur est sur cette ligne :
for index in range(debut_index, nbcell,pi):

Lorsque ça fonctionnera, je pense que le gain de temps sera sensible.
Pour n=240, la dernière version fonctionnelle me donnait chez moi : 0.0009999275207519531 s
Avec la version en cours : c'est 0.0 s.

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#257 15-06-2018 13:18:43

LEG
Membre
Inscription : 19-09-2012
Messages : 269

Re : crible en python

Bonkour @Yoshi

for index in range(debut_index, nbcell,pi): je ne vois pas pourquoi l'erreur viendrait de cette ligne , car il n'y a vraiment aucune raison....

Par contre cette ligne : debut_index=Fam[cpt]//10//3 est toujours génératrice d'erreur , mais surtout je ne comprend pas pourquoi  tu calcules le début index avec Fam[cpt]....??  est ce que Fam[cpt] représente les j....?

la marge d'erreur à l'ai exponentielle .. Et il n'est pas sûr que l'on ai un gain de temps...regardes le résultat :


cette version avec n= 300 000 000Extraction des premiers n à 2*n : 0.639601469039917 seconds ---

**  16825025 nombres trouvés en 9.952817678451538 secondes **
Appuyez sur une touche pour continuer...

avec G9Y
Donnez la valeur de n = 30k : 300000000
Phase d'initialisation: 0.28080058097839355 seconds ---
Famille de chaque Pi: : 0.28080058097839355 secondes ---
Criblage des 8 familles: 9.07921576499939 seconds ---
Extraction des premiers n à 2*n : 0.6240010261535645 seconds ---

**  15072378 nombres trouvés en 10.264817953109741 secondes **
Appuyez sur une touche pour continuer...

debut_index=Fam[cpt]//10//3 je viens d'essayer avec:  debut_index=Fam[fam]//10//3  et avec debut_index=j//10//3

toujours une erreur, moins importante ...

Extraction des premiers n à 2*n : 0.6708011627197266 seconds ---

**  16654488 nombres trouvés en 10.311618089675903 secondes **
Appuyez sur une touche pour continuer...


Ce qui apparait donc au niveau du crible, c'est une augmentation du nombre de nombres premiers , par exemple pour n = 3 000 000 000
gain de temps 1,5 seconde;  mais une erreur de 16 000 000  de premiers en plus...

Ce qui veut dire que le paramétrage est erroné d'où certain j sont mal indexés et ou mal positionnés , ou encore que des doublons ont été supprimés;

de ce fait les Pi ne font pas leur travail et ne marquent pas des [0] donc plus de [1]....!

voila le paramétrage et criblage correcte, ie; si il y a la bonne position des index  au départ de chaque Pi.

On a 87  Premiers P [600 ; 1200] ; pour n = 600

f1  : [0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0]<...>[0,0,0,1109,0,1049,1019,0,0,929,0,0,839,809,0,0,719,0,659,0]
f7  : [1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0]<..>[1193,1163,0,1103,0,0,1013,983,953,0,0,863,0,0,773,743,0,683,653,0]
f11: [0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1]
f13: [1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1]
f17: [0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1]
f19: [1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
f23: [0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1]
f29: [1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1]

ce qui n'est pas du tout le cas avec la nouvelle version
en mettant la fonction print(nombres)

 s=s_1+s_23+s_4
    print("Extraction des premiers n à 2*n : %s seconds ---" % s_4)
    print(nombres)
    return total,s
 

Dernière modification par LEG (15-06-2018 16:05:23)

Hors ligne

#258 15-06-2018 19:26:22

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 930

Re : crible en python

Salut,

Je viens de voir ta réponse :
j'avais entre temps repris des tests...
Pour n=240,
J'ai affiché les Fam du prog expérimental  correspondant aux Pfam[i'] de la dernière version fonctionnelle, puis pour chaque Fam les debut_index correspondants de l'un et de l'autre : identiques...
L'erreur est après : je vais bien la dénicher...
Ça me navre d'autant plus qu'avant l'essai, j'étais sûr que c'était bon.

Alors explication de texte de ce qui m'a conduit au au programme expérimental...
Donc, je suis arrivé à la conclusion que si je ne voulais pas faire des tests inutiles, j'étais obligé de garder les différentes Pfam[i']  mais une seule, pour chaque i différent, à cause de

if j%3!=0 and j%5!=0:
    fam =Dico[j%30]      
        if Pf[fam] == 0: # <---
            Pf[fam] = j    # <---

Et ayant vérifié qu'on traitait bien une Pf après l'autre, et en lecture dans le même ordre qu'à la construction, j'ai décidé de laisser tomber la liste de listes Pfam, pour n'en garder qu'une, Fam,  que je remplis, puis vide à chaque tour...

Mais, dans le prog qui est juste,
les j sont d'abord les nombres qui sont stockés dans les Pfam[i'] (dans le bloc s2)
Donc dans le bloc s3 il y avait :

        for j in range(8):
            debut_index=Pf[j]//10//3

puis à l'étape suivante de lecture des Pfam ('dans le bloc s3),
les j sont juste un index de 0 à 7 qui donne la position du nombre que l'on extrait alors d'un Pfam[i'].

Comme j'ai fusionné les blocs s2 et s3, j ne pouvait plus être l'un et l'autre. J'ai donc conservé j comme nombre, et j'ai dû recréer un index (cpt) qui vaudra de 0 à 7 et qui par Fam[cpt]  remplacera le Pf[j] du bloc s3...
J'ai vérifié : l'erreur ne vient pas de là...
Ceci :

    for i,pi in enumerate(Primes_init):      
        r=nn%pi
        debut,fin,pas=r+pi*(1-r%2),1+r+pi*29,pi*2
        Fam,cpt=[0,0,0,0,0,0,0,0],-1
        for j in range(debut,fin,pas):    
            if j%3!=0 and j%5!=0:
                fam =Dico[j%30]

est quasiment repris du bloc s2

Fam,cpt=[0,0,0,0,0,0,0,0],-1 : sur cette ligne : Fam c'est l'ancien Pf (=Pfam[i']) et je ne stocke plus l'intégralité de Pfam. Gain de place mémoire.
Et cpt, initialisé à -1, est incrémenté de de 1 à chaque j valable stocké va de 0 à 7.
Quand suite à ces lignes tu vois cpt, c'est le j du bloc s3...

                    debut_index=Fam[cpt]//10//3
                    Nombres_cpt=nombres[cpt]

avant, c'était :

            debut_index=Pf[j]//10//3
            Nombres_j=nombres[j]

Et la suite du bloc s3 est alors reprise en remplaçant j par cpt...

Tu comprends pourquoi ce matin, je croyais dur comme fer que ça fonctionnerait...
Ça aurait dû  ! En théorie...
Il y a sûrement un petit détail qui m'échappe : la nuit porte conseil !

J'ai été clair ?

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#259 15-06-2018 20:19:36

LEG
Membre
Inscription : 19-09-2012
Messages : 269

Re : crible en python

Re Yoshi: "j'étais en train de te donner la réponse"
effectivement tu avais raison et j'ai bien compris tes explications car j'étais en train de faire différents tests pour vérifier qu'il n'y avait pas d'erreur dans les Fam..

Voila l'erreur: comme tu le supposer, tous les Fam sont juste et les j aussi.

donc j'ai regardé avec l'indentation de G9Y

il y avait quelque chose qui me chiffonnait  le fait d'avoir mis cpt et non j

il faut "réindenter" cette partie..avec:

for cpt in range(8):

Car c'est cette fonction qui permet de cribler correctement.


for j in range(debut,fin,pas):    
            if j%3!=0 and j%5!=0:
                fam =Dico[j%30]
                if Fam[fam] == 0:
                    Fam[fam] = j
                    cpt+=1
for cpt in range(8):
            debut_index=Fam[cpt]//10//3
            Nombres_cpt=nombres[cpt]
            for index in range(debut_index, nbcell,pi):
                Nombres_cpt[index] = 0
 

résultat:
Extraction des premiers n à 2*n : 0.6240010261535645 seconds ---

**  15072378 nombres trouvés en 10.015217542648315 secondes **
Appuyez sur une touche pour continuer...

résultat avec G9Y:
Donnez la valeur de n = 30k : 300000000
Phase d'initialisation: 0.2652003765106201 seconds ---
Famille de chaque Pi: : 0.28080058097839355 secondes ---
Criblage des 8 familles: 9.172816038131714 seconds ---
Extraction des premiers n à 2*n : 0.6552011966705322 seconds ---

**  15072378 nombres trouvés en 10.37401819229126 secondes **

pou n=3 000 000 000
Donnez la valeur de n = 30k : 3000000000
Extraction des premiers n à 2*n : 6.208811044692993 seconds ---

**  135095831 nombres trouvés en 120.27621126174927 secondes **
Appuyez sur une touche pour continuer...


je met le programme de ta version, qui fonctionne parfaitement:


from time import time
from os import system
from collections import OrderedDict

## V. 6.0.1 ##

def eratostene(n):
    n = int((2*n)**0.5)
    m = (n-1) // 2
    limite=1+n
    b = [True]*m
    premiers = [2]
    for i,p in enumerate(range(3,limite,2)):
        if b[i]:
            premiers.append(p)
            j = 2*i*i + 6*i + 3
            debut,pas=j,2*i+3
            for j in range(debut,m,pas):
                b[j] = False
    debut=i
    for i in range(debut,m):
        if b[i]:
            premiers.append(p)
        p += 2
    return premiers[3:]

def CribleG2Y_mod30(n):
    # INITIALISATION
    start_i= time()
    Primes_init = eratostene(n)
    nn,nbcell,nbcl=n*2,n//30,n//30-1
    nombres=[]
    for i in range(8):
        nombres.append([1]*nbcell)
    Pfam,P8=[],[1, 7, 11, 13, 17, 19, 23, 29]
    Dico=OrderedDict={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}
    s_1=time()-start_i
    #print("Phase d'initialisation: %s seconds ---" % s_1)

    # FAMILLES POUR CHAQUE Pi
    start_time = time()
    for i,pi in enumerate(Primes_init):
        r=nn%pi
        debut,fin,pas=r+pi*(1-r%2),1+r+pi*29,pi*2
        Fam,cpt=[0,0,0,0,0,0,0,0],-1
        for j in range(debut,fin,pas):
            if j%3!=0 and j%5!=0:
                fam =Dico[j%30]
                if Fam[fam] == 0:
                    Fam[fam] = j
                    cpt+=1
        for cpt in range(8):
            debut_index=Fam[cpt]//10//3
            Nombres_cpt=nombres[cpt]
            for index in range(debut_index, nbcell,pi):
                Nombres_cpt[index] = 0
    s_23=time()-start_time

    # CALCUL DES NOMRES PREMIERS ENTRE n ET 2*n
    start_time = time()
    total = 0
    for sous_liste in nombres:
        total+=sum(sous_liste)
    s_4=time() - start_time
    s=s_1+s_23+s_4
    print("Extraction des premiers n à 2*n : %s seconds ---" % s_4)
    return total,s

n = int(input("Donnez la valeur de n = 30k : "))
nbr,s= CribleG2Y_mod30(n)
print ("\n** ",nbr,"nombres trouvés en %s secondes" % s ,"**")
system("pause")
 

je vais faire quelque test par famille.

@+++  Merci infiniment pour ton travail et ta pugnacité......

Dernière modification par LEG (16-06-2018 06:35:52)

Hors ligne

#260 16-06-2018 06:27:16

LEG
Membre
Inscription : 19-09-2012
Messages : 269

Re : crible en python

Bonjour @Yoshi

En résumé :

Pour n = 600 ; le dernier Pi = 31 et son reste R = 22 .
soit : R + Pi = j = 53

calcul des {15 j} ≤ f ,  f =31*29 = 899
{53, 115,177,239,301,363,425,487,549,611,673,735,797,859,921}

Traitement des j dans Fam,cpt[0,0,0,0,0,0,0,0,],-1
Fam =[301,487, 611, 673, 797, 859, 53, 239] pour le  dernier Pi = 31 et son R =22
Par  le boc s2:

fam =Dico[j%30]
                if Fam[fam] == 0:
                    Fam[fam] = j
                    cpt+=1
 

Ce qui veut dire que le programme garde en stock et en mémoire virtuelle tous les J et les Fam,cpt[0,...,0],-1;
pour les traiter par le dernier bloc s3


Criblage de P8, des 8 fam jusqu’à n /30 ; par le bloc s3 avec la fonction :

 for cpt in range(1):

Si cette fonction est enlevée, le criblage ne se fait pas de façon correcte.
Ce qui s’est traduit par une erreur du nombre de premiers # V .6.0. #


for cpt in range(1):
            debut_index=Fam[cpt]//10//3
            Nombres_cpt=nombres[cpt]
            for index in range(debut_index, nbcell,pi):
                Nombres_cpt[index] = 0
 

L’idéal, serait de traiter au fur et à mesure la liste des {15 j} ≤ f , au fur et à mesure avec une seule fonction :
q,reste=divmod(j,30) : ou avec,  fam ,Dico[j%30]= divmod(j,30)
en passant peut être directement au bloc s3, si on peut récupérer l’index lors de la phase :  fam =Dico[j%30].


for cpt in range(1):
            debut_index= “fam, Dico[j%30]= divmod(j,30) “    # ce qui ne s’écrit surement pas comme cela…
            Nombres_cpt=nombres[cpt]
            for index in range(debut_index, nbcell,pi):
                Nombres_cpt[index] = 0
 

Pour info voila ce que donne cette version, équivalente à l'avant dernière G1Y: pour la famille Dico = {7:0}

V=== RESTART: E:\Documents\conjecture de Goldbach\cribleG2Y_par Famille.py ===
Donnez la valeur de n = 30k : 29400000000
Extraction des premiers n à 2*n : 7.48801326751709 seconds ---

**  150067287 nombres trouvés en 168.4178957939148 secondes ** premier q [n ;2n]; Fam = 23 modulo 30
>>>
=== RESTART: E:\Documents\conjecture de Goldbach\cribleG2Y_par Famille.py ===
Donnez la valeur de n = 30k : 29550000000
Extraction des premiers n à 2*n : 7.534813404083252 seconds ---

**  150801281 nombres trouvés en 174.2055060863495 secondes **
>>>
=== RESTART: E:\Documents\conjecture de Goldbach\cribleG2Y_par Famille.py ===
Donnez la valeur de n = 30k : 29700000000
Extraction des premiers n à 2*n : 7.628413438796997 seconds ---

**  151535675 nombres trouvés en 424.33634519577026 secondes **

Dernière modification par LEG (16-06-2018 06:40:09)

Hors ligne

#261 16-06-2018 07:41:02

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 930

Re : crible en python

Bonjour,

Je vais essayer de trouver un fil d'Ariane dans ton abondante littérature... Ca ne risque de ne pas être évident parce que tu as du mal (c'est normal) - en ce qui concerne la programmation - à être synthétique.
Si ma version donne un nombre incorrect de premiers pour n=240, il est inutile d'espérer que pour des valeurs de n supérieures, ça s'arrange.
Donc j'en reste à n=240 jusqu'à ce le résulrat soit correct. Après seulement j'irais voir plus loin.

Tu as écrit :

donc j'ai regardé avec l'indentation de G9Y

il y avait quelque chose qui me chiffonnait  le fait d'avoir mis cpt et non j

il faut "réindenter" cette partie..avec:

Jusqu'à preuve du contraire, l'indentation est correcte.
En ce qui concerne cpt c'est le n° d'ordre du j traité.

Ce qui te chiffonne (tu veux un fer à repasser ? ^_^) vient de ce que tu as oublié ce que j'avais annoncé de ma "philisophie" :
je traite les j à la volée et j'ajoute maintenant dès qu'il y en a un accepté et stocké dans Fam.

A quoi sert Fam, alors ? Juste à empêcher qu'on traite un j trop souvent : à l'intérieur d'une Fam (ex Pf[i']), il n'y avait pas de doublons et il n'y en a pas non plus maintenant. Fam est un stockage temporaire.

Toi tu proposes de stocker tous les j dans Fam, puis de repartir de cpt =0 avec une nouvelle boucle, moi je traite les j dans l'ordre de leur création (avec l'index cpt) au fur et à mesure...

        for j in range(debut,fin,pas):    
            if j%3!=0 and j%5!=0:
                fam =Dico[j%30]
                if Fam[fam] == 0:  # Si l'emplacement contient 0
                    Fam[fam] = j     # j'y stocke le j
                    cpt+=1             # j'augmente mon compteur de 1
                    debut_index=Fam[cpt]//10//3  # Je crée le début_index à partir du j et la suite c'est le bloc s3
                    Nombres_cpt=nombres[cpt]
                    for index in range(debut_index, nbcell,pi):
                        Nombres_cpt[index] = 0

En principe, Fam[cpt] c'est le j traité. Je vais vérifier dans un moment...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#262 16-06-2018 08:53:21

LEG
Membre
Inscription : 19-09-2012
Messages : 269

Re : crible en python

ok pour le fer à repasser ...LoLLLLL

Toi tu proposes de stocker tous les j dans Fam, puis de repartir de cpt =0 avec une nouvelle boucle, moi je traite les j dans l'ordre de leur création (avec l'index cpt) au fur et à mesure...

ce n'est pas tout à fait cela que je propose , j'ai bien compris ton explication du fonctionnement de la programmation, que tu m'expliques .
mais le programme lui il garde bien en mémoire tous les j relatif à leur Pi à partir de cette fonction :

for i,pi in enumerate(Primes_init):
        r=nn%pi
        debut,fin,pas=r+pi*(1-r%2),1+r+pi*29,pi*2

et le dernier gardé en mémoire relatif au dernier Pi =31 , pour N=600
est {53, 115,177,239,301,363,425,487,549,611,673,735,797,859,921}

A quoi sert Fam, alors ? Juste à empêcher qu'on traite un j trop souvent : à l'intérieur d'une Fam (ex Pf[i'])

Ok pas de problème...

Mais tu crées le début d'index , à partir du traitement de Fam = [301,487, 611, 673, 797, 859, 53, 239] "avec l'exemple de la dernière Fam de n=600"

et si tu n'as pas l'instruction au bloc s3 :

 for cpt in range(8):

le bloc s3 ne va pas cribler...

En principe, Fam[cpt] c'est le j traité

oui exact, je les ai vérifiés , c'est comme cela que j'en suis arrivé à la fonction : for cpt in range(8)

Donc pour éviter tous ces traitements et stockage
il ne faut avoir qu'un famille , par ex : Dico={1:0}

pour n=240  et le premier Pi  = 7;avec R =4
les j sont{(11), 25,39,53,67,81,95,109,123,137,151,165,179,193,207..} la limite des j = 203=7*29

Alors , peut être qu'avec cette fonction : q,reste=divmod(j,30) : ont peut tout faire.

j=(11)
si reste != 1 puisque l'on a que la famille Dico={1:0} on passe j suivant, 53, 67, 109, 137, arrive :
j =151 ; reste ==1 et q == 5 d'après la fonction q,reste=divmod(j,30) : , et q , qui devient le début d'index pour :


       for j in range(1):
                   debut_index=q  # Je crée le début_index à partir du j et la suite c'est le bloc s3
                    Nombres_j=nombres[j]
                    for index in range(debut_index, nbcell,pi):
                        Nombres_j[index] = 0
 

voila ce que je pensais ....Donc, je pensais aussi que l'on pouvait se passer des Fam,cpt et leurs traitements...par


 for j in range(debut,fin,pas):    
            if j%3!=0 and j%5!=0:
                fam =Dico[j%30]
                if Fam[fam] == 0:  # Si l'emplacement contient 0
                    Fam[fam] = j     # j'y stocke le j
                    cpt+=1             # j'augmente mon compteur de 1
 

Voili , Voila....et en plus je n'ai plus besoins du fer.......
@+

Dernière modification par LEG (16-06-2018 08:57:49)

Hors ligne

#263 16-06-2018 11:30:34

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 930

Re : crible en python

Salut,

Je ne comprends absolument rien à tes propositions : trop d'infos tue l'info.
Je maintiens que, si, je crible.
J'ai un problème et je n'ai pas l'habitude de travailler en disant : je jette le bébé avec l'eau du bain...
Je ne change de méthode que si, lorsque j'ai trouvé le problème, je suis convaincu que je ne peux pas faire autrement...

Le problème est que, contrairement à ce que j'ai écrit, je me suis aperçu que les debut_index sont archi-faux...
J'ai donc remonté le courant et j'ai découvert que traitant les j à la volée, ils ne sont pas traités dans l'ordre de stockage d'une Fam.
Preuve :
           Vraie Fam :  [151, 67, 11, 193, 137, 109, 53, 179]
Ordre traitement  :  [11, 53, 67, 109, 137, 151, 179, 193]

Je présume que ça doit poser un pb qui fait que les debut_index sont tous faux et que mon prog 6.0 crible (si, si !) n'importe comment...
C'est toi le spécialiste là, : j'attends ta confirmation.

Donc ma vision de Fam était incomplète : non seulement, il y a stockage pour y éviter les doublons, mais stockage à un endroit précis en lien avec Dico : ce n'est pas pour rien...

En attendant, je retourne à ma Revue, mes relecteurs m'ont envoyés des propositions de correction...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#264 16-06-2018 12:38:05

LEG
Membre
Inscription : 19-09-2012
Messages : 269

Re : crible en python

vuC'est ce que je pense : peut être que tu n'aurais pas fais attention à l'ordre des étapes du programme..

La première étape est bien dans l'ordre du programme, des j :

Ordre traitement  :  [11, 53, 67, 109, 137, 151, 179, 193]

puis :

Vraie Fam :  [151, 67, 11, 193, 137, 109, 53, 179]

une fois traité par fam= Dico[j%30] ...!
C'est cette fonction qui classe dans l'ordre la vraie Fam....!

et ensuite traité par le bloc s3 début index pour criblage

c'est comme cela qu'à été écris le programme depuis le début...

J'ai donc remonté le courant et j'ai découvert que traitant les j à la volée, ils ne sont pas traités dans l'ordre de stockage d'une Fam.
Preuve :

comment veux tu traiter les j dans l'ordre de stockage, sans passer par fam= Dico[j%30]....?

Si ce n'était pas le cas, effectivement tu pourrais avoir les début d'index faux, ce qui n'est pas le cas et tu ne pourrais rien faire, pour faire fonctionner le programme, preuve il marche...! mais avec la fonction

for cpt in range(8):

que tu pensais inutile...

je t'ai indiqué l'ordre de fonctionnement du crible
1_) initialisation des [1] par rapport à n fixé = 240, ton exe...
2_) récupération des Pi d'Eratosthène
3_) calcul des reste R,  2n%Pi


for i,pi in enumerate(Primes_init):
        r=nn%pi
        debut,fin,pas=r+pi*(1-r%2),1+r+pi*29,pi*2
 

4_) édition des j < = pi*29 : [11, 53, 67, 109, 137, 151, 179, 193], pour Pi ==7
etc etc tous les [j.........] pour Pi==11

[j.........] pour Pi==13
[j.........] pour Pi==17
[j.........] pour Pi==19

5_) traitement des vraie Fam pour les mettre dans l'ordre de Dico={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}

donc ton exemple:  [151, 67, 11, 193, 137, 109, 53, 179]
et comme tu as 5 Pi, appartenant à [7;19]
tu auras 5 Fam [....................]

6_)ensuite début index et criblage bloc s3 ce qui donne pour la Fam ci dessus, [5,2,0,6,4,3,1,5] il y  a bien 8 début d'index; où est ce que c'est , ou que cela pourrait être faux...?
où est ce que tu as vue qu'ils étaient archi faux...? tous les programmes que tu as modifiés fonctionnent....

Mais ils y a deux blocs 2,3 qui font un travail, qui pourrait être réduit à un seul suivant, l'explication de mon dernier #post

à partir du point 4_)...c'est ce que je faisais avec excel ...ou autre ..

est ce que tu as vu le programme: def crible_G(n) du début  premières page  post #1 ("tu verrais en gros le principe...")

Dernière modification par LEG (16-06-2018 12:50:06)

Hors ligne

#265 16-06-2018 13:09:16

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 930

Re : crible en python

Re,

OK...
Inattention !
Je ne me suis pas méfié...
Du coup mon compteur cpt est non seulement faux mais inutile.
Je vais reprendre et m'en passer.
Ca va être vite fait.
Ce sera le moment de vérité...

C'est fait : 2 correctifs...
Remplacenent debut_index par debut_index=j//10//3
Suppression cpt et remplacement par fam

Moyennant quoi j'ai bien 40  premiers annoncés pour n=240
Je vais monter dans les n...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#266 16-06-2018 13:36:23

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 930

Re : crible en python

Re,

C'est fait. Ça roule...
Déception : je dois gagner 1/10e s pour n=36000000. Mais on gagne en place mémoire.
Satisfaction : j'ai toujours maintenu que, si, si, mon programme criblait bien. J'avais raison
Résultat :

Phase d'initialisation: 0.08200454711914062 seconds ---
Bloc S2_s3 : 1.3980798721313477 seconds ---
Extraction des premiers n à 2*n : 0.09300541877746582 seconds ---

**  2024396 nombres trouvés en 1.573089838027954 secondes **

from time import time
from os import system
from collections import OrderedDict

## V. 6.1 ##

def eratostene(n):
    n = int((2*n)**0.5)
    m = (n-1) // 2
    limite=1+n
    b = [True]*m
    premiers = [2]
    for i,p in enumerate(range(3,limite,2)):
        if b[i]:
            premiers.append(p)
            j = 2*i*i + 6*i + 3
            debut,pas=j,2*i+3
            for j in range(debut,m,pas):
                b[j] = False
    debut=i
    for i in range(debut,m):
        if b[i]:
            premiers.append(p)
        p += 2
    return premiers[3:]

def Crible_mod30(n):
    # INITIALISATION
    start_i= time()
    Primes_init = eratostene(n)
    nn,nbcell=n*2,n//30
    nombres=[]
    for i in range(8):
        nombres.append([1]*nbcell)
    P8=[1, 7, 11, 13, 17, 19, 23, 29]
    Dico=OrderedDict={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}
    s_1=time()-start_i
    print("Phase d'initialisation: %s seconds ---" % s_1)
   
    # FAMILLES POUR CHAQUE Pi
    start_time = time()
    for i,pi in enumerate(Primes_init):      
        r=nn%pi
        debut,fin,pas=r+pi*(1-r%2),1+r+pi*29,pi*2
        Fam=[0,0,0,0,0,0,0,0]
        for j in range(debut,fin,pas):    
            if j%3!=0 and j%5!=0:
                fam =Dico[j%30]
                if Fam[fam] == 0:
                    Fam[fam] = j
                    debut_index=j//10//3
                    Nombres_fam=nombres[fam]
                    for index in range(debut_index, nbcell,pi):
                        Nombres_fam[index] = 0  
    s_23=time()-start_time
    print("Bloc S2_s3 : %s seconds ---" % s_23)

    # CALCUL DES NOMRES PREMIERS ENTRE n ET 2*n
    start_time = time()
    total = 0
    for sous_liste in nombres:
        total+=sum(sous_liste)      
    s_4=time() - start_time
    s=s_1+s_23+s_4
    print("Extraction des premiers n à 2*n : %s seconds ---" % s_4)
    return total,s

n = int(input("Donnez la valeur de n = 30k : "))
nbr,s= Crible_mod30(n)
print ("\n** ",nbr,"nombres trouvés en %s secondes" % s ,"**")
system("pause")
 

Voilà, tu peux jouer

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#267 16-06-2018 15:27:23

LEG
Membre
Inscription : 19-09-2012
Messages : 269

Re : crible en python

Tu as raison il marche bien , effectivement on gagne environ 1 seconde sur 3mds , ce qui était à peu près prévu ..
je vais ensuite tester jusqu'où il va ...

Donnez la valeur de n = 30k : 3000000000
Phase d'initialisation: 2.2620038986206055 seconds ---
Bloc S2_s3 : 110.35459399223328 seconds ---
Extraction des premiers n à 2*n : 6.177610635757446 seconds ---

**  135095831 nombres trouvés en 118.79420852661133 secondes **
>>>

Donnez la valeur de n = 30k : 3000000000
Extraction des premiers n à 2*n : 6.19321084022522 seconds ---

**  135095831 nombres trouvés en 119.34020972251892 secondes **
>>>

je vais aller à la pêche....
Merci pour tous tes efforts , et j'espère que je pourrai te payer un bon coup à boire et à manger

Yoshi passe un bon week end  A+
Gilbert.

Hors ligne

#268 16-06-2018 16:46:41

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 930

Re : crible en python

Re,

Là, je crois bien que faire mieux (plus rapide) ça va être mission impossible...
A tout hasard, essaie ça :


from time import time
from os import system
from collections import OrderedDict

## V. 6.2 ##

def eratostene(n):
    n = int((2*n)**0.5)
    m = (n-1) // 2
    limite=1+n
    b = [True]*m
    premiers = [2]
    for i,p in enumerate(range(3,limite,2)):
        if b[i]:
            premiers.append(p)
            j = 2*i*i + 6*i + 3
            debut,pas=j,2*i+3
            for j in range(debut,m,pas):
                b[j] = False
    debut=i
    for i in range(debut,m):
        if b[i]:
            premiers.append(p)
        p += 2
    return premiers[3:]

def Crible_mod30(n):
    # INITIALISATION
    start_i= time()
    Primes_init = eratostene(n)
    nn,nbcell=n*2,n//30
    nombres=[]
    for i in range(8):
        nombres.append([1]*nbcell)
    P8=[1, 7, 11, 13, 17, 19, 23, 29]
    Dico=OrderedDict={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}
    s_1=time()-start_i
    print("Phase d'initialisation: %s seconds ---" % s_1)
   
    # FAMILLES POUR CHAQUE Pi
    start_time = time()
    for i,pi in enumerate(Primes_init):      
        r=nn%pi
        debut,fin,pas=r+pi*(1-r%2),1+r+pi*29,pi*2
        Fam=[0,0,0,0,0,0,0,0]
        for j in range(debut,fin,pas):    
            if j%3!=0 and j%5!=0:
                fam =Dico[j%30]
                if not Fam[fam]:
                    Fam[fam] = 1
                    debut_index=j//30
                    Nombres_fam=nombres[fam]
                    for index in range(debut_index, nbcell,pi):
                        Nombres_fam[index] = 0  
    s_23=time()-start_time
    print("Bloc S2_s3 : %s seconds ---" % s_23)

    # CALCUL DES NOMRES PREMIERS ENTRE n ET 2*n
    start_time = time()
    total = 0
    for sous_liste in nombres:
        total+=sum(sous_liste)      
    s_4=time() - start_time
    s=s_1+s_23+s_4
    print("Extraction des premiers n à 2*n : %s seconds ---" % s_4)
    return total,s

n = int(input("Donnez la valeur de n = 30k : "))
nbr,s= Crible_mod30(n)
print ("\n** ",nbr,"nombres trouvés en %s secondes" % s ,"**")
system("pause")
 

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#269 16-06-2018 19:13:38

LEG
Membre
Inscription : 19-09-2012
Messages : 269

Re : crible en python

Là, tu arrives au bout du bout...LoLLLL

je pense que c'est la même programmation qu'Eratosthène modulo 30 , il faut cribler uniquement par famille, les j au fur et à mesure, pour ne pas utiliser trop de mémoire. et en une seule opération avec q, reste=divmod(j/30)

voila actuellement ce que cela donne pour la famille Dico={1:0}

je me suis un peu embêter pour trouver le bon paramètre
toujours pareil pour ,  for i in range(1): au lieu de (8)

Mais ensuite il faut modifier la ligne  if j%3!=0 and j%5!=0:  , comme ceci,   if j%30==1:
ce qui est logique puisque l'on ne va traiter que les j se terminant 1 , donc congrus à 1 [30].

résultat avec V.6.2 pour n = 24 300 000 000
>>>
=== RESTART: E:\Documents\conjecture de Goldbach\cribleG2Y_par Famille.py ===
Donnez la valeur de n = 30k : 24300000000
Phase d'initialisation: 2.3400042057037354 seconds ---
Bloc S2_s3 : 122.60061550140381 seconds ---
Extraction des premiers n à 2*n : 6.162010908126831 seconds ---

**  125009260 nombres trouvés en 131.10263061523438 secondes **
>>>

ta dernière modifiée
>>>
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG3_modulo30.py =====
Donnez la valeur de n = 30k : 24300000000
Phase d'initialisation: 2.324404001235962 seconds ---
Bloc S2_s3 : 122.42901492118835 seconds ---
Extraction des premiers n à 2*n : 6.146410703659058 seconds ---

** 125009260 nombres trouvés en 130.89982962608337 secondes **  3/10éme
>>>

la limite maxi est de 29 850 000 000 en 772 "

Eratostène modulo 30 par famille, met pour n 60 000 000 000 , 300" mais cela n'à rien à voir avec Goldbach,  le criblage n'a pas de divisions , de plus ce n'est pas la même raison...ni la même fonction G(n) ...etc...

Dernière modification par LEG (16-06-2018 19:21:47)

Hors ligne

#270 17-06-2018 11:09:34

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 930

Re : crible en python

Re,

J'ai encore dû gagner un pou_ième en passant par un test bit à bit.
Je ne maîtrise pas totalement ça encore totalement, mais ça marche.
| est un opérateur binaire : 0|0=1, 0|1=1, 1|0  =1  et 1 |1 =1 qui force un bit précis à 1.
& est un autre opérateur binaire qui teste l'état d'un bit et renvoie 0 ou 1,2,4,8,16,32,64,128 dont les valeurs booleennes sont True...
J'initialise une variable temoin à 0
Sa représentation binaire est 00000000.
Supposons que fam=2
Je stocke la valeur booleenne du bit n° fam de temoin dans la variable testbit par testbit=(1<<fam)&temoin
Si testbit vaut False, je force la valeur du bit n° fam de temoin à 1 :
temoin=((1<<fam)|temoin
et je continue.
Ça remplace l'accès à la liste : je n'utilise qu'un temoin dont la valeur va varier de 1 à 255...


from time import time
from os import system
from collections import OrderedDict

## V. 6.3 ##

def eratostene(n):
    n = int((2*n)**0.5)
    m = (n-1) // 2
    limite=1+n
    b = [True]*m
    premiers = [2]
    for i,p in enumerate(range(3,limite,2)):
        if b[i]:
            premiers.append(p)
            j = 2*i*i + 6*i + 3
            debut,pas=j,2*i+3
            for j in range(debut,m,pas):
                b[j] = False
    debut=i
    for i in range(debut,m):
        if b[i]:
            premiers.append(p)
        p += 2
    return premiers[3:]

def Crible_mod30(n):
    # INITIALISATION
    global fam,temoin
    start_i= time()
    Primes_init = eratostene(n)
    nn,nbcell=n*2,n//30
    nombres=[]
    for i in range(8):
        nombres.append([1]*nbcell)
    P8=[1, 7, 11, 13, 17, 19, 23, 29]
    Dico=OrderedDict={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}
    s_1=time()-start_i
    print("Phase d'initialisation: %s seconds ---" % s_1)
   
    # FAMILLES POUR CHAQUE Pi
    start_time = time()
    for i,pi in enumerate(Primes_init):      
        r=nn%pi
        debut,fin,pas=r+pi*(1-r%2),1+r+pi*29,pi*2
        temoin=0
        for j in range(debut,fin,pas):    
            if j%3!=0 and j%5!=0:
                fam=Dico[j%30]
                testbit=(1<<fam)&temoin
                if not testbit:
                    temoin=(1<<fam)|temoin
                    debut_index=j//30
                    Nombres_fam=nombres[fam]
                    for index in range(debut_index, nbcell,pi):
                        Nombres_fam[index] = 0  
    s_23=time()-start_time
    print("Bloc S2_s3 : %s seconds ---" % s_23)

    # CALCUL DES NOMRES PREMIERS ENTRE n ET 2*n
    start_time = time()
    total = 0
    for sous_liste in nombres:
        total+=sum(sous_liste)      
    s_4=time() - start_time
    s=s_1+s_23+s_4
    print("Extraction des premiers n à 2*n : %s seconds ---" % s_4)
    return total,s

n = int(input("Donnez la valeur de n = 30k : "))
nbr,s= Crible_mod30(n)
print ("\n** ",nbr,"nombres trouvés en %s secondes" % s ,"**")
system("pause")

Pour n=360000000
Version 6.3

Phase d'initialisation: 0.6170353889465332 seconds ---
Bloc S2_s3 : 16.123922109603882 seconds ---
Extraction des premiers n à 2*n : 0.9270529747009277 seconds ---

**  17922760 nombres trouvés en 17.668010473251343 secondes **

Version 6.2

Phase d'initialisation: 0.6210355758666992 seconds ---
Bloc S2_s3 : 16.406938314437866 seconds ---
Extraction des premiers n à 2*n : 0.9250528812408447 seconds ---

**  17922760 nombres trouvés en 17.95302677154541 secondes **

Et encore, les variations de temps me paraissent aléatoires...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#271 17-06-2018 14:56:29

LEG
Membre
Inscription : 19-09-2012
Messages : 269

Re : crible en python

Bonjoiur Yoshi
je vois que cet algorithme te tient....
Tout d'abord:
a) même si on supprime la division de fam=Dico[j%30] on ne gagnerai rien...

b) comme tu l'as surement remarqué même si on ne stock plus cela ne changerai pas grand chose

c) Donc je ne pense pas que le criblage des j au fur et à mesure, de la fonction


 debut,fin,pas=r+pi*(1-r%2),1+r+pi*29,pi*2
        temoin=0
        for j in range(debut,fin,pas):
 

changerait quoi que ce soit à par 1 ou 2 secondes

d) car le résultat que j'ai testé en est une preuve suffisante

e) Je vais donc charger ta nouvelle version en cribleG4Y_modulo30 et voir ce que cela donne pour le criblage de la fam , P8 = 1

je te met trois résultats où j'ai modifié les lignes des cribles G9Y,G2Y et G3Y :


 for i in range(8):
 P8=[1, 7, 11, 13, 17, 19, 23, 29]
    Dico=OrderedDict={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}
 if j%3!=0 and j%5!=0:
                fam=Dico[j%30]
 

Afin de ne cribler que par famille...Je ferai ensuite de même avec G4Y et son résultat..
   
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG9Y_modulo30.py =====
Donnez la valeur de n = 30k : 29400000000
Phase d'initialisation: 3.2604055404663086 seconds ---
Famille de chaque Pi: : 4.336807727813721 secondes ---
Criblage des 8 familles: 155.1110725402832 seconds ---
Extraction des premiers n à 2*n : 7.534813642501831 seconds ---

**  150069716 nombres trouvés en 170.24309945106506 secondes **

=== RESTART: E:\Documents\conjecture de Goldbach\cribleG2Y_par Famille.py ===
Donnez la valeur de n = 30k : 29400000000
Phase d'initialisation: 4.10280704498291 seconds ---
Bloc S2_s3 : 161.14828300476074 seconds ---
Extraction des premiers n à 2*n : 7.566013336181641 seconds ---

** 150069716 nombres trouvés en 172.8171033859253 secondes **

===== RESTART: E:\Documents\conjecture de Goldbach\cribleG3Y_modulo30.py =====
Donnez la valeur de n = 30k : 29400000000
Phase d'initialisation: 3.9000065326690674 seconds ---
Bloc S2_s3 : 156.5618748664856 seconds ---
Extraction des premiers n à 2*n : 7.503613471984863 seconds ---

**  150069716 nombres trouvés en 167.96549487113953 secondes **

il y a des variables de temps qui s'expliquent en fonction de l'écart de temps pour lancer un nouveau test entre les trois cribles; mais l'un dans l'autre à 1 ou 2 seconde près cela ne change rien...Ce qui veut dire que ta dernière version ne gagnerait rien par rapport à la version V.6.2 = G3Y même en modifiant les 5 lignes ci dessus , afin de ne cribler que par famille et supprimer la division de  fam=Dico[j%30] qui devient inutile par famille...

@+

Dernière modification par LEG (18-06-2018 07:28:43)

Hors ligne

#272 17-06-2018 16:07:54

LEG
Membre
Inscription : 19-09-2012
Messages : 269

Re : crible en python

Tu avais raison, mais ce n'est peut être pas un pouième de pouième

===== RESTART: E:\Documents\conjecture de Goldbach\cribleG4_modulo30.py =====
Donnez la valeur de n = 30k : 24000000000
Phase d'initialisation: 2.8548049926757812 seconds ---
Bloc S2_s3 : 119.7614107131958 seconds ---
Extraction des premiers n à 2*n : 6.0996105670928955 seconds ---

**  123530551 nombres trouvés en 128.71582627296448 secondes **
>>>
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG4_modulo30.py =====
Donnez la valeur de n = 30k : 27000000000
Phase d'initialisation: 2.5740044116973877 seconds ---
Bloc S2_s3 : 138.06024265289307 seconds ---
Extraction des premiers n à 2*n : 6.8328118324279785 seconds ---

**  138301355 nombres trouvés en 147.46705889701843 secondes **
>>>

===== RESTART: E:\Documents\conjecture de Goldbach\cribleG4_modulo30.py =====
Donnez la valeur de n = 30k : 29100000000
Phase d'initialisation: 3.104405403137207 seconds ---
Bloc S2_s3 : 150.4622642993927 seconds ---
Extraction des premiers n à 2*n : 7.378813028335571 seconds ---

**  148600698 nombres trouvés en 160.94548273086548 secondes **
>>>
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG4_modulo30.py =====
Donnez la valeur de n = 30k : 29400000000
Phase d'initialisation: 3.744006395339966 seconds ---
Bloc S2_s3 : 166.06229162216187 seconds ---
Extraction des premiers n à 2*n : 7.628413438796997 seconds ---

**  150069716 nombres trouvés en 177.43471145629883 secondes **
>>>

il ne me reste plus qu'à vérifier si il passe à 30 mds....

la modif des 5 lignes est relatif au criblage par famille :


for i in range(8):    # on remplace 8 par 1

 P8=[1, 7, 11, 13, 17, 19, 23, 29]   #on remplace par P8=[1] il ne reste qu'une famille, la 1

    Dico=OrderedDict={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}  #on ne garde que {1,0} , il ne reste qu'une famille la 1:0

 if j%30==1:  # Car on ne va cribler que la famille 1 modulo 30, se terminant par 1

                fam=Dico[1]  # car on a testé ci dessus, si j = 1 modulo 30, d'où calcul du modulo inutile
 

Et malgrès cela , le chilmiliblic n'avance guerre plus vite , un peu plus de capacité mémoire...on est presque à 30mds....

Voila ....Yoshi , Mais c'est un très bon crible avec un bon programme...Je t'en remercie ....


Pour la conjecture de Goldbach, on sait que l'on a suffisamment de nombre premiers q, pour satisfaire la conjecture ...
On peut même calculer la densité des trois familles P8 = [1,7,13] relatif à 2n = 30k + 14, où : uniquement ces trois familles peuvent  satisfaire Goldbach .

La densité est d'environ : ((15k + 7) / Ln (30k + 14)) * 0,375
Pour n = 3 000 007 , on a 73509 premiers q [n ; 2n] , pour une estimation de la fonction ((15k + 7) / Ln (30k + 14)) * 0,375  = 72081

Pour 29 850 000 000 il met 319 secondes , mais pas d'amélioration sur la limite < 29 910 000 000...ce qui n'a pas d'importance
@+

Dernière modification par LEG (18-06-2018 11:20:26)

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante ?58 - 12
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums