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).

#226 11-05-2018 17:23:27

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : crible en python

Re,

J'avais vu ce matin : 35 au lieu de 40.
Je m'y attendais à moitié...
Ce que tu as suggéré demande probablement d'autre modifs en aval (ou peut-être en amont dans l'initialisation) Et: j'ai pensé qu'on devait modifier la structure de Pfam et son remplissage et peut-être le remplissage de la liste nombres.
Voilà les deux listes en question :
Pfam =[
[151, 67, 11, 193, 137, 109, 53, 179],
[0, 7, 161, 73, 227, 139, 0, 29],
[181, 0, 0, 103, 77, 0, 233, 0],
[0, 157, 191, 0, 0, 0, 0, 89],
[0, 157, 0, 43, 0, 0, 233, 119]
]
Tu vas pouvoir vérifier si ladite liste est conforme à tes attentes ou pas (14 zéros sur 40, ça me paraît beaucoup + 2 doublons 157 et 233)
Ancienne version pour comparaison
[
[151, 67, 11, 193, 137, 109, 53, 179],
[271, 7, 161, 73, 227, 139, 293, 29],
[181, 337, 311, 103, 77, 259, 233, 389],
[361, 157, 191, 463, 497, 259, 293, 89],
[271, 157, 461, 43, 347, 499, 233, 119]
]
Pour nombres :

[
[0, 1, 1, 1, 1, 0, 0, 1],
[0, 1, 0, 1, 1, 0, 1, 1],
[0, 1, 1, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 1],
[0, 1, 0, 1, 0, 1, 1, 0],
[0, 1, 1, 0, 0, 1, 1, 1],
[0, 0, 1, 1, 1, 1, 1, 0],
[0, 1, 0, 0, 1, 0, 1, 1]
]

liste obtenue avec la dernière version fonctionnelle (pour comparaison) : 5 différences (et 40-35 = 5.)

[
[1, 1, 1, 1, 1, 0, 0, 1],
[0, 1, 0, 1, 1, 0, 1, 1],
[0, 1, 1, 1, 1, 0, 0, 0],
[1, 0, 0, 0, 1, 1, 0, 1],
[1, 1, 0, 1, 0, 1, 1, 0],
[1, 1, 1, 0, 0, 1, 1, 1],
[1, 0, 1, 1, 1, 1, 1, 0],
[0, 1, 0, 0, 1, 0, 1, 1]
]

Et le crible qui génère ça avec la seule modif indiquée :


 # 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={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):
        Pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
        r=nn%pi
        debut,fin,pas=r+pi*(1-r%2),min(pi*29,n),pi*2 # seule modif : fin...
        for j in range(debut,fin,pas):
            Pf=Pfam[i]
            if j%3!=0 and j%5!=0:
                fam =Dico[j%30]      
                if Pf[fam] == 0:
                    Pf[fam] = j
    s_2=time()-start_time
    print("Famille de chaque Pi: : %s secondes ---" % s_2)
   
    #ON CRIBLE LES 8 COLONNES AVEC CHAQUE FAMILLE DE pi
    start_time = time()
    for i,Pf in enumerate(Pfam):
        pi=Primes_init[i]
        for j in range(8):
            debut_index=(Pf[j]-P8[j])//30
            Nombres_j=nombres[j]
            for index in range(debut_index, nbcell,pi):
                Nombres_j[index] = 0
 

Dernière partie S4 inchangée...

Normalement, tu as du grain à moudre...

Rappel : demain, je ne serais pas de retour avent 19 h 30/20 h)

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#227 11-05-2018 19:52:31

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

Re : crible en python

re bonsoir

Oui, je sais, tous les j de chaque sous-liste ci-dessus sont dans l'ordre croissant des j%30 : 1 7 11 13 17 19 23 29
Mais ça ne me dit pas qui ils sont.

Ce sont les 8 premiers termes de P8, en progression arithmétique de raison 30 et à part 1, qui n'est pas premier, ils vont servir de base pour calculer les [tex]j \in P8[/tex] dans la limite:[0 ; P_i*29] soit au maximum, 15 j pour chaque Pi, afin de cribler les entiers congrus à 2n%Pi, P premier, d'indice i. Soit Pi marquera 8 congrus sur Pi*8 nombres; en partant de l'index de j
Donc l'index de $J\in P8$ est le point de départ, marqué [0] de Pi qui va cribler par pas de Pi.

Au maximum pour Pi = 7 cela donnera 56 nombres ("pas 64"), qui seront criblés par les 5 Pi de bases,[tex]\leqslant\sqrt{2n}[/tex]
car 7*30 = 210 et 210/3,75 = 56. 3,75 et le coefficient pour obtenir les entiers de P8, par rapport aux entiers naturels positif >0 , quelque soit n.

Ce qui donnera pour n= 210 , ou 240 au maximum 39 nombres sur 56 , soit , comme Eratosthène, le crible de Goldbach donnera, 39 premiers sur 56 de n à 2n,Au minimum...

d'où attention à la modification de :

1) l'instruction dans, famille de Pi cette ligne ci-dessous, est la bonne ligne de code :

debut,fin,pas=r+pi*(1-r%2),1+r+pi*29,pi*2

  ; qui  ne doit pas être modifier avec l'instruction : ,min(pi*29,n) :

Car elle modifie les J de pfam , dans de grandes proportions pour n > 3000, et fausse totalement le crible, en supprimant des j, ce qui a pour effet de supprimer des entiers congrus à 2n%pi , d'où augmentation importante du nombre de nombres premiers de n à 2n , sans même améliorer le temps ce qui est logique , par contre tu auras beaucoup plus de cellules [1] à compter.

C'est pour cette raison, juste dans le poste au dessus, que je t'ai dit tu as raison il ne faut pas toucher à pfam, sauf si on ne l'utilise plus, ["car le problème des j > n n'est que pour les valeur de n < 3000, d'où comme tu le signales, c'est effectivement en aval que tu peux éventuellement améliorer..."].
Il y a une explication très simple, la racine carrée de 2n progresse moins vite que n..! Donc les j, ne pourront plus dépasser n >3000
En exemple :
[tex]\sqrt{600}[/tex] = 24 dans le pire des cas tu as 23*30= 690 très au dessus de n = 300

[tex]\sqrt{3000}[/tex] = 54 dans le pire des cas tu as 53*30= 1590 A peine au dessus de n = 1500

[tex]\sqrt{30000}[/tex] = 173 dans le pire des cas tu as 173*30= 5190 bien en dessus de n = 15000 et en plus aucune erreur possible car la limite F, prime sur la limite n, pour les j; comme tu l'avais remarqué , tu peux très bien avoir un j , le dernier, tel que j(-1) +2*Pi = 14987 pourquoi pas, donc à la limite de 15000 .

L'instruction : que tu as mise; ,min(pi*29,n, elle marque d'office les premiers de la ligne n°0, qu'elle marque [0] peut être à cause
de ,min, ce qui te donne dans ton premier tableau les fameux cinq 0...mais ensuite, elle fait le contraire elle supprime des j d'où augmentation de cellules [1] est résultat archi faux ; voici le résultat , avec cette mauvaise instruction , et en dessous les 2 tableaux avec la bonne instruction ci-dessus: le temps est identique, mais cela ne durerait pas car plus de[1] prendra du temps pour les compter...!

De la même Façon que ton idée pour compter la somme des 1, était très bonne car, l'inverse n'est pas possible, avec les [0].
D'autant plus, que ce que tu appelles les doublons, poseraient problème, du fait qu'ils correspondent à la décomposition unique en facteurs premiers d'un entiers positif, de n à 2n pour ce qui nous conserne, d'où le corollaire du TFA, un entier positif > 0, peut être congru de façon unique, à l'ordre près de ses facteurs, ce qui donne  des doublons de j ...!
******************************************************************************************************
Python 3.6.5 (v3.6.5:f59c0932b4, Mar 28 2018, 17:00:18) [MSC v.1900 64 bit (AMD64)] on win32
Type "copyright", "credits" or "license()" for more information.
>>>
========== RESTART: E:\executable algo P(30)\cribleG9Y_modulo30.py ==========
Donnez la valeur de n = 30k : 300000000
Phase d'initialisation: 0.28080034255981445 seconds ---
Famille de chaque Pi: : 0.28080058097839355 secondes ---
Criblage des 8 familles: 9.063616037368774 seconds ---
Extraction des premiers n à 2*n : 0.6396012306213379 seconds ---

**  15320277, résultat faux nombres trouvés en 10.26481819152832 secondes **
>>>
========== RESTART: E:\executable algo P(30)\cribleG9Y_modulo30.py ==========
Donnez la valeur de n = 30k : 600000000
Phase d'initialisation: 0.514801025390625 seconds ---
Famille de chaque Pi: : 0.561600923538208 secondes ---
Criblage des 8 familles: 19.234833478927612 seconds ---
Extraction des premiers n à 2*n : 1.2636022567749023 seconds ---

**  29579614  , résultat faux nombres trouvés en 21.574837684631348 secondes **

#############################################################################>>>

========== RESTART: E:\executable algo P(30)\cribleG9Y_modulo30.py ==========
Donnez la valeur de n = 30k : 300000000
Phase d'initialisation: 0.2964005470275879 seconds ---
Famille de chaque Pi: : 0.2964005470275879 secondes ---
Criblage des 8 familles: 8.985615730285645 seconds ---
Extraction des premiers n à 2*n : 0.6396012306213379 seconds ---

**  15072378 nombres trouvés en 10.218018054962158 secondes **  OK
>>>
========== RESTART: E:\executable algo P(30)\cribleG9Y_modulo30.py ==========
Donnez la valeur de n = 30k : 600000000
Phase d'initialisation: 0.514801025390625 seconds ---
Famille de chaque Pi: : 0.5772008895874023 secondes ---
Criblage des 8 familles: 18.798032999038696 seconds ---
Extraction des premiers n à 2*n : 1.248002052307129 seconds ---

**  29130002 nombres trouvés en 21.138036966323853 secondes **  OK

Ne touche surtout pas à Pfam, comme tu le pensais...., car le nombre de j, de R à + (k*Pi) =15, dont 8 appartiennent à P8.

Passe un bonweek end
@ A demain, mais ne te sent pas obligé, car il n'y a plus grand chose à modifier sauf si tu as envie de faire dans la foulée, famille de Pi et criblage avec les suppositions du post au dessus et J = 271 par ex:

Donc fam =Dico[271%30]==1 et le quotient, q==9 ; soit Dico[1%30]=Dico[1:0] ; c'est à dire:

fam , Dico(j%30) donne le reste et le quotient q;  Dico(1%30) donne Dico{1:0} de rang 9; pour P8 [1,] et en récupérant le quotient , on a le début d'index pour Dico{1:0} == 9; on part cribler par pas de Pi = 7; de 9 > à 8 dans ton exemple, ...etc

Ou tout simplement, mettre les débuts d'index dans Pfam de 0 à 7 à la place des j, de 0 à 7 et passer à la phase 3 criblage, ce qui supprime la division : ce passage:
for j in range(8):
            debut_index=(Pf[j]-P8[j])//30.

on passe au criblage:
for index in range(debut_index, nbcell,pi):

..ce qui est aussi...faisable...mais pour 2 secondes au grand max , je pense, pour 30mds et pour une famille...??

Dernière modification par LEG (28-05-2018 07:19:31)

Hors ligne

#228 12-05-2018 07:08:22

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

Re : crible en python

Pour info:
On peut calculer les rapports : (N / 3,75) / P(n). Où P(n) est le nombre d’entiers $[1]\not\equiv {30k}[P_i]$ = nombres de premiers P[N ; 2N] pour une limite N criblée.

Par exemple, criblage par tranche de 30 000 000 :
La fonction 2 = $\frac{N}{Ln 2N}$

  990000000 / Ln 1980000000 = 46 247 931 ;
Soit environ : 2*(960000000 / Ln 1920000000) – (930000000 / Ln 1860000000) = 46 249 791   ["suivant le principe d'une suite aritmétique, où $N \geqslant {30}$ progresse arithmétiquement de raison 15."]

(930000000/3,75) / 44211471 = 5,6094…
(960000000/3,75) / 45568107 = 5,6179….
(990000000/3,75) / 46923731 = 5,6261…
(1020000000/3,75) / 48277550 = 5,6340….
(1050000000/3,75) / 49629176 = 5,6418….
(1080000000/3,75) / 50979308 = 5,6493….
(1110000000/3,75) / 52326432 = 5,6567….

D'autres résultats :
G(n) fonction qui compte le nombre d'entiers $[1]\not\equiv {30k}[P_i]$

Si on prend la suite de G(n) par itération de 15:

G(15) = 4 ; G(30) = 7 ; G(45) = 10 ..etc..etc

La fonction 2, donne par itération de 15, le même principe qu’une suite arithmétique de raison 15, c’est-à-dire ≈ : Un+1 = 2Un – Un-1 , d’où cette fonction ne peut varier que de très peu, lorsque n = 15k →∞ et ce, quel que soit 15k criblé = G(n) :

15/ln30 = 4,41…     = U1                                     pour un réel de 4.
30/ln60 = 7,32..      = U2                                      pour un réel de 7
45/ln 90= 10,00…   =U3 ;   ≈   V1 = 2* U2 – U1 = 10,24…           pour un réel de 10       
60/ln120 = 12,53… =U4            V2 = 2* U3 – U2 = 12,67…          pour un réel de 13
75/ln150 =14,96..   =U5            V3 = 2* U4 – U3 = 15,06…          pour un réel de 14
90/ln180 = 17,33..  =U6             V4 = 2* U5 – U4 = 17,40…         pour un réel de 17
105/ln210= 19,63.. =U7             V5= 2* U6 – U5 = 19,69…         pour un réel de 19
120/ln240 = 21,89.. =U8            V6 = 2* U7 – U6 = 21,94…           pour un réel de 22
135/ln270 = 24,11..  =U9            V7 = 2* U8 – U7 = 24,15…         pour un réel de 25
150/ln300 = 26,29..  =U10         V8 = 2* U9 – U8 = 26,33…          pour un réel de 27
165/ln330 = 28,45.. =U11          V9 = 2* U10 – U9 = 28,48…        pour un réel de 28
180/ln360 = 30,58..  =U12          V10 = 2* U11 – U10 = 30,60…      pour un réel de 31
195/ln390 = 32,68..  =U13         V11 = 2* U12 – U11 = 32,70…     pour un réel de 33 
210/ln420 = 34,76..  =U14         V11 = 2* U13 – U12 = 34,78…     pour un réel de 35

Etc...etc..Avec des oscillations de + ou - 1 nombre , jusqu'à environ 990 , pour ensuite être en dessous de G(n).

En Conclusion, le crible de Goldbach, à les mêmes propriété qu le crible d'Eratosthène, de n à 2n , c'est un corollaire du T.N.P et du T.F.A,
d'où un entier naturel > 0, peut être congru de façon unique à l'ordre près de ses facteurs...Car un entier strictement positif peut s'écrire comme le produit de nombres premiers de façon unique ..etc ..etc, donc: pour un entier appartenant à [N ; 2n]...!

le nombre minimum de nombres premiers de $n$ à $2n$ , pour $n = 210$ est $39$, plus généralement pour $n$ de la forme de $30k$ et $ n \geqslant {210}$ vaut lorsque n tends vers + l'infini ,$\frac{n}{Ln 2n}$

Dernière modification par LEG (28-05-2018 07:37:07)

Hors ligne

#229 12-05-2018 19:04:34

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : crible en python

Salur,

Je rentre HS...
Je verrai demain

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#230 13-05-2018 19:35:13

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : crible en python

Bonsoir,

Je pense avoir dissipé - en partie - les nuées :
- tu as remarqué que dans s2, on calculait Pfam et que pour n très grand, ça faisait une palanquée de nombres,
- tu as remarqué que dans s3, on passait alors en revue tous les nombres j stockés...
  Et tu t'es dit : Et si, au lieu de les stocker, on les utilisait au fur et à mesure de leur création ?
- Donc tu cherches à fusionner s2 et s3 au prix du calcul de l'index associé pour mettre des 0, dans la liste nombres.

En utilisant Pfam, je ne crois pas qu'on puisse faire mieux que l'existant...
Cela posé, on peut penser sereinement à cette histoire de fusion et donc d'index...

Je vais examiner de bcp plus près qu'avant la façon dont, à partir d'un nombre extrait de Pfam, on détermine à quelle position de ma liste nombres, on remplace un 1 par un 0.

Je pense que la problématique est la suivante :
il faut trouver la formule permettant à partir d'un j calculé, donc connaissant sa position dans Pfam, à partir de cette position, faire comme si on venait de l'en extraire et enchaîner  directement sur le bloc s3.
Dans les 3 semaines qui viennent, l'échéance de parution de "ma" revue approchant, je vais devoir m'y mettre sérieusement et je ne pourrai penser à ton programme qu'épisodiquement...

Je pense à pister nommément chaque nombre de Pfam et pour cela
- afficher leur position exacte dans Pfam au moment du stockage via append (bloc s2), dans l'ordre de leur apparition
- afficher en regard leur position exacte dans Pfam au moment de leur extraction et dans l'ordre (bloc s3)
- afficher en regard l'index qui permet d'écrire 0 dans nombres
- chercher alors le lien pour chaque j affiché entre les 3 valeurs ci-dessous.

Si rien n'est évident, je recommencerai en écrivant Pfam comme liste simple, en  y stockant de 8 en 8 les éléments des ex-sous-listes, idem avec nombres...

Ce serait bien le diable s'il n'y avait rien à voir...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#231 14-05-2018 08:23:31

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

Re : crible en python

yoshi]Bonsoir, Re

Je pense avoir dissipé - en partie - les nuées :
- tu as remarqué que dans s2, on calculait Pfam et que pour n très grand, ça faisait une palanquée de nombres,

Tout à fait, car cela fait, pour 40000 Pi en gros 40000 * 8 j , à calculer la position et l'index de dédut
Et si, au lieu de les stocker, on les utilisait au fur et à mesure de leur création ? OUI


- Donc tu cherches à fusionner s2 et s3 au prix du calcul de l'index associé

oui

pour mettre des 0, dans la liste nombres.

qui correspond au début de la phase de Criblage par pas de Pi..

En utilisant Pfam, je ne crois pas qu'on puisse faire mieux que l'existant...

Exact, c'est pour cela que je t'ai dit on ne gagnera peut être que 1 à 2 secondes pour 30 mds et pour une Famille criblée, estimation faite , d'après le temps mis dans la phase Si : Famille de Pi...Donc...???


il faut trouver la formule permettant à partir d'un j calculé, donc connaissant sa position dans Pfam,

Position qui est donnée après : if j%3!=0 and j%5!=0: ..; Par la ligne : fam =Dico[j%30]  ...qui par conséquent permet aussi de récupérer le début d'index en utilisant le quotient....Donc de positionner le départ de Pi dans P8, pour le criblage, au lieu de positionner J pour ensuite aller calculer le début d'index dans s3...et criblage dans P8.. 
               

à partir de cette position, faire comme si on venait de l'en extraire et enchaîner  directement sur le bloc s3.

Parfaitement, enchainer sur S3 qui est le criblage dans P8, pour marquer les [0] , dans nombres....par pas de Pi ...

Tu as parfaitement déroulé le fonctionnement du criblage dans le programme...

Si rien n'est évident,

Le programme est très bien fait comme il est, il n'y aura rien à changer....

Ce serait bien le diable s'il n'y avait rien à voir... Ce ne serra que de la logique et du peaufinage, dans le déroulement des 2 phases S2 et S3..., Mais on ne pourra pas gagner grand chose en principe...Sauf : comme tu as tellement amélioré le fonctionnement du crible depuis l'origine en divisant le temps par 10  voir plus...

Alors pense d'abord à ta revues....Et avec un Grand merci...

Peut être que ce crible te permettra de formaliser mieux que je le fais et d'être le premier à montrer : que le nombre de nombres premiers lorsque n tend vers + l'infinie vaut:
n sur le log "nipeurien" de 2n au minimum ! ...De démontrer que ce ne sont que des corollaires du TNP et Du TFA, d'où en découle la conjecture de Goldbach....et le postulat de Bertrand passera à la postérité...car il ne sert vraiment à rien , concernant la répartition des nombres premiers, surtout de n à 2n.....

@+

Dernière modification par LEG (28-05-2018 07:57:40)

Hors ligne

#232 07-06-2018 08:58:38

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

Re : crible en python

Bonjour @Yoshi :

Je reviens sur ton dernier post du 13/05 relatif à ta conclusion.

Je pense à pister nommément chaque nombre de Pfam et pour cela
- afficher leur position exacte dans Pfam au moment du stockage via append (bloc s2), dans l'ordre de leur apparition
- afficher en regard leur position exacte dans Pfam au moment de leur extraction et dans l'ordre (bloc s3)
- afficher en regard l'index qui permet d'écrire 0 dans nombres
- chercher alors le lien pour chaque j affiché entre les 3 valeurs ci-dessous.

En principe il n'y a qu'un seul lien pour chacun des j affiché appartenant à [R ; Pi*29] et pour chaque Pi.
C'est la division de j par 30 ; qui te donne le reste R est le quotient x, qui est le début d'index ou le rang dans p8 = liste nombres; c'est à dire la position du premier [0] d'une des 8 familles de p8. Donc, position de départ de Pi pour cribler l'une des 8 familles jusqu'à n/30. Pour chaque Pi, il y a donc 8 débuts d'index relatif aux 8 j donné par la quotient x

pour chaque j affiché, tu as donc j%30 = r , si r = Dico [1:0, 7:1, 11:2, 13:3, 17:4, 19:5, 23:6, 29:7] tu as sa famille p8; et en récupérant le quotient x , lors de cette division qui je suppose, correspond à cette intruction : [ q,reste=divmod((j),30) ] ; tu as le début d'index qui donne le premier [0] dans sa famille Dico=[1:0,....,29:7]et le début du criblage Pour Pi; puis de passer  à j suivant.

Prenons par exemple n = 240, soit 2n = 480 , le premier Pi = 7
liste nombres: 240/30 =8; les 8familles Dico[..] sur 8 lignes, indice de 0 à 7.
480%7= 4
j = 4+7 =11 et :

q,reste=divmod((j),30)

donne début d'index : q= 0, et r =11 soit: Dico[11:2] , Pi = 7, crible de 0 à 7 dans liste nombres p8 = Dico[....] :

[.........p8 = Dico.........]
[1:0, 7:1, 11:2, 13:3, 17:4, 19:5, 23:6, 29:7]

[1, 1, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1,1 , 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 0, 1, 1, 1, 1, 1]
]

Puis on passe à j suivant = 11 + incr = 25 ;

q,reste=divmod((j),30)

r = 25 n'appartient pas à Dico[..].

on passe à j suivant 25+incr = 39 ;

q,reste=divmod((j),30)

r = 9 n'appartient pas à Dico[..].

j suivant 39+incr = 53 ;

q,reste=divmod((j),30)

q=1 et r = 23 ; Dico[ 23:6, ..]. Pi = 7, crible de 1 à 7...

etc...
une fois les 8 j passés, on passe à Pi suivant =11 et on réitère....

Alors effectivement on peut gagner en nombres d'opérations et on ne stock pas dans Pfam...comme tu l'as pensé ...quel sera le gain ...?
pour des valeurs de n= 300 000 000, et +  ; en criblant par famille c'est à dire : in range(1): au lieu de (8)


Si rien n'est évident, je recommencerai en écrivant Pfam comme liste simple, en  y stockant de 8 en 8 les éléments des ex-sous-listes, idem avec nombres...

Je pense que là, il y a une erreur d'interprétation du crible...
Il y a toujours pour n > 990 , 8 j appartenant à Dico[....] parmi les 15 j affichés, appartenant à [R ; Pi*29]

Mais liste nombres il y a bien 8 colonnes = 8 familles, donc 8 départs [0] par Pi,  mais le nombre de lignes dépend de n...! Tu ne peux pas faire de 8 en 8....

Donc tu vois, il n'y a que les deux blocs s2 et s3 à voir , et si cela vaut le coup.....

*****************************************************************

Voila la limite maxi, que j'ai criblée pour une famille.

===== RESTART: E:\Documents\conjecture de Goldbach\cribleG9Y_modulo30.py =====7[30] …>23[30]
Donnez la valeur de n = 30k : 24030000000
Phase d'initialisation: 2.3088040351867676 seconds ---
Famille de chaque Pi: : 2.9016051292419434 secondes ---
Criblage 1 familles: 120.72861194610596 seconds ---
Extraction des premiers n à 2*n : 6.08401083946228 seconds ---

**  123 676 669 nombres trouvés en 132.02303194999695 secondes **
>>>
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG9Y_modulo30.py =====
Donnez la valeur de n = 30k : 24060000000
Phase d'initialisation: 2.3400039672851562 seconds ---
Famille de chaque Pi: : 2.8080053329467773 secondes ---
Criblage 1 familles: 121.66461396217346 seconds ---
Extraction des premiers n à 2*n : 6.068410634994507 seconds ---

**  123 824 660 nombres trouvés en 132.8810338973999 secondes **
>>>
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG9Y_modulo30.py =====
Donnez la valeur de n = 30k : 24090000000
Phase d'initialisation: 2.2932040691375732 seconds ---
Famille de chaque Pi: : 2.9016051292419434 secondes ---
Criblage 1 familles: 124.42581844329834 seconds ---
Extraction des premiers n à 2*n : 6.162010669708252 seconds ---

**  123 972 083 nombres trouvés en 135.7826383113861 secondes **

*********************************************************
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG9Y_modulo30.py =====1[30]….> 29[30]

Donnez la valeur de n = 30k : 24030000000
Phase d'initialisation: 2.230803966522217 seconds ---
Famille de chaque Pi: : 2.8236050605773926 secondes ---
Criblage 1 familles: 122.7722156047821 seconds ---
Extraction des premiers n à 2*n : 6.068410634994507 seconds ---

**  123 677 693 nombres trouvés en 133.89503526687622 secondes **
>>>
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG9Y_modulo30.py =====
Donnez la valeur de n = 30k : 24060000000
Phase d'initialisation: 2.2620036602020264 seconds ---
Famille de chaque Pi: : 2.839205026626587 secondes ---
Criblage 1 familles: 121.97661399841309 seconds ---
Extraction des premiers n à 2*n : 6.068410873413086 seconds ---

**  123 826 211 nombres trouvés en 133.14623355865479 secondes **
>>>
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG9Y_modulo30.py =====
Donnez la valeur de n = 30k : 24090000000
Phase d'initialisation: 2.2776038646698 seconds ---
Famille de chaque Pi: : 2.8548049926757812 secondes ---
Criblage 1 familles: 121.97661447525024 seconds ---
Extraction des premiers n à 2*n : 6.084010601043701 seconds ---

**  123 974 177 nombres trouvés en 133.19303393363953 secondes **
>>>


C'est d'ailleurs curieux le temps mis en fonction des tranches de n ou des familles

Cordialement
@+

Dernière modification par LEG (18-07-2018 06:34:13)

Hors ligne

#233 07-06-2018 10:21:53

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : crible en python

Re,

Je vais avoir très bientôt  du temps pour revenir aux affaires...
J'avais préparé (et gardé sous le code) cette version avec fusion des blocs s2 et s3...
J'ignorais si ça fonctionnait.

Je viens de la lancer :
index out of range = j'essaie d'accéder à la liste nombres avec un index hors limite, ici pour n=240 : j=11, alors qu'on ne devrait pas aller au-delà de 11.
C'est très exactement cette ligne qui coince :Nombres_j=nombres[j]
nombres =
[
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
]
ce qui veut dire l'index j calculé avant est incorrect.
Je n'ai pas vraiment le temps de chercher... Je m'étais dit qu'un dictionnaire ordonné à la place d'un dico simple allait servir (j'ai oublié pourquoi) mais le pb n'est pas là...


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

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):
        Pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
        r=nn%pi
        debut,fin,pas=r+pi*(1-r%2),1+r+pi*29,pi*2
        for j in range(debut,fin,pas):
            Pf=Pfam[i]
            if j%3!=0 and j%5!=0:
                fam =Dico[j%30]
                indice=j//10//3  ### C'est lui qui est en cause
                Nombres_j=nombres[j]
                for index in range(debut_index, nbcell,pi):
                    Nombres_j[index] = 0
    s23=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=s1+s23+s4
    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")
 


@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#234 07-06-2018 11:56:45

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

Re : crible en python

re

indice=j//10//3  ### C'est lui qui est en cause

ben oui...
car si je comprend bien supposons dans ton exemple le premier j = 11
l'indice c'est 11//30 = 0

or :  si tu fais 11//10 = 1 et encore 1//3 = 0
donc l'indice qui reste c'est quoi....? 1 ou 0

On devrait avoir dans nombres :

nombres =
[
[1, 1, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 0, 1, 1, 1, 1, 1],
]

Dernière modification par LEG (07-06-2018 11:58:48)

Hors ligne

#235 07-06-2018 12:05:19

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

Re : crible en python

quand j'essaye de le lancer voila le message d'erreur: j'ai remplacé j//10//3 par j//30

==== RESTART: E:\Documents\conjecture de Goldbach\cribleG1_par Famille.py ====
Traceback (most recent call last):
  File "E:\Documents\conjecture de Goldbach\cribleG1_par Famille.py", line 66, in <module>
    nbr,s= Crible_mod30(n)
  File "E:\Documents\conjecture de Goldbach\cribleG1_par Famille.py", line 49, in Crible_mod30
    Nombres_j=nombres[j]
IndexError: list index out of range
>>>

en laissant j//10//3
voila le message d'erreur:

Traceback (most recent call last):
  File "E:\Documents\conjecture de Goldbach\cribleG1_par Famille.py", line 66, in <module>
    nbr,s= Crible_mod30(n)
  File "E:\Documents\conjecture de Goldbach\cribleG1_par Famille.py", line 50, in Crible_mod30
    for index in range(debut_index, nbcell,pi):
NameError: name 'debut_index' is not defined

Dernière modification par LEG (07-06-2018 12:17:47)

Hors ligne

#236 07-06-2018 12:37:19

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : crible en python

Re,

LEG a écrit :

  File "E:\Documents\conjecture de Goldbach\cribleG1_par Famille.py", line 49, in Crible_mod30
    Nombres_j=nombres[j]
IndexError: list index out of range

Yoshi a écrit :

ndex out of range = j'essaie d'accéder à la liste nombres avec un index hors limite, ici pour n=240 : j=11, alors qu'on ne devrait pas aller au-delà de 11.
C'est très exactement cette ligne qui coince :Nombres_j=nombres[j]

C'est bien ce que j'ai dit...

Quant à :

or :  si tu fais 11//10 = 1 et encore 1//3 = 0
donc l'indice qui reste c'est quoi....? 1 ou 0

Tu n'as pas vérifié ?
Alors voilà

>>> 11//10//3
0
>>> 271//10//3
9
>>> 271//30
9
>>>
 

Je t'avais dit que ce n'était pas testé...
J'aurais dû noter pourquoi, j'ai écrit ça comme ça : maintenant, c'est loin...

Bon, wait and see... Je trouverai !
Patience !

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#237 07-06-2018 13:16:04

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

Re : crible en python

ok ......j'ai compris pour 11//10//3

            if j%3!=0 and j%5!=0:
                fam =Dico[j%30]
                indice=j//10//3  ### C'est lui qui est en cause { mettre indice=[j]//10//3 }
                Nombres_j=nombres[j]
                for index in range(debut_index, nbcell,pi):  et,  for index in range(indice, nbcell,pi):
                    Nombres_j[index] = 0


Mais j , ce ne peut être un index car j = 11, correspond pour n=240 à : 4 +7 où 4 est le reste de 480%7...
,
l'index de j = 11 est : 11/10//3 = 0 est comme j=11 ; ce qui vaut dans Dico[ 1:0, 7:1, 11:2 ....] dans nombres cet index 0, va se positionner sur la première ligne, 3ème colonne; afin de remplacer [1] par [0]
[1, 1, 0, 1, 1, 1, 1, 1],

et Pi = 7, va marquer d'un [0] de 0 à 7..

peut être que le fait de nommer indice = j//10//3 est en contradiction avec la ligne :  for index in range(debut_index, nbcell,pi):

début_index devrait être nommé indice.....???

Ou encore: Comme dans mon dernier programme j'ai :

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

il faut peut être écrire :

debut_index=[j]//10//3  # on enlève Pf
            Nombres_j=nombres[j]
            for index in range(debut_index, nbcell,pi):


voila .....

Dernière modification par LEG (07-06-2018 13:21:44)

Hors ligne

#238 07-06-2018 14:13:40

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

Re : crible en python

j'ai tété les deux possibilité et c'est toujours la ligne 48 qui cause l'erreur :

Traceback (most recent call last):
  File "E:\Documents\conjecture de Goldbach\cribleG1_par Famille.py", line 66, in <module>
    nbr,s= Crible_mod30(n)
  File "E:\Documents\conjecture de Goldbach\cribleG1_par Famille.py", line 48, in Crible_mod30
    debut_index=[j]//10//3  ### C'est lui qui est en cause
TypeError: unsupported operand type(s) for //: 'list' and 'int'

Hors ligne

#239 07-06-2018 16:27:47

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : crible en python

RE,

J'avais essayé aussi.

TypeError: unsupported operand type(s) for //: 'list' and 'int'

Mais ça, c'est autre chose (et qui ne vient pas de ma programmation) : il y a un problème d'erreur de manipulation entre entier et liste.
Soit tu traites un entier comme si c'était une liste, soit l'inverse ; difficile à repérer. Sans mrsblocS2+S3 que tu as modifié, je ne peux savoir...
Voilà pourquoi je t'avais dit avoir décidé un jour,  quand je programme, de commencer les noms de listes ou les chaînes par des "majuscules", et les variables numériques par des minuscules...
D'autre part, à quoi bon calculer  fam =Dico[j%30], si c'est pour ne pas l'utiliser...
Donc, je pense qu'il y a un souci là-dessous.

Quand j'avais préparé le bloc S2+S3, j'avais quand même réfléchi un peu dessus : si j'ai gardé fam =Dico[j%30], il y avait sûrement une raison !
Je vais  ma retrouver (pas tout de suite) en comparant le dernier bon code et celui-ci : ça doit pouvoir marcher !

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#240 07-06-2018 18:07:26

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

Re : crible en python

Quand j'avais préparé le bloc S2+S3, j'avais quand même réfléchi un peu dessus : si j'ai gardé fam =Dico[j%30], il y avait sûrement une raison !

tu avais utilisé: fam =Dico[j%30] pour faire appel à une bibliothèque et  pour placer les j dans pfam en fonction du reste de j%30 = Dico={1:0, 7:1, ....etc.., 29:7}
c'est vrai que là , si j = 161, par exemple  avec Pi = 11, pour n=240

il te faut bien avoir Dico[j%30] = 11 et début index = 5; donc Dico={11:2} afin de placer le début_index = 5 dans nombres colonne 2; afin de cribler, ie: marquer les [0] par pas de 11, de 5 à 7 ; dans nombres : c'est à dire, la colonne 2...

Il te fallait bien une fonction qui définisse la colonne où le programme, va placer l'index de j...non ? la colonne 2, correspond à p8 = 11

Pour moi je pensais que Dico={1:0,.......,29:7} te servais dans le programme à fixer la colonne ou Famille de p8, dans nombres...pour ensuite placer l'index de j...

je te met le dernier code, (fais attention, j'ai rajouté ' pour les [i'] afin de l'éditer) :


from time import time
from os import system

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 CribleG9Y_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={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):
        Pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
        r=nn%pi
        debut,fin,pas=r+pi*(1-r%2),1+r+pi*29,pi*2
        for j in range(debut,fin,pas):
            Pf=Pfam[i']
            if j%3!=0 and j%5!=0:
                fam =Dico[j%30]      
                if Pf[fam] == 0:
                    Pf[fam] = j
    s_2=time()-start_time
    print("Famille de chaque Pi: : %s secondes ---" % s_2)
   
    #ON CRIBLE LES 8 COLONNES AVEC CHAQUE FAMILLE DE pi
    start_time = time()
    for i,Pf in enumerate(Pfam):
        pi=Primes_init[i'
]
        for j in range(8):
            debut_index=Pf[j]//10//3
            Nombres_j=nombres[j]
            for index in range(debut_index, nbcell,pi):
                Nombres_j[index] = 0
    s_3=time() - start_time
    print("Criblage des 8 familles: %s seconds ---" % s_3)
    #print(Nombres_j)

    # 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            
    print("Extraction des premiers n à 2*n : %s seconds ---" % s_4)
    return total,s_1+s_2+s_3+s_4,

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

comment tu fais pour garder les couleurs dans le code...?

celui ci de programme, pour une famille criblée, je suis allé jusqu'à 26 160 000 000 :
>>>
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG9Y_modulo30.py ========== 1[30].….>29[30]
Donnez la valeur de n = 30k : 26160000000
Phase d'initialisation: 2.4804043769836426 seconds ---
Famille de chaque Pi: : 3.135605573654175 secondes ---
Criblage des 8 familles: 131.55503129959106 seconds ---
Extraction des premiers n à 2*n : 6.583211660385132 seconds ---

**  134 171 843 nombres premiers trouvés en 143.754252910614 secondes ** dans p8 = 29

je n'ai fais qu'apporter tes modifications depuis cribleG1....au fur et à mesure de tes instructions et modif... Rien que le bloc s4, il a divisé le temps par 20 au minimum...

ça va être difficile de faire beaucoup plus vite , par contre on risque d'y gagner en mémoire et de pousser la limite n, vers 40 mds...

et autre chose , Dico={1:0........,29:7} me permet de définir la famille que je veux cribler , en modifiant l'ordre ; ainsi que in range (8):
Il se peut que ce soit Pfam,P8=[],[1, 7, 11, 13, 17, 19, 23, 29], qui ne serve plus à rien...dans ta nouvelle version...sauf si c'est lié à
Dico = {1:0.........29:7}

@+

Dernière modification par LEG (08-06-2018 08:03:15)

Hors ligne

#241 07-06-2018 18:55:41

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : crible en python

Re,

comment tu fais pour garder les couleurs dans le code...?

Réponse simple : regarde ton post, je l'ai édité... Après code, j'ai ajouté = Python

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#242 07-06-2018 19:29:34

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : crible en python

Re,

comment tu fais pour garder les couleurs dans le code...?

Réponse simple : regarde ton post, je l'ai édité... Après code, j'ai ajouté = Python

J'ai toujours un problème d'indice avec j=271 j//30 ou j//10//3 --> 9 et là, crac message d'erreur !
271 valeur erronée ?

De toutes façons pour accéder à la liste nombres, j'ai besoin de 2 indices
Le 1er détermine la sous_famille (j'en ai 8, numérotées de 0 à 7) : dans ma version, j'ai essayé avec de prendre i comme indice pour accéder à la sous-famille (après le plantage, j'ai récupéré la liste nombres, le 2e la position du 1 dans la sous-famille sélectionnée à passer à 0.
Tout repose sur ces deux indices : il faut que les obtienne sans passer par Pfam : je pensais que c'était, dans l'ordre Dico[j%30] et indice=j//30... Si oui alors tout repose sur le calcul de j...
Voilà la liste nombres erronée (donc ce n'est pas çà) obtenue avec i (1er indice) celui de l'énumération de la position des premiers fournis par le def eratostene :
[
[0, 0, 1, 1, 1, 1, 1, 0],
[0, 1, 1, 1, 1, 1, 1, 0],
[0, 0, 1, 1, 1, 1, 1, 0],
[0, 1, 1, 1, 1, 1, 1, 0],
[0, 0, 1, 1, 1, 1, 1, 0],
[0, 0, 1, 1, 1, 1, 1, 0],
[0, 1, 1, 1, 1, 1, 1, 0],
[1, 0, 1, 1, 1, 1, 1, 1]
]
et la bonne liste :
[
[1, 1, 1, 1, 1, 0, 0, 1],
[0, 1, 0, 1, 1, 0, 1, 1],
[0, 1, 1, 1, 1, 0, 0, 0],
[1, 0, 0, 0, 1, 1, 0, 1],
[1, 1, 0, 1, 0, 1, 1, 0],
[1, 1, 1, 0, 0, 1, 1, 1],
[1, 0, 1, 1, 1, 1, 1, 0],
[0, 1, 0, 0, 1, 0, 1, 1]
]

C'est plus compliqué que prévu : il faudrait que je m'investisse à plein temps, mais ce n'est pas pour tout de suite...
Je suis très loin et très proche du but.

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#243 08-06-2018 06:39:15

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

Re : crible en python

Bonjour
@Yoshi , merci pour le code = python...

De toutes façons pour accéder à la liste nombres, j'ai besoin de 2 indices
Le 1er détermine la sous_famille (j'en ai 8, numérotées de 0 à 7) :

Attention cet indice est donné par Dico={1:0, 7:1,.........,29:7} c'était pour cela que tu as utilisé cette bibliothèque en remplacement des if et else ainsi que  des fam 0,1,2.....,7 dans le premier programme...

dans ma version, j'ai essayé avec de prendre i comme indice pour accéder à la sous-famille (après le plantage, j'ai récupéré la liste nombres, le 2e la position du 1 dans la sous-famille sélectionnée à passer à 0.

Ce deuxième indice est donné par le quotient de la division de j par 30 ou par //10//3

dans ta nouvelle formule il est clair que pour n=240, j =271 ne peut aller, car > à n , donc il devrait y avoir une instruction qui permet de ne pas en tenir compte et de finir le criblage lorsque j est > à n ...C'est ce qui se passe dans les {cribleG1 à G9Y modulo30} .. pour des petites valeurs de n < 990.
Ce qui ne devrait pas empêcher ton nouveau programme de fonctionner quand même....

Tout repose sur ces deux indices : il faut que les obtienne sans passer par Pfam : je pensais que c'était, dans l'ordre Dico[j%30] et indice=j//30... Si oui alors tout repose sur le calcul de j...

c'est bien dans cet ordre que cela doit fonctionner...

par exemple :


# liste nombres, n = n/30 :

.........Dico={1:0.......29:7}
in: {F1  F7  F11  F13  F17  F19  F23  F29}
0 :  1   1   1   1   1   1   1   1 
1 :  1   1   1   1   1   1   1   1 
2 :  1   1   1   1   1   1   1   1 
3 :  1   1   1   1   1   1   1   1 
4 :  1   1   1   1   1   1   1   1 
5 :  1   1   1   1   1   1   1   1 
  :   1   1   1   1   1   1   1   1
  :   1   1   1   1   1   1   1   1
  :   1   1   1   1   1   1   1   1
  :   1   1   1   1   1   1   1   1
  :   1   1   1  1    1   1   1   1
n :  1   1   1   1   1   1   1   1 
 

Ordre des étapes :
limite n , initialisation des [1] <= n//30 . On a les Pi ,
Pour chaque Pi:

Calcul de R et liste des 15 j = Ri dans la limite f = Pi * 29 ; # Comme ça , on ne stock qu'une liste de J au fur et à mesure

on commence les tests : if : j%3 ou j%5 != 0. Alors j%30 = Dico={1,…à 29}.et on récupère l'indice=quotient donné par j%30

que l'on va immédiatement marquer [0] dans sa Fam liste nombres, ie; remplacer le [1] en [0], pour cribler par pas de Pi jusqu'à la limite n/30. #ce qui évite de stocker les j dans Pfam

Puis on passe à j suivant..Dans la limite j <= f quand Pi a fini de cribler P8, les 8 fam de la liste nombres; on passe à Pi suivant et on réitère.

Dernière modification par LEG (13-06-2018 16:02:55)

Hors ligne

#244 08-06-2018 06:48:18

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : crible en python

Re,

J'ai retrouvé pendant la nuit (oui, oui, ça m'arrive souvent) le fil conducteur - mal mis en application encore, certes - qui a présidé à la nouvelle mouture.
Je m'étais dit que comme
1. On fabriquait tous les nombres de Pfam pour les stocker un par un et dans les cas limites, il y en a plusieurs milliards
2. On reprenait ensuite tous ces Pfam un par un pour les traiter
3. il serait peut-être plus judicieux de les construire un par un sans les stocker et de les traiter à la volée pour modifier la liste nombres...

Voilà, j'y vois un peu clair...
C'est peut-être évident, mais c'est déjà beaucoup : au lieu de tâtonner au hasard comme hier soir, je sais maintenant de nouveau où je vais !

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#245 08-06-2018 07:04:31

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

Re : crible en python

{ la nuit permet de classer les idées , pour trier et donner la solution au petit matin....LoLLLL} 

Ca, j'ignorai que le programme, calculer tous les pfam et qu'il les stockait, pour ensuite les traiter un par un..

Effectivement il faut les traiter au fur et à mesure...un par un...dans la limite de n; afin de "modifier" de cribler la liste nombres...

C'est aussi pour cela que l'on pouvait faire pareil pour les j les traiter au fur et à mesure, passez à j suivant , dans la limite de n , puis Pi suivant , au fur et à mesure la liste nombres est modifiée ie; criblée les [1] remplacé par [0].

c'est cette partie centrale du programme qu'il faut voir , "pourtant les temps mis pour initialiser et famille de Pi sont vraiment minime.."
Tu as réduit le temps par plus de 30...

Lorsque je crible avec crible_mod30 que tu avais déjà modifié et avec criblG9y_mod30 qui est le dernier, on divise le temps par 5, pour n = 3 000 000 000 , pour une famille criblée ; de plus je suis limité à 15 000 000 000 environ

pour info: je met les 3 temps, on crible la famille 7[30], pour obtenir les premiers congrus à 23[30]

====== RESTART: E:\Documents\conjecture de Goldbach\crible_modulo30.py ======
Donnez la valeur de N = 30k : 9000000000
Crible mod30 : Initialisation: 13.556423664093018 seconds ---
Crible mod30 : Famille de chaque Pi: 1.1388018131256104 seconds ---
Crible mod30 : Criblage des 8 familles: 70.7617244720459 seconds ---
Crible mod30 : Extraction des premiers n à 2*n : 93.17896389961243 seconds ---
On a 48272778 nombres premiers
>>>

==== RESTART: E:\Documents\conjecture de Goldbach\cribleG1_par Famille.py ====
Donnez la valeur de n = 30k : 9000000000
CribleG1_mod30 : Initialisation: 13.322423696517944 seconds ---
CribleG1 mod30 : Famille de chaque couple R et Pi: 1.0920016765594482 seconds ---
CribleG1 mod30 : Criblage des 8 familles: 64.2877128124237 seconds ---
CribleG1 mod30 : Extraction des premiers n à 2*n : 22.588839769363403 seconds ---
On a 48272778 nombres premiers
>>>

===== RESTART: E:\Documents\conjecture de Goldbach\cribleG9Y_modulo30.py =====
Donnez la valeur de n = 30k : 9000000000
Phase d'initialisation: 0.904801607131958 seconds ---
Famille de chaque Pi: : 1.123201847076416 secondes ---
Criblage des 8 familles: 41.60527324676514 seconds ---
Extraction des premiers n à 2*n : 2.2776038646698 seconds ---

**  48272778 nombres trouvés en 45.91088056564331 secondes **
>>>

Dernière modification par LEG (08-06-2018 07:56:59)

Hors ligne

#246 08-06-2018 16:49:19

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

Re : crible en python

peut être que cela va t'aider "mais avec un gros doute"
j'ai réussi à le faire marcher , j'ai mis in range (1) au lieu de 8 pour qu'il ne crible que la première famille Dico={1:0.........}

voici ton programme tu peux voir ce que j'ai modifié pour qu'il fonctionne ..


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

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(1):
        nombres.append([1]*nbcell)
    Pfam,P8=[],[1, 7, 11, 13, 17, 19, 23, 29]
    Dico={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}   #j'ai remis comme avant
    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):
        Pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
        r=nn%pi
        debut,fin,pas=r+pi*(1-r%2),1+r+pi*29,pi*2
        for j in range(debut,fin,pas):
            Pf=Pfam[i]
            if j%3!=0 and j%5!=0:
                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
    s23=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+s23+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 : "))           #j'ai remis comme avant
nbr,s= Crible_mod30(n)
print ("\n** ",nbr,"nombres trouvés en %s secondes" % s ,"**")
system("pause")
 

j'ai modifié la partie centrale après Pfam = j


voila pour l'instant...

Dernière modification par LEG (13-06-2018 16:08:05)

Hors ligne

#247 09-06-2018 11:41:18

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

Re : crible en python

<il se peut que l'on ne puisse pas faire grand chose car :
on est obligé de passer par:

fam =Dico[j%30]

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

pour mettre les index de j dans leur famille respective, qui est donné par Dico={...}
or le fait de refaire la division pour calculer l'index, ne changera rien...

Je pense que la seule possibilité serait de traiter le début d'index dans fam=Dico[j%30] en récupérant le quotient q...
ce qui permet de traiter au fur et à mesure et de ne pas stoker les Pfam....on ne fait qu'une division....

voili voila
@+

Hors ligne

#248 09-06-2018 13:37:55

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : crible en python

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à.
On ne peut donc avoir de doublons au sein d'une même famille, mais 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 ?

Si on pouvait éliminer ces doublons, on pourrait pour un nombre avoir, "à la volée" les infos :
pas traité, famille, indices.
Là, je pense qu'avec bloc 2+bloc 3 on pourrait faire du 2 en 1...

J'y réfléchis...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#249 09-06-2018 14:58:32

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

Re : crible en python

Tu peux avoir des doublons au sein d'une même famille, la différence c'est que ce n'est pas avec le même Pi, sinon le crible serait faux et tu ne peux pas les supprimer ou y échapper. sinon les autres Pi ayant le même j ne pourront pas cribler...!

lorsque tu cribles avec Eratosthène , tu repasses bien sur des nombres qui ont été déjà marqués par des Pi inférieur , comment tu ferais pour les sauter ...?
Là c'est identique à Eratosthène si ce n'est que c'est dans les congruences, donc cela te fais voir des J identiques= doublons dans une même famille ou dans une autre....

si tu criblais par tranche de n = 15k, tu verrais le phénomène plus simplement  chaque j augmente de 30 tu peux même prévoir les j'+30, pour n = 15(k+1)..mais cela n'apporte rien, si ce n'est une meilleur compréhension ou vision de la répartition des nombres premiers..

par contre le programme que j'ai mis au dessus il va bien et un peu plus loin que G9Y.

pour info

==== RESTART: E:\Documents\conjecture de Goldbach\cribleG1_par Famille.py ====
Donnez la valeur de n = 30k : 29400000000
Phase d'initialisation: 3.962406873703003 seconds ---
Famille de chaque Pi: : 346.89780926704407 secondes ---
Extraction des premiers n à 2*n : 7.6908135414123535 seconds ---

**  150069716 nombres trouvés en 358.5510296821594 secondes **
>>>
==== RESTART: E:\Documents\conjecture de Goldbach\cribleG1_par Famille.py ====
Donnez la valeur de n = 30k : 29550000000
Phase d'initialisation: 4.336807489395142 seconds ---
Famille de chaque Pi: : 349.64341402053833 secondes ---
Extraction des premiers n à 2*n : 7.924814224243164 seconds ---

**  150803440 nombres trouvés en 361.90503573417664 secondes **
>>>
==== RESTART: E:\Documents\conjecture de Goldbach\cribleG1_par Famille.py ====
Donnez la valeur de n = 30k : 29700000000
Phase d'initialisation: 3.697206735610962 seconds ---
Famille de chaque Pi: : 591.4126389026642 secondes ---
Extraction des premiers n à 2*n : 19.71843433380127 seconds ---

**  151537305 nombres trouvés en 614.8282799720764 secondes **

A partir de 29 400 000 000 il commence à traîner en dessous par tranche de 300 000 000 il met 145 secondes de 2" en 2"...

Dernière modification par LEG (13-06-2018 16:11:59)

Hors ligne

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

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

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 , va nous donner l'index qui est le quotient, ainsi que le reste correspondant à la famille p8=7 .

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 (18-07-2018 07:06:54)

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 (donner le résultat en chiffres)?
quatre-vingt dix-neuf plus soixante six
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