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

#201 08-05-2018 19:06:41

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

Re : crible en python

Re,

Et comme tu m'as fait une Blague en remplaçant la colonne n°2 par des 3m

Quelle blague ? Où ça ?
Je n'ai utilisé que des sorties de mon dernier programme...

@+


Arx Tarpeia Capitoli proxima...

En ligne

#202 08-05-2018 19:46:59

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

Re : crible en python

c'est vrai..?, car :
la deuxième colonne sont des 3m ; et il manque la colonne = famille 17modulo 30, Dico= {17:5} , colonne 2 à supprimer ...

[241, 243, 247, 251, 253, 259, 263, 269],
[271, 273, 277, 281, 283, 289, 293, 299],
[301, 303, 307, 311, 313, 319, 323, 329],
[331, 333, 337, 341, 343, 349, 353, 359],
[361, 363, 367, 371, 373, 379, 383, 389],
[391, 393, 397, 401, 403, 409, 413, 419],
[421, 423, 427, 431, 433, 439, 443, 449],
[451, 453, 457, 461, 463, 469, 473, 479]

Si tu fais un masque, la première ligne doit être indicé, afin de bien te poser sur les tableau à partir de la même ligne , c'est donc le premier [0] de la première (ligne ou colonne : sens du criblage) , qui donne (l'indice le rang) de la première ligne.des 8 familles
Par Exemple : si la première cellule [0] à été indexé (3) = 109, colonne dans Dico = {19:5} tu poses ton masque sur la ligne ("sens du criblage ligne ou colonne) d'indice 3

tu les appelles sous liste.. ce ne sont pas des masque ok

[151, 67, 11, 193, 137, 109, 53, 179],.ce sont les cell[0] et leur N° de ligne :[0:5,0:2,0:0,0:6,0:4,0:3,0:1,0:5]
[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]


......................................................................................................................
tableau de 8 lignes:[p8]
            [1,7,11,13, 17,19, 23,29]
colonne n°  0, 1 ,2, 3, 4, 5, 6, 7  .....etc......> vers (nbcell = n/30)
........(1). .[1, 1, 1, 1, 1, 0, 0, 1],
........(7). .[0, 1, 0, 1, 1, 0, 1, 1],
........(11) .[0, 1, 1, 1, 1, 0, 0, 0],
....... (13). [1, 0, 0, 0, 1, 1, 0, 1],
....... (17)..[1, 1, 0, 1, 0, 1, 1, 0],
........(19). [1, 1, 1, 0, 0, 1, 1, 1],
........(23). [1, 0, 1, 1, 1, 1, 1, 0],
.......(29). .[0, 1, 0, 0, 1, 0, 1, 1],

Une remarque : tu ne peux pas utiliser un tableau avec les entiers de n à 2n.....! car il faut inverser les familles complémentaires, du fait des congruences ; si un entier A est congru B [Pi]; Pi divise la différence B - A, si A=1, B=30 alors B - A = 29....etc..

passe une bonne soirée @+

Dernière modification par LEG (09-05-2018 08:50:32)

Hors ligne

#203 09-05-2018 08:34:43

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

Re : crible en python

yoshi a écrit :

Re,

Et comme tu m'as fait une Blague en remplaçant la colonne n°2 par des 3m

Quelle blague ? Où ça ?
Je n'ai utilisé que des sorties de mon dernier programme...

@+

c'est par ce que tu t'es trompé dans P8[ 1, (3),7,11,13, [17],19,23,29]

Tu as mis la famille des 3m en 2ème et tu as oublié, la famille ,17, en 4ème...

Une précision, il y a uniquement une liste des 8 familles. Et : ce que tu appels 5 sous listes sont les pfam [J] qui ont uniquement 8J si n > 960, car tu auras les 8 Pi <= sqrt de 2n..
Si il n'y a que 5 premiers Pi, il y aura 5 pfam; si il y a 1000 Pi;  il y en aura 1000...ok...

Hors ligne

#204 09-05-2018 09:39:16

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

Re : crible en python

Bonjour,

Nan, nan pas d'erreurs...
le premier tableau des candidats que je t'ai présenté a été composé ainsi :
J'ai passé en revue tous les nombres de 240 à 480.
parmi eux, j'ai retenu les candidats, c'est à dire tout nombre nb tel que

A,C,cpt=[],[],0
for nb in range(240,480):
    for r in [1,7,11,13,17,19,23,29]:
        if nb%30==r:
            A.append(nb)
            cpt+=1
            if cpt==8:
                C.append(A)
                A,cpt=[],0

print (C)

Puis j'ai fait quelques tests (de tête) sur C pour savoir si un 0 de la liste nombres, correspondait à un nombre non premier de la liste C...
Pas concluant...
Alors j'ai créé un deuxième tableau à partir de C, de cette façon :

D=list(zip(C[0],C[1],C[2],C[3],C[4],C[5],C[6],C[7]))
print(D)

La fonction zip m'a permis de grouper les 8 30 k+1, les 8 30k+7, les 8 30k+11...etc.
Mêmes tests, pas concluants...
Tu peux vérifier que mes dires sont exacts, et avoir les deux sorties en m^me temps via :

A,C,cpt=[],[],0
for nb in range(240,480):
    for r in [1,7,11,13,17,19,23,29]:
        if nb%30==r:
            A.append(nb)
            cpt+=1
            if cpt==8:
                C.append(A)
                A,cpt=[],0
print(C)
D=list(zip(C[0],C[1],C[2],C[3],C[4],C[5],C[6],C[7]))
print()
print(D)
 

Aurais-je mal écrit le code hier ?
Sortie :

[[241, 247, 251, 253, 257, 259, 263, 269], [271, 277, 281, 283, 287, 289, 293, 299], [301, 307, 311, 313, 317, 319, 323, 329], [331, 337, 341, 343, 347, 349, 353, 359], [361, 367, 371, 373, 377, 379, 383, 389], [391, 397, 401, 403, 407, 409, 413, 419], [421, 427, 431, 433, 437, 439, 443, 449], [451, 457, 461, 463, 467, 469, 473, 479]]

[(241, 271, 301, 331, 361, 391, 421, 451), (247, 277, 307, 337, 367, 397, 427, 457), (251, 281, 311, 341, 371, 401, 431, 461), (253, 283, 313, 343, 373, 403, 433, 463), (257, 287, 317, 347, 377, 407, 437, 467), (259, 289, 319, 349, 379, 409, 439, 469), (263, 293, 323, 353, 383, 413, 443, 473), (269, 299, 329, 359, 389, 419, 449, 479)]

Pourquoi ai-je posé cette question ?
Parce que j'ai pensé que, peut-être, si je savais ça je comprendrais mieux le pourquoi du fonctionnement du programme, mes questions que tu m'as posées et je pourrais - peut-être (encore !) - y répondre...
Donc, la liste sur laquelle appliquée le Masque nombres, ,'est aucune des deux proposées... Dommage.

N-B : la fonction zip ne fabrique pas des listes, mais des n-uplets :
couples, triplets... Ici des octuplets. Pour ne pas introduire "un bruit de fond", dans mon post, j'avais remplacé les parenthèses par des crochets.
C'est tout...
Donc pas d'erreur, d'oubli ou je ne sais quoi :
je cherchais simplement à comprendre  :
1. Si la liste nombres pouvait être considérée comme un masque : 1--> nb premier, 0 ( ça, c'était plus que probable, puisqu'en comportant tous les 1, j'obtiens le nombre de nombres premiers..
2. A quelle liste de nombres et rangés dans quel ordre, je devais appliquer le masque, pour obtenir la liste des premiers et non lus leur nombre...

Tu me parles de 3m, de 5m... Qu'est-ce que tu appelles 3m, 5 m... ?

@+

[EDIT] Quand tu évoquais Bertrand, c'est à ceci que tu fais allusion : (conjecture de ) "entre un nombre et son double il y a toujours au moins un nombre premier"

Dernière modification par yoshi (09-05-2018 10:38:56)


Arx Tarpeia Capitoli proxima...

En ligne

#205 09-05-2018 11:31:37

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

Re : crible en python

[yoshi]Bonjour, 

Aurais-je mal écrit le code hier ? surement..la position des tableau qui est mal interprété il est où ton masque que tu veux coller...?...est il bien orienté...?

Sortie :..............................[sortie cribleG8Y , des 30k+[P8] de 7 à 240
................................................>masque ..........>............> tout est à l'envers...

.[(1), (1), (1), (1), (1),(0),(0),(1)] ........>[451, 457, 461, 463, 467, 469, 473, [479]]
.[0, 1, 0, 1, 1, 0, 1, 1].....> .............................[421, 427,431, 433, 437, 439, 443.[449],.
[0,1, 1, 1, 1, 0, 0, 0].....>  ..........................  [391, 397, 401, 403, 407, 409, 413,[419]                                                         
[1, 0, 0, 0, 1, 1, 0, 1]......> ............................[361, 367, 371, 373, 377, 379, 383,[389]
[1, 1, 0, 1, 0, 1, 1, 0], ....> ............................ [331, 337, 341, 343, 347, 349, 353, [359],.
..[1, 1, 1, 0, 0, 1, 1, 1],....> ............................  [301, 307, 311, 313, 317, 319, 323, [(329)]
..[1, 0, 1, 1, 1, 1, 1, 0]......>.............................  [271, 277, 281, 283, 287, 289, 293, [(299)]
.[0, 1, 0, 0, 1, 0, 1, 1]].....> .............................. [241, 247, 251, 253, 257, 259,263,   [269]

effectivement si on met dans la bonne orientation ligne 1 et colonne 8 bien alignée et dans l'autre sens il se peut fortement que ton programme soit juste.....! je travail dans excel avec des couleurs pour me réorienté...car Galère....

compare ton masque avec celui des  decribleG8Y dans le bon ordre d'orientation..et compare comme suit:
première ligne du masque de gauche à droite avec dernière colonne de Haut en Bas ce qui donne réaligné:
    1. ....31....61... ..91......121....151...181....211
.[(1), .  (1), ..(1),... (1),... (1), ....(0), ..(0),...(1)]  .
[479]] .[449],[419] [389]..[359]..[329] .[299..[269]

C'EST SUPER CHI...

Tu me parles de 3m, de 5m... Qu'est-ce que tu appelles 3m, 5 m... ?

multiple de 3, multiple de 5
comment peux tu avoir dans un tableau de 30k +[P8], une colonne de 3m en deuxième position,???



. Si la liste nombres pouvait être considérée comme un masque : 1--> nb premier, 0 ( ça, c'était plus que probable, puisqu'en comportant tous les 1, j'obtiens le nombre de nombres premiers..
2. A quelle liste de nombres et rangés dans quel ordre, je devais appliquer le masque, pour obtenir la liste des premiers et non lus leur nombre...

regarde la réorientation de ta sortie avec l'exemple ci dessus afin de vérifier...

mais ton masque ...
@+

Dernière modification par LEG (09-05-2018 11:47:49)

Hors ligne

#206 09-05-2018 12:15:04

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

Re : crible en python

Ren

La sortie finale ci-dessous de la liste nombres peut-elle être considérée comme un masque ?
nombres = :
[
[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]
]

Oui, à condition de torturer une de mes deux  listes de candidats ?
Listes de candidats recréées ce matin :

[[241, 247, 251, 253, 257, 259, 263, 269], [271, 277, 281, 283, 287, 289, 293, 299], [301, 307, 311, 313, 317, 319, 323, 329], [331, 337, 341, 343, 347, 349, 353, 359], [361, 367, 371, 373, 377, 379, 383, 389], [391, 397, 401, 403, 407, 409, 413, 419], [421, 427, 431, 433, 437, 439, 443, 449], [451, 457, 461, 463, 467, 469, 473, 479]]

[(241, 271, 301, 331, 361, 391, 421, 451), (247, 277, 307, 337, 367, 397, 427, 457), (251, 281, 311, 341, 371, 401, 431, 461), (253, 283, 313, 343, 373, 403, 433, 463), (257, 287, 317, 347, 377, 407, 437, 467), (259, 289, 319, 349, 379, 409, 439, 469), (263, 293, 323, 353, 383, 413, 443, 473), (269, 299, 329, 359, 389, 419, 449, 479)]

aucun multiple de 3 n'est présent.
Par contre, c'est vrai, ça m'avait échappé, post #202, en 2e position figure un multiple de 3... Diantre !!!

@+


Arx Tarpeia Capitoli proxima...

En ligne

#207 09-05-2018 12:24:15

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

Re : crible en python

le premier tableau des candidats que je t'ai présenté a été composé ainsi :
J'ai passé en revue tous les nombres de 240 à 480.

,
il ne peut y avoir dans un tableau : des candidats qui sont des multiples de 3...§ car il te faudrait des multiples de 3..de 7 à 240..IMPOSSIBLE...!30k + P8 , n'en a pas...! sinon on ne travaille plus dans les 8 familles de nombres premiers >5

un multiple de trois ne peut rient te donner dans ces 8 familles , où le crible travaille uniquement dans les congruents à 2n modulo Pi, par définition 3 divise 30k et donc il ne peut pas avoir un complémentaire de 240 à 480 qui serait multiple de 3...c'est pour cela qu'ils sont éliminés d'office...! comme les 2m et 5m..

Hors ligne

#208 09-05-2018 13:05:26

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

Re : crible en python

yoshi a écrit :

Ren

La sortie finale ci-dessous de la liste nombres peut-elle être considérée comme un masque ?
nombres = :

Pas du tout
. la taille d'un masque va varier avec N , il dépend de Pi, du premier index = j == (30k +P8):(" j'en prend un petit celui de la première ligne :[1, 1, 1, 1, 1, 0, 0, 1], famille P8= 30k +1 et Pi = 7

a) ne peut comporter que 8 [0] par Pi, et un seul par famille= colonne. il s'établit dans l'ordre du programme , c'est à dire dans l'ordre des [j]
, puisque l'on va réitérer c'est à dire copié collé, pour chacun des Pi lignes, jusqu'à lalimite n/30 = nombre de ligne sur 8 colonne...
b) 1 ne peut figurer il est remplacé par 31 afin que le masque soit symétrique...
c) on prend le premiers index=j de chaque famille pour Pi

Tes [j] = [0] ==  [7,11,43,77,109,53,29] sous réserve que ton tableau corresponde au crible, n=240; Pi = ? et R =?

les 8 J, dans l'ordre d'apparition tel que R ? + Pi............................8ème J =(30k+P8)

(1).(7).(11) .(13).[17).(19).(23).(29)
....................................................
[*   0    0    *   *   *   *   0  ]
[*
[*
[*
[*
[0
[*
[*......................................]
pour l'instant:
..........................................................



[
[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]

exemple d'un masque avec Pi=7 , le dernier 0 sous 23 est ,7ligne en dessous, il permet de se dupliquer à partir de cette ligne mod 7
la première colonne est 30k+7 , la dernière est 30k +1 mais en commençant à 31

,    ,    ,    ,    ,    0    ,    ,
0    ,    ,    ,    ,    ,    ,    ,
,    ,    ,    ,    0    ,    ,    ,
,    ,    ,    0    ,    ,    ,    0
,    ,    ,    ,    ,    ,    0    ,
,    ,    0    ,    ,    ,    ,    ,
,    0    ,    ,    ,    ,    ,    ,
,    ,    ,    ,    ,    0    ,    ,


en suite je te montre :  donne moi n =  x  Pi =  Y   et R = Z

Mais je pense, que tu as peut être intérêt à modifier juste la ligne du programme phase 2 (famille Pi):fam =Dico[j%30]

pour supprimer: pHase 3 criblage :index = int((pfam['i][j] - p8[j]) / 30) ..

Dernière modification par LEG (09-05-2018 13:22:32)

Hors ligne

#209 09-05-2018 13:53:33

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

Re : crible en python

Re,

il ne peut y avoir dans un tableau : des candidats qui sont des multiples de 3...§ car il te faudrait des multiples de 3..de 7 à 240..IMPOSSIBLE...!30k + P8 , n'en a pas...! sinon on ne travaille plus dans les 8 familles de nombres premiers >5

Cré bon sang !!!
1. Citation compète :

le premier tableau des candidats que je t'ai présenté a été composé ainsi :
J'ai passé en revue tous les nombres de 240 à 480.
parmi eux, j'ai retenu les candidats, c'est à dire tout nombre nb tel que

A,C,cpt=[],[],0
for nb in range(240,480):
    for r in [1,7,11,13,17,19,23,29]:
        if nb%30==r:
            A.append(nb)
            cpt+=1
            if cpt==8:
                C.append(A)
                A,cpt=[],0

print (C)

Paraphrase de ce que j'ai fait :
Je passe en revue chacun nombres entre 240 et 480
    Pour chacun des nombres, je passe en revue chacun des r de [1,7,11,13,17,19,23,29]
         Là je teste si ledit nombre est congru à r modulo 30, c'est la ligne : if nb%30 == r:
             si oui je stocke dans A, j'augmente mon compteur de 1
              |   si mon compteur vaut 8
              |    |   je stocke A dans C, je remets le compreur à 0 et je vide A
              |   sinon
              |    |  on poursuit   
             sinon
                 on passe au reste suivant que des nombres du type 30k+r avec r dans [1,7,11,13,17,19,23,29]
2. Il est donc évident que le code ci-dessus ne peut fournir que des nombres du type 30k+r avec r dans P8...
    N'as-tu pas testé ?
    Alors pourquoi me seriner il ne peut y avoir dans un tableau : des candidats qui sont des multiples de 3..
    Tu pense que je ne sais pas ?
    A mon tour :
    30k+1 : aucune factorisation évidente
    30k+2 = 2(15k+1) pair. Refusé.
    30k+3 =3(10k+1) multiple de 3. Refusé
    30k+4 : 2(15k+2) pair. Refusé.
    30k+5 : 5(6k+1) multiple de 5. Refusé.
    30k+6 : 6(6k+1) multiple de 6. Refusé.
    30k+7 : aucune factorisation évidente
........................................
    30k +27 = 3(10k+9) multiple de 3. Refusé
    30k+28 =  2(15k+14) pair. Refusé.
    30k+29 aucune factorisation évidente

Voilà pourquoi je sais que les seuls nombres qui seront premiers seront de la forme
30k+r avec r dans  [1,7,11,13,17,19,23,29]
(Agaçant, hein...)

Mais, je m'aperçois qu'il faut cette condition supplémentaire : que k%r [tex]\neq[/tex] 0 et (et [tex]r\neq 1[/tex]) !
Ça m'avait échappé !

Par exemple :
si k %7 =0, alors il existe k' tel que k=7k'  et 30k+7= 30*7*k'+7 = 7(30k'+1) multiple de 7 refusé...
C'est cette dernière condition que par contre j'ai oublié parmi mes candidats.
Je refais donc mon script

A=[]
for k in range(8,16):
    for q in [2,3,5,7]:
        if k%q==0 or k in [11,13]:
            break
    for r in [1,7,11,13,17,19,23,29]:
        nb=30*k+r
        if nb%30==r:
            A.append(nb)
           
print("A =",A

Du coup voilà mes candidats à la primature entre (240 et 480)...
A = [241, 247, 251, 253, 257, 259, 263, 269, 271, 277, 281, 283, 287, 289, 293, 299, 301, 307, 311, 313, 317, 319, 323, 329, 331, 337, 341, 343, 347, 349, 353, 359, 361, 367, 371, 373, 377, 379, 383, 389, 391, 397, 401, 403, 407, 409, 413, 419, 421, 427, 431, 433, 437, 439, 443, 449, 451, 457, 461, 463, 467, 469, 473, 479]

Je vérifierai tout à l'heure si ce sont les mêmes : là, ça gronde au dessus de ma tête, je vais tout débrancher...

@+


Arx Tarpeia Capitoli proxima...

En ligne

#210 09-05-2018 14:24:29

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

Re : crible en python

Cré bon sang !!!
1. Citation compète :
: Non attends, on est OK.
Mais l'autre soir dans le premier tableau il y avait la deuxième colonne :
[241, 243, 247, 251, 253, 259, 263, 269],
[271, 273, 277, 281, 283, 289, 293, 299],
[301, 303, 307, 311, 313, 319, 323, 329],
[331, 333, 337, 341, 343, 349, 353, 359],
[361, 363, 367, 371, 373, 379, 383, 389],
[391, 393, 397, 401, 403, 409, 413, 419],
[421, 423, 427, 431, 433, 439, 443, 449],
[451, 453, 457, 461, 463, 469, 473, 479] et je pensais que tu m'avais fait une blague....

je vérifie :

Du coup voilà mes candidats à la primature entre (240 et 480)...
A = [241, 247, 251, 253, 257, 259, 263, 269, 271, 277, 281, 283, 287, 289, 293, 299, 301, 307, 311, 313, 317, 319, 323, 329, 331, 337, 341, 343, 347, 349, 353, 359, 361, 367, 371, 373, 377, 379, 383, 389, 391, 397, 401, 403, 407, 409, 413, 419, 421, 427, 431, 433, 437, 439, 443, 449, 451, 457, 461, 463, 467, 469, 473, 479]

P8 = 29, dans le sens inverse:

[479]; 449 ;419 ; 389 ; 359: 329 ;299 ;  269 ]

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

le crible : donne donc 329 et 299 non premier...!

je me suis enfermé à la cave....LoLLLLL...

Dernière modification par LEG (09-05-2018 14:25:36)

Hors ligne

#211 09-05-2018 14:54:10

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

Re : crible en python

voila avec un petite crible : pour N =150 ....qui va éclaircir

B_)                                   
crible_mod30 :  N = 150; Pi ≤ sqrt 2N ; Pi = 7,11,13,17. R = 6,3,1,11                                   
N = 30k , on part du reste R º p8[30] une fois défini les 8 Ri de départ.       

On détermine les Ri = j appartenant à p8, pour chaque Pi et on crible; ensuite on réitère avec le Pi suivant:...>limite 150/30 = 5
                                                   
6 + 7   = 13 ; +14 ; 27 +14 = 41 + 14; 55+14 ; 69 +14 = 83 +14 = 97 +14 ; 111; +14 ;125 ;+14 =139 +14  >150 fin.                                                       
3 + 2*11 =25; +22 = 47 ; +22 ;69 + 22= 91 + 22 = 113 +22 ; 135 +22 . > à  150Fin                                                       
1 + 2*13 = 27 +26 = 53 +26 = 79 +26; 105 +26 = 131 ; +26 > 150.fin                                                       
11 + 2*17 = 45; +34 = 79; +34 = 113 ; +34 =147 +22...>150fin                                                       
                           
                                   
    A cribler    : serront marqués [0] les nombres en gras
                           
1    7    11    13    17    19    23    29       
31    37    41    43    47    49    53    59       
61    67    71    73    77    79    83    89       
91    97    101    103    107    109    113    119       
121    127    131    133    137    139    143    149   

    candidat à la primature

151    157    161    163    167    169    173    179       
181    187   191    193    197    199    203    209       
211    217    221    223    227    229    233    239       
241    247    251    253    257    259    263    269       
271    277    281    283    287    289    293    299       

donc ne sont pas premiers les candidats en gras

Hors ligne

#212 09-05-2018 14:55:07

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

Re : crible en python

Re,

Ayé, l'orage est passé à côté...
Une recherche google m'a permis de tomber sur des sujets traitant de cribles de nombres premiers, j'ai trouvé l'expression "algorithme P[30]", mais rien qui en dis plus...
J'ai aussi pu constater que sur l'Ile Maths, ils ne sont pas très portés sur Python et qu'ils n'ont pas fait grand chose pour... toi !

Oui, j'ai constaté qu'effectivement les listes postées l'autre soir étaient fausses : n'ayant pas gardé mes scrpits, je ne sais pas ce que j'ai fait, sinon, tu as probablement raison, avoir utilisé 3 et oublié 17 pour les b de 30k+b...

Ce sont des choses qui m'arrivent de temps en temps lorsque je suis en excès de vitesse...

T'es peut-être pas enfermé...
Il faut encore vérifier bien qu'il y ait toujours 64 nombres si je peux les répartir par sous listes de 8,
chaque sous-liste regroupant les nombres de restes P8...

Je vais d'abord modérer le forum...

@+


Arx Tarpeia Capitoli proxima...

En ligne

#213 09-05-2018 16:56:03

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

Re : crible en python

re
suite à tes explications hier sur le déroulement de la phase 2 famille de Pi :
et sur tes explications que je t'avais demandé ,avant hier sur le déroulement de la phase 3, criblage :

j'ai regroupé: les deux parties du programme qui devrait en faire qu'une à mon avis et il faut d'abord corriger cette histoire de double limite afin que j soit <= f mais aussi <= n.
ce que je vais essayer de faire demain matin
Ce que je n'ai pas réussi à faire à cause de l'appel de pfam[0,0,0,0,0,0,0,0,] qui doit être indexé complètement...Donc comment ?
***********************************
donc : dans ce processus ci-dessous:
A-t-on j%3==0 ou j%5==0 ?
   Non.
   | Donc fam =Dico[j%30]=Dico[11%30]=Dico[11] , (OK ..et le quotient pourquoi ne pas l'utiliser..?)
, soit fam=2. Et puisque Pf[2] (c'est à dire Pfam[0][2]) ==0,  à la place du 0, on écrit 11 :  Alors que l'on aurait dû cribler , en partant de  (0):2 qui serra le rang , l'index de  de la famille 11:2..à cet étape ..Non...?
suite:
(Et là on teste le nouveau  j)
   A-t-on j%3==0 ou j%5==0 ?
   Oui. On passe directement au j suivant : j = 25+14 = 39
   (Et là on teste ce nouveau  j)
   A-t-on j%3==0 ou j%5==0 ?
   Oui. On passe directement au j suivant : j = 39+14 = 53
   (Et là on teste ce nouveau  j)
   A-t-on j%3==0 ou j%5==0 ?
non:
Donc fam =Dico[j%30]=Dico[53%30]=Dico[23] , soit fam=6., est le quotient = (1)..? Pourquoi ne pas aller cribler directement au lieu d'indexer Pf=[
Ok 
Et puisque Pf[6] (c'est à dire Pfam[0][6]) ==0,  à la place du 0, on écrit 53 alors que on aurait dû écrire (1):6 et cribler la famille 23:6 à partir de l'index = le rang .
On a alors Pf=[0, 0, (11), 0, 0, 0, (53), 0]  au lieu de et automatiquement Pfam=[[0, 0, (0), 0, 0, 0, (1),0]] ...
Ce qui fait Bien éviter le processus : dans le criblage :
for j in range(8):
            debut_index=(Pf[j] - P8[j])//30
            Nombres_j=nombres[j]
suite :
[ etc.."Le dernier j à être testé (quand i == 0) sera j=193..."] Tout à fait...
Quand on a testé tous les j possible <= f == pi*29 donc <= f == 7*29 , on sort de la boucle et  prend la valeur 1.
Pfam devient [[151, 67, 11, 193, 137, 109, 53, 179], Au lieu de [(5),(2),(0), (6), (4), (3), (1), (5)]

........................D'OÛ:......on supprime .... index = int((pfam['i][j] - p8[j]) / 30)          .....

for i in range(lenpfam):…………………..> qui doit être [(5),(2),(0), (6), (4), (3), (1),(5)
        for j in range(8):
            index = int((pfam['i][j] - p8[j]) / 30)           
            while index < nbcell:
                nombres[j][index] = 0
                index += p['i]

de sorte que cette partie soit modifiée et / ou directement en phase S2 à la suite du point (5)]
ci-dessus

*************************
Tu ne devrait avoir que  le résultat des 5 pfam qui donne directement les index ci dessous  == [(5),(2),(0), (6), (4), (3), (1)(5)

Donc : tu n'aurais pas besoin de recalculer la position de ses index, dans le processus ci-dessous, et passer directement au criblage par pas de 7

le premier index est (5) :P8 I 0], pour chaque index de 5 à 8, par pas de 7, suivant ; (2) : P8 I 1],  de 2 à 8par pas de 7..> suivant de 0 à 8 par pas de 7……..etc…etc le dernier (1) :P8 I 7]  de 1 à 8 par pas de 7 …fin de cette série.. On passe au Pi suivant

*************
avec Pi=11

Pour chacun des Pf d'indice i de 0 à 4
     Exemple le Pf n° i = 1 qui est : [271, 7, 161, 73, 227, 139, 293, 29] ; relatif à Pi = 11, donc dans la limite de n = 240,
le premier index = 0:271 étant > 240 il ne devrait pas y être, ni 6:293
             
         Pour chaque élément  repéré par son indice  j de 0  à 7
              on calcule le début des indices : debut_index
              Exemple avec j=0 : Pf[0] c'est Pfam[1][0] qui vaut 271 .......> à n == 240 il faut corriger cette erreur de limite
              ici debut_index= (271- 11)//30 = 9    (Le 1 c'est P8|0])
              Pour chaque index de 9  à  8 par pas de 7
                   on passe immédiatement au debut_index suivant correspondant à j=1 parce que 9>8
              j=1 --> Pfam[1][1] vaut 7
              debut_index = (7-7)/30 = 0  (le 2e 7 c'est P8[1])
              Pour index de 0 à 8 (8, c'est nbcell) par pas de pi=11 (ici p[1] ou Primes_init[1]=11)
                     index = 0
                     nombres[1][0] =0
Vérification : [0, 1, 0, 1, 1, 0, 1, 1],  ---------->  nombres[1]
Le 1 en position [1][0] dans la liste nombres initiale est changé en 0.

Est ce qu'alors, ton nouveau programme s'inspire de cela:

les 5 pfam final indexés dans la phase S2 Famille Pi pour Pi=7 : qui devrait être directement dans P8 :
P8 = [1 , 7 , 11 ,  13 , 17 , 19 , 23 , 29]
....[(5),(2),(0), (6), (4), (3), (1),(5) par pas de 7 pour chaque colonne=famille
.............................................................
..0)............(0)
..1).....................................(1)
..2)......(2)
..3)...............................(3)
..4).........................(4)
..5).(5).......................................(5)]
..6)..................(6)
..7)............(0)
lim nbcell = 8 ligne de 0) à 7)

Voila un exemple de masque pour Pi=7 qui se dupliquerait à partir de la ligne.. 7).......>7)......>7)......>7)
tu cribles les 8 familles d'un coup par pas de 7, mais c'est très compliqué à programmer , et franchement ....ce n'est pas sûr que l'on serait gagnant .
sur des tableaux 7000 à 10000 lignes dans un tableur, il réplique la macro..oui...Mais..
Là c'est inutile car le but est d'avoir un outil efficace , bien programmé Ce QUE TU AS FAIT, afin d'étudier le comportement de la répartition de nombres premiers, par famille..par rapport aux entiers de ces 8 familles ou d'une seule.. et sa fonction [tex] \frac{N}{Ln.2N}[/tex] , lorsque N tend vers + l'infini...etc. D'autant que tel quel, il prend N = 29 970 000 000. de quoi étudier.... pour N = 15k et 15(k+1)..>..> 30 mds.

Dernière modification par LEG (10-05-2018 04:44:42)

Hors ligne

#214 09-05-2018 18:42:20

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

Re : crible en python

je te joins ci dessous, les entiers > 240 qui sont premiers , pour tes testes . des 8 fam P8[7.11.13.17.19.23.29.31]
..............................................................]
0     0      223    227    229    233    239    241
0     251     0      257     0     263    269    271
277  281   283       0      0      293      0       0
307 311  313     317      0       0       0      331
337     0       0    347    349    353    359     0
367     0    373     0    379    383     389     0
397    401     0     0    409      0     419    421
0     431    433     0     439    443    449     0
457  461   463   467      0      0      479      0
..............................................................]
@+ bonne soirée

Hors ligne

#215 09-05-2018 19:33:39

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

Re : crible en python

Re,

Non, rien de neuf : pas de nouveau programme...
Demain, je vais essayer de digérer ce que tu as écrit pour pouvoir modifier le dernier qui tourne.
Si j'y arrive, on gagnera en vitesse...

@+


Arx Tarpeia Capitoli proxima...

En ligne

#216 09-05-2018 22:05:37

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

Re : crible en python

yoshi a écrit :

Re,

Non, rien de neuf : pas de nouveau programme...
Demain, je vais essayer de digérer ce que tu as écrit pour pouvoir modifier le dernier qui tourne.
Si j'y arrive, on gagnera en vitesse...et en mémoire
C'est clair , car on ne refait pas ce qui est faisable en phase S2, en utilisant directement le quotient....

@+

le plus dur c'était ce que tu as Fait..
Là, il faut compiler deux  phases en une, pour supprimer les calculs inutiles en phase 3 de cette ligne :
index = int((pfam['i][j] - p8[j]) / 30). donc modifier ce bloc..

Ou de cribler directement à partir du quotient et de la position de l'index de la ligne phase S2, suivant tes explication du processus:

r=4,pi=7
suite:
.
.
j = 11+14 = 25
(Et là on teste le nouveau  j)
   A-t-on j%3==0 ou j%5==0 ?
   Oui. On passe directement au j suivant : j = 25+14 = 39
   (Et là on teste ce nouveau  j)
   A-t-on j%3==0 ou j%5==0 ?
   Oui. On passe directement au j suivant : j = 39+14 = 53
   (Et là on teste ce nouveau  j)
   A-t-on j%3==0 ou j%5==0 ?
non:
Donc fam =Dico[j%30]=Dico[53%30]=Dico[23] , soit fam=6., quotient = Dico[53//30]=1 ; soit index 1:6 dans fam23:6
le quotient = (1):6..? ,
Pour index de 0 à 8 (8, c'est nbcell) par pas de pi=7 (ici p[0] ou Primes_init[0]=7)
     index = 1 . . . . . . .> nbcell =8 : [0,1,,2,3,4,5,6,7)  on passe au j suivant....,
Pourquoi ne pas aller cribler directement au lieu de faire appel à Pf =[0,0,0,0,0,0,0,0] afin d'indexer Pf=[0,0,0,...] ??
cela éviterai ou règlerai ce problème de limite j <= f mais aussi <= n : que je n'ai pu résoudre, surement à cause de l'appel de Pf[0,0,0,0,0,0,0,0] ,... je suppose....

Pense d'abord à toi...
Mais j'aimerai quand même te remercier...envoies moi un mail...
@+ Gilbert

Dernière modification par LEG (10-05-2018 08:05:05)

Hors ligne

#217 10-05-2018 08:03:01

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

Re : crible en python

pour répondre au 2 posts ci -dessus, en espérant t'éviter à nouveau tes explications , suivant ces dernière j'ai répété ton processus,dans l'ordre en partant de R; afin de te montrer ce problème de dépassement de j >= n , et dans ton cas précis n=240
...................................
Tes explications du 7/5, post #194 ;  et 85
Désolé, je me suis absenté...
n=240
nbcell=240//30=8 (de 0 à 7)
Primes_init=[7, 11, 13, 17, 19]  récupérés grâce à l'appel à la def eratostene.
Pfam : (en gras les j > n=240 , il y en a 1/3
[
[151, 67, 11, 193, 137, 109, 53, 179],                --->Pf =   Pfam[0]  ;  pi=Primes_init[0] = 7
[271, 7, 161, 73, 227, 139, 932, 29],                  --->Pf =   Pfam[1]  ; pi=Primes_init[1]  =11
[181, 337, 311, 103, 77, 259, 233, 389],            --->Pf =   Pfam[2]  ; pi=Primes_init[0] = 13
[361, 157, 191, 463, 497, 259, 293, 89],             --->Pf =   Pfam[3]  ; pi=Primes_init[0] = 17
[271, 157, 461, 43, 347, 499, 233, 119]              --->Pf =   Pfam[4]  ; pi=Primes_init[0] =19
Suite…
***********************************************************************************
n=240,
Pi = [7,11,13,17,19] index de 0 à 4, et pfam de 0 à 4
j doit être au maximum <= f = pi*29 et et si j >= n break , on passe à Pi et R suivant;  tel que j <= n {ce que je n'ai pas réussi à faire ce matin car il y a une limites maxi pour les Pi petits  donc j <= f et si j >= n break , pour les Pi plus grands, tel que Pi*29 > n limite donc j >n l'instruction break , fait passer à Pi et R suivant; car ils cribleront  moins de 8 fam...

On peut peut-être procéder comme ci-dessous :

Exemple, suivant le processus de tes deux exemples entre phase s2 et phase s3: pour ne faire qu’un processus

On a déjà fait Pi[0] =7 , pfam[0]
………..
d’où en exemple, on passe à Pi[1] suivant = 11 ;  f = 11*29 = 319 > n… ? alors  on doit limiter dans pfam[1] la limite de j :

[«  ceci est ton ex pfam[1]: [271, 7, 161, 73, 227, 139, 293, 29],                  --->Pf =   Pfam[1]  ; pi=Primes_init[1]  =11
suivant le processus ci-dessous : »]

pi[1] =11, R(1) = 7

j=7
à t’on j%3==0 ou j%5 ==0
non
donc fam =Dico[j%30]=Dico[7%30]= Dico[7]est le quotient ==(0)
soit fam 1 et puisque Pf[21], (c'est à dire Pfam[0][1]) index(0)) on part cribler par pas de Pi[0] = 11 de (0) à 8 (nbcell = 8)et on passe à j suivant.

J =7+22= 29
à t’on j%3==0 ou j%5 ==0
non
donc fam =Dico[j%30]=Dico[29%30]= Dico[29]est le quotient ==(0)
soit fam 6 et puisque Pf[6], (c'est à dire Pfam[0][6]) index(0))on part cribler par pas de 11 de (0) à 8 (nbcell = 8)et on passe à j suivant.
J= 29+22 =51

à t’on j%3==0 ou j%5 ==0
oui : On passe directement au j suivant :: j = 51+22 = 73

à t’on j%3==0 ou j%5 ==0
non
donc fam =Dico[j%30]=Dico[73%30]= Dico[13]est le quotient ==(2)
soit fam  et puisque Pf[3], (c'est à dire Pfam[0][3]) index(2))on part cribler par pas de 11 de (0) à 8 (nbcell = 8) et on passe à j suivant.
J =73+22 = 95

à t’on j%3==0 ou j%5 ==0
oui ; On passe directement au j suivant :: j = 95+22 = 117

à t’on j%3==0 ou j%5 ==0
oui ; On passe directement au j suivant :: j = 117+22 = 139

à t’on j%3==0 ou j%5 ==0
non
donc fam =Dico[j%30]=Dico[139%30]= Dico[19]est le quotient ==(4)
soit fam  et puisque Pf[5], (c'est à dire Pfam[0][5]) index(4))on part cribler par pas de 11 de (0) à 8 (nbcell = 8) et on passe à j suivant.
J = 139 +22 = 161

à t’on j%3==0 ou j%5 ==0
non
donc fam =Dico[j%30]=Dico[161%30]= Dico[11]est le quotient ==(5)
soit fam  et puisque Pf[2], (c'est à dire Pfam[0][2]) index(5))on part cribler par pas de 11 de (0) à 8 (nbcell = 8) et on passe à j suivant.
J = 161 + 22 =183.

à t’on j%3==0 ou j%5 ==0
oui ; On passe directement au j suivant :: j = 183+22 = 205

à t’on j%3==0 ou j%5 ==0
oui ; On passe directement au j suivant :: j = 205+22 = 227

à t’on j%3==0 ou j%5 ==0
non
donc fam =Dico[j%30]=Dico[227%30]= Dico[17]est le quotient ==(7)
soit fam  et puisque Pf[4], (c'est à dire Pfam[0][4]) index(7))on part cribler par pas de 11 de (0) à 8 (nbcell = 8) et on passe à j suivant.

J = 227 +22 = 249 > n = 240 Break  Cela met fin au processus de pfam[1]; on passe Pi[2] et R[2] .... ;
le criblage des fam, serra dans l'ordre de [p8 = [1,6,3,5,2,4] ] sur 8......> pi suivant.

on passe à Pi [2] suivant et R[2] ; on réitère le processus. Jusqu’au dernier Pi[4] .

Les Pi étant de plus en plus grand, le processus serra de plus en plus court, de ce fait l’algorithme accélère … en phase de criblage final.

Mais cela nous évite de passer par cette étape :

for i in range(lenpfam) :
        for j in range(8):
            index = int((pfam['i][j] - p8[j]) / 30)           
            while index < nbcell:
                nombres[j][index] = 0
                index += p['i]
………………………………………….

Dernière modification par LEG (10-05-2018 09:28:46)

Hors ligne

#218 10-05-2018 12:16:37

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

Re : crible en python

Bonjour,

Je commence à regarder ce que tu as écrit...

j doit être au minimum <= f = pi*29 et au maximum <= n ;  tel que j <= n

Alors là, il faut simplifier :
si tu as :
[tex]\begin{cases}j\leqslant pi*29\\j\leqslant 240\end{cases}[/tex]
et si j'ai bien compris ce que tiu veux dire,il y a une des deux lignes inutiles ..
En  effet


pi           pi*29         n           2n
 1            29          240         480
 7           203          240         480
11           319          240         480
13           377          240         480
19           493          240         480

pour les deux premières lignes si j<=pi*29 cette condition prime sur l'autre : alors  j est automatiquement <=240
pour les autres, si j<= 240 alors cette condition prime sur l'autre : alors  j est automatiquement <=pi*29
Tout dépend de n et de pi...
On doit avoir, à partir de pi=7, [tex]j\leqslant \min(29*pi,n)[/tex]
Vérification :


 pi   29*pi    n     min(29*pi,n)
  1    29      30        29
  7   203      30        30
 11   319      30        30
 13   377      30        30
 17   493      30        30
 19   551      30        30
 23   667      30        30
 29   841      30        30

  1    29     120        29
  7   203     120       120
 11   319     120       120
 13   377     120       120
 17   493     120       120
 19   551     120       120
 23   667     120       120
 29   841     120       120

  1    29     210        29
  7   203     210       203
 11   319     210       210
 13   377     210       210
 17   493     210       210
 19   551     210       210
 23   667     210       210
 29   841     210       210

  1    29     300        29
  7   203     300       203
 11   319     300       300
 13   377     300       300
 17   493     300       300
 19   551     300       300
 23   667     300       300
 29   841     300       300

  1    29     390        29
  7   203     390       203
 11   319     390       319
 13   377     390       377
 17   493     390       390
 19   551     390       390
 23   667     390       390
 29   841     390       390

  1    29     480        29
  7   203     480       203
 11   319     480       319
 13   377     480       377
 17   493     480       480
 19   551     480       480
 23   667     480       480
 29   841     480       480

  1    29     570        29
  7   203     570       203
 11   319     570       319
 13   377     570       377
 17   493     570       493
 19   551     570       551
 23   667     570       570
 29   841     570       570

  1    29     660        29
  7   203     660       203
 11   319     660       319
 13   377     660       377
 17   493     660       493
 19   551     660       551
 23   667     660       660
 29   841     660       660

  1    29     750        29
  7   203     750       203
 11   319     750       319
 13   377     750       377
 17   493     750       493
 19   551     750       551
 23   667     750       667
 29   841     750       750

  1    29     840        29
  7   203     840       203
 11   319     840       319
 13   377     840       377
 17   493     840       493
 19   551     840       551
 23   667     840       667
 29   841     840       840

  1    29     930        29
  7   203     930       203
 11   319     930       319
 13   377     930       377
 17   493     930       493
 19   551     930       551
 23   667     930       667
 29   841     930       841

  1    29    1020        29
  7   203    1020       203
 11   319    1020       319
 13   377    1020       377
 17   493    1020       493
 19   551    1020       551
 23   667    1020       667
 29   841    1020       841

  1    29    1110        29
  7   203    1110       203
 11   319    1110       319
 13   377    1110       377
 17   493    1110       493
 19   551    1110       551
 23   667    1110       667
 29   841    1110       841

  1    29    1200        29
  7   203    1200       203
 11   319    1200       319
 13   377    1200       377
 17   493    1200       493
 19   551    1200       551
 23   667    1200       667
 29   841    1200       841

  1    29    1290        29
  7   203    1290       203
 11   319    1290       319
 13   377    1290       377
 17   493    1290       493
 19   551    1290       551
 23   667    1290       667
 29   841    1290       841

ou alors ce que tu as voulu écrire est plutôt :
[tex]29*pi\leqslant <\leqslant n[/tex] ?

Parce que ça, sinon :

j doit être au minimum <= f = pi*29 et au maximum <= n ;  tel que j <= n

, mathématiquement, je ne sais pas ce que ça veut dire : un minimum, c'est une valeur plancher, comment j peut-il être inférieur ou = à un minimum ?

n = 240,
le premier index = 0:271 étant > 240 il ne devrait pas y être, ni 6:293
(...)
P8 = [1 , 7 , 11 ,  13 , 17 , 19 , 23 , 29]
....[(5),(2),(0), (6), (4), (3), (1),(5) ]

Je ne comprends pas tes notations ;
- que veulent dire les "deux points" 0:271 et 6:293 ?
- 0 et 6 correspondent à quoi ? des valeurs de i du bloc ?
- (0), (6) : ce 0 et ce 6 sont obtenus de la même façon que ci-dessus ? Sinon; comment ? Pourquoi ces parenthèses ?

post#216 a écrit :

A-t-on j%3==0 ou j%5==0 ?
   Non.
   | Donc fam =Dico[j%30]=Dico[11%30]=Dico[11] , (OK ..et le quotient pourquoi ne pas l'utiliser..?)
, soit fam=2. Et puisque Pf[2] (c'est à dire Pfam[0][2]) ==0,  à la place du 0, on écrit 11 :  Alors que l'on aurait dû cribler , en partant de  (0):2 qui serra le rang , l'index de  de la famille 11:2..à cet étape ..Non...?

Utiliser le quotient
lequel ? celui-ci : j//30 ? Et tu en ferais quoi exactement ?
On abandonnerait j%30 et Dico[j%30] ?
Si on garde les deux, on peut les obtenir d'un coup :
q,reste=divmod(j,30) :

>>> q,reste=divmod(693,30)
>>> q
23
>>> reste
3
>>>

Un peu de synthèse.
Soient les deux blocs :

    # FAMILLES POUR CHAQUE Pi
    start_time = time()
    Debuts_i=[]
    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
            A.append(debut_index)
            Nombres_j=nombres[j]
            for index in range(debut_index, nbcell,pi):
                Nombres_j[index] = 0

Seul le 2e bloc "On crible les 8 colonnes" va être modifié ?
Là  ?


debut_index=(Pf[j]-P8[j])//30
            Nombres_j=nombres[j]
            for index in range(debut_index, nbcell,pi):
                Nombres_j[index] = 0

Essaie de m'expliquer de façon "ramassée" quelle est exactement ton idée.
Tu veux te passer de Pfam ?
Je t'ai déjà demandé 2 fois (si ce n'est 3) de me dire ce que représentent les nombres de Pfam, comment tu peux les qualifier...
J'ai vu que


Pfam =[
[151,  67,  11, 193, 137, 109, 53, 179]
  5    2     0    6    4    3   1    5          j//30
[271,  7, 161,  73, 227, 139, 293,  29]
  9    0     5   2    7    4    9    0
[181, 337, 311, 103,  77, 259, 233, 389]
  6    11   10    3    2    8    7   12
[361, 157, 191, 463, 497, 259, 293,  89]
 12    5     6   15   16    8    9    2
[271, 157, 461,  43, 347, 499, 233, 119]
    9   5   15    1   11   16    7    3
]

(C'est de là que viennent les (0) (6) vus plus haut ? j//30 ? Le j%30 =12 sera utilisé comment pour index ?)


il y  40 éléments dans Prefam, alors que nombres contient 64 éléments (des 1 et des 0)...
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.
Je peux modifier Pfam (une ligne) pour que les j %30 d'une même sous-liste, soient les mêmes, comme ça :
[
[151, 271, 181, 361, 271]
[67, 7, 337, 157, 157]
[193, 73, 103, 463, 43]
[137, 227, 77, 497, 347]
[109, 139, 259, 259, 499]
[53, 293, 233, 293, 233]
[179, 29, 389, 89, 119]
]
Au lieu d'avoir 5 sous-listes de 8, j'ai 8 sous-listes de 5 de restes dans la division par 30 : 1 7 11 13 17 19 23 29...
Je vois comment les fabriquer, les regrouper différemment, mais ça ne me dit pas qui ils sont, pourquoi il y en a 40, pourquoi dans nombres on passe à 64.
Je vois le détail de ces calculs, je peux les décrire (je l'ai déjà fait), mais ça ne me dit pas pourquoi...

J'ai encore aujourd'hui et demain...
Samedi c'est l'AG de mon Assoc, et à partir de lundi, je devrai m'occuper en priorité de notre revue (le n° de juin)...

@+


Arx Tarpeia Capitoli proxima...

En ligne

#219 10-05-2018 13:29:23

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

Re : crible en python

bonjour Yoshi
1)

j doit être au minimum <= f = pi*29 et au maximum <= n ;  tel que j <= n :

erreur de ma part j'ai rectifié ce matin..

2) j'ai repris le post d'hier que j'ai entièrement rectifié ce matin et que j'aurai dû supprimer  #post 220 juste au dessus de ta réponse..
c'est celui ci qu'il faut prendre en compte.

3) oui pour la suppression de append  pf=[0,0,0,0,0,0,0,0]
la raison est dans le processus du post #220 qui est en principe évidente suite aux explications que tu m'as donné hier et avant hier dans le processus des deux Phases..

4)

Je ne comprends pas tes notations ;
- que veulent dire les "deux points" 0:271 et 6:293 ?

ce sont tes notation que j'ai écris à l'envers par erreur dans Dico={271:0........293:6...} fam 1:0 et fam 23:6

5)

Utiliser le quotient
lequel ? celui-ci : j//30 ?....... 
On abandonnerait Dico[j%30] ? ...Non
Si on garde les deux, on peut les obtenir d'un coup : Excellente idée et en modiffiant
q,reste=divmod(j,30) :

ce bloc,  à la place de:  fam =Dico[j%30]  à fin d'avoir l'index , pour cribler directement à partir du rang de l'index, en modifiant les deux lignes qui suivent...par celle du criblage en phase S3 :
 

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

A.append(debut_index)
            Nombres_j=nombres[j]
            for index in range(debut_index, nbcell,pi):
                Nombres_j[index] = 0

Voila l'idée, et on se passerait de Pfam...Non ?....

6)

Essaie de m'expliquer de façon "ramassée" quelle est exactement ton idée.
Tu veux te passer de Pfam ?
Je t'ai déjà demandé 2 fois (si ce n'est 3) de me dire ce que représentent les nombres de Pfam, comment tu peux les qualifier...

depuis le début, on est dans les congruences je pensais que tu savais, que ces nombres dans pfam sont les nombres qui sont congrus à 2n modulo Pi

J'ai vu que:

Pfam =[
[151,  67,  11, 193, 137, 109, 53, 179]
  5    2     0    6    4    3   1    5          .......> j//30. que l'on peut remplacer  dans la phase S2, de par tes explications :
:donc fam =Dico[j%30]=Dico[7%30]= Dico[7]est le quotient ==(0)....Non..?

[271,  7, 161,  73, 227, 139, 293,  29]   ..............> :  480-271 = 209 non premier mais de 7 à n ?
  9    0     5   2    7    4    9    0
[181, 337, 311, 103,  77, 259, 233, 389]  .....> 480-337 =143 non prime de 7 à n..?, idem 480-311 , idem 480- 259..etc
  6    11   10    3    2    8    7   12
[361, 157, 191, 463, 497, 259, 293,  89]  ....>on criblerai à l'envers si dans pfam on prend des j > 240...!..en plus des non primes..
12    5     6   15   16    8    9    2
[271, 157, 461,  43, 347, 499, 233, 119] 
    9   5   15    1   11   16    7    3
]

(C'est de là que viennent les (0) (6) vus plus haut ?

Pas du tout..
tu as les j  de pfam les entiers congrs à 2n [Pi] et dessous  les index des j , qui déterminent le rang dans les colonnes = Familles ou l'indice des lignes, dans les colonnes ..comme tu veux..,

Exemple Pfam [0] l'entier j = 151 famille 1; partira du 5ème rang par pas de 7 de 5 à 8 ; pour changer les nbcell[1] en [0]
comme pour 240/30 tu n'as que 8 lignes numéroté de 0 à 7 ...on passe au j suivant...67 , rang 2 famille 7; par pas de 7 de 2 à 8...etc

voila pourquoi on criblerai directement de la phase S2, sans avoir même besoin de faire append fam [0,0,0,0,0,0,0,0].
suivant ton processus expliqué, que le programme exécute, et qui correspond vraiment à l'algorithme du crible...
processus décrit entièrement au dessus, post #220...

suite à ce processus :
ce qui suit ci dessous ne sert strictement à rien , déjà à cause des j > n = 240...tu en conviendras.

Je peux modifier Pfam (une ligne) pour que les j %30 d'une même sous-liste, soient les mêmes, comme ça : (inutile)
[
[151, 271, 181, 361, 271]
[67, 7, 337, 157, 157]
[193, 73, 103, 463, 43]
[137, 227, 77, 497, 347]
[109, 139, 259, 259, 499]
[53, 293, 233, 293, 233]
[179, 29, 389, 89, 119]

Ceci est le résultat de tes explications, dans le processus de la phase S3, criblage.
Qui met tout en évidence, et les erreurs qu'à fait mon petit fils dans le déroulement du programme ...

y compris de ne pas limiter les j = entiers congrus 2n%Pi, dans les pfam, > n; heureusement sans incidence ...puisque cela nous donnerai les entiers de 7 à N et non de N à 2n, qui ne sont pas premiers..bref...comme dirait pépin...

@ +

Dernière modification par LEG (10-05-2018 16:08:24)

Hors ligne

#220 10-05-2018 17:37:35

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

Re : crible en python

Re,

je pensais que tu savais, que ces nombres dans pfam sont les nombres qui sont congrus à 2n modulo Pi (pi ?)

Ça, je sais, je vois, c'est la réponse à comment sont-ils fabriqués ?
Moi, ce qui m'intéresse, c'est qui ils sont, ce qu'ils représentent par rapport
- soit à l'ensemble des nombres  de 240 à 480
- soit à mes candidats à la primature : [241, 247, 251, 253, 257, 259, 263, 269, 271, 277, 281, 283, 287, 289, 293, 299, 301, 307, 311, 313, 317, 319, 323, 329, 331, 337, 341, 343, 347, 349, 353, 359, 361, 367, 371, 373, 377, 379, 383, 389, 391, 397, 401, 403, 407, 409, 413, 419, 421, 427, 431, 433, 437, 439, 443, 449, 451, 457, 461, 463, 467, 469, 473, 479]
- soit à la liste nombres (on passe de 40 nombres à 64 : ça m'a toujours épaté :)
[
[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]
]

En 1 mot comme en 100, je ne sais toujours ce que tu souhaites que je fasse.
Je dois m'inspirer de ce que tu as écrit ci dessous et de l'exemple traité après :

n=240,
Pi = [7,11,13,17,19] index de 0 à 4, et pfam de 0 à 4
j doit être au maximum <= f = pi*29 et et si j >= n break , on passe à Pi et R suivant;  tel que j <= n {ce que je n'ai pas réussi à faire ce matin car il y a une limites maxi pour les Pi petits  donc j <= f et si j >= n break , pour les Pi plus grands, tel que Pi*29 > n limite donc j >n l'instruction break , fait passer à Pi et R suivant; car ils cribleront  moins de 8 fam...

Qui est R ? Connais pas...
Attention, tantôt tu écris $<$n tantôt $\leqslant$... Sois plus rigoureux...

Il y a aussi que tu utilises des versions déjà modifiées (ce n'est pas la première fois !).
Par exemple, tu évoques ce bloc :

for i in range(lenpfam) :
        for j in range(8):
            index = int((pfam['i][j] - p8[j]) / 30)          
            while index < nbcell:
                nombres[j][index] = 0
                index += p['
i]

Alors qu'il date...
La dernière version en cours est celle-ci :

    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

Si tu ne l'utilises pas, pourquoi ? que lui reproches-tu ?
Pour mémoire,
Primes_init pour n = 240 est : [7, 11, 13, 17, 19]. C'est bien ce que tu appelles Pi ?

j doit être au maximum <= f = pi*29 et et si j >= n break , on passe à Pi et R (?) suivant ;  tel que j <= n

Il y a deux cas de figure possibles
[tex]n\leqslant pi*29[/tex]  ---> On doit avoir [tex]j\leqslant n\; ***;\leqslant pi*29[/tex] et j ne peut pas être dans la zone [tex]***[/tex]
et
[tex]pi*29\leqslant n[/tex]  ---> On doit avoir [tex]j\leqslant pi*29\;***\;\leqslant n  [/tex] et j ne peut pas être dans la zone [tex]***[/tex]
Si oui, alors tu as parcouru mon grand tableau d'un œil distrait, parce que c'était bien mon interprétation première :
[tex]j \leqslant min(pi*29,n)[/tex] : j doit être toujours être inférieur à la plus petite des deux valeurs entre n et pi*29, (min(a,b) = minimum de a et b en Python).

>>> print (min(7,2))
2

 pi   29*pi    n     min(29*pi,n)
  1    29     120        29
  7   203     120       120
 11   319     120       120
 13   377     120       120
 17   493     120       120
 19   551     120       120
 23   667     120       120
 29   841     120       120

  1    29     300        29
  7   203     300       203
 11   319     300       300
 13   377     300       300
 17   493     300       300
 19   551     300       300
 23   667     300       300
 29   841     300       300

tu as les j  de pfam les entiers congrus à 2n [Pi]

Non, il ne peut pas y avoir de congruence modulo une liste : Pi = [7, 11, 13, 17, 19]. Tu veux parler de modulo pi avec [tex]pi \in Pi[/tex] ?
Attention, en Python, pi ou Pi ne désignent pas le même objet...
C'est pour ça que (habitude personnelle) je prends une initiale en minuscules pour une variable numérique et en capitales pour listes, Dictionnaires, chaînes...)

A.append(debut_index) --> désolé c'est une scorie non supprimée lors de mes essais
            Nombres_j=nombres[j]
            for index in range(debut_index, nbcell,pi):
                Nombres_j[index] = 0

Cette ligne ne me servait qu'à stocker tous les debut_index pour les examiner après.
N'a rien à faire dans le bloc.

Donc

    for i,Pf in enumerate(Pfam):                           # on garderait ces lignes ou pas ?
        pi=Primes_init[i]                                  # Si : non
        for j in range(8):                                 # Quoi à la place ?
            debut_index= ? # telle est la question clé ...
            Nombres_j=nombres[j]
            for index in range(debut_index, nbcell,pi):
                Nombres_j[index] = 0

Utiliser le quotient
lequel ? celui-ci : j//30 ?....... Réponse : oui ou non ?
On abandonnerait Dico[j%30] ? ...Non
Si on garde les deux, on peut les obtenir d'un coup : Excellente idée et en modifiant
q,reste=divmod(j,30)

En modifiant quoi ? q,reste=divmod(j,30) ? alors tu calcules comment ton index ?

J'arrête là parce que j'ai entrevu que tu as modifié ton post...

@+


Arx Tarpeia Capitoli proxima...

En ligne

#221 10-05-2018 19:55:57

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

Re : crible en python

re Yoshi

Ça, je sais, je vois, c'est la réponse à comment sont-ils fabriqués ?

voyons , ils sont fabriqué à partir du reste R de 2n%pi puis on les augmente de k*Pi comme pour fabriquer les multiples de Pi dans Eratosthène ...Pour n=240, et Pi =7 , 480 % 7 == 4, qui est le premier R congru à 480 [7] ,d'où, R  +7+7+7..etc <= n , j'ai tous les entiers
congru à 480[7; de même pour les multiples de 7, en partant de 7.+7+7..<=n]

Moi, ce qui m'intéresse, c'est qui ils sont, ce qu'ils représentent par rapport
- soit à l'ensemble des nombres  de 240 à 480

pour le premier = R +7 ==11, 11 est congru à 480[7]  d'où 480 -11 , ne peut être premier car divisible par 7; propriété des entiers A congru à B [pi] , pi divise la différence A -B,
je te l'ai expliqué..tu n'as peut être pas fait attention..avec tous ces massage.

comme on s'intéresse aux entiers non multiple de 2,3 ou 5, donc à l'ensemble des entiers congrus à 1 modulo 30, ou à Pi modulo 30, pour Pi premier appartenant à [7 : 29] donc : P8= [1,7,11,13,17,19,23,29];
mes entiers > n , qui sont tes candidats > n
et comme on sait que si un entier de cet ensemble appartenant à [ 7 ; n] , n'est pas congru à 2n % Pi, et bien il est premier appartenant à [n ; 2n] , soit nos candidats..je t'ai même expliqué pourquoi j'étais sûr d'extraire tous les nombres premiers appartenant à [n ;2n] en te disant, c'est trivial...:
Car il suffit de barrer de n à 2n les multiples de [[tex]P_i\leqslant\sqrt{2n} [/tex]] selon le principe Eratosthène, mais en utilisant les congruences. ie) marquer les entiers [tex] n\equiv {2n} [p_i] [/tex] de n à 2n, selon ce même principe, mais avec les [tex]P_i\leqslant\sqrt{2n} [/tex] ....!; avec n appartenant aux familles arithmétique P8[....], de raison 30.. D'où tes candidats comme les miens de n à 2n font bien partie de l'ensemble P8, en progression arithmétique..!

ensuite c'est pour cela, qu'on limite pour cribler jusqu'à n avec Pi, les J <= min(j+pi*29, n) en partant de j , car on aura les 8 j  , dont un seul par famille de P8. On partira du rang de ce j par pas de Pi , soit 7 pour cet exemple...

donc il nous faut l'index de départ ou le rang dans sa famille, pour marquer les entiers congrus à 2n%Pi par pas de Pi ....> n/30 puisque l'on est en progression arithmétique de raison 30 dans les 8 familles de P8. Comme le principe d'Eratosthène...

d'où on a besoin d'utiliser p8%30 conjointement avec Dico%30 à) pour l'index, b) pour la famille à qui appartient l'index de j. je te l'ai détaillé , en reprenant tes explication..
tu me dis :

Qui est R ? Connais pas...

Ah bon..et c'est quoi que tu calcules depuis le début.. 2n%pi...? si c'est pas R, ...?
j = Ri... Attention, tantôt tu écris <n tantôt ⩽... Sois plus rigoureux... ok...

j⩽min(pi∗29,n) : j doit être toujours être inférieur à la plus petite des deux valeurs entre n et pi*29, (min(a,b) = minimum de a et b en Python).

On est bien d'accord, mais tu oublies, dans l'exemple que l'on utilise avec n = 240 quand tu incrémentes les j +2*Pi..tu ne dépasses pas  n...? a QUOI BON , PUISQU' ALORS j n'est plus <= à 240  à quoi sert 'il, c'est 2n - (n-1 = j) qui nous intéresse..pour marquer les n <= 2ncongrus 2n%pi .c'est pour cela que dans pfam il est inutile d'avoir des j >= 240

ton tableau que j'ai bien compris min (29*pi) mais avec n=240 comment limiter avec pi = 11, puis 13, puis 17 et 19 que j lorsqu 'on les teste et qu'on les incr , on s'arrête à n<= 240...

pi> 5   29*pi    n     min(29*pi,n)
             
  7     203     240       
11    319     240    480 -253 n'est pas entre n et 2n..il ne peut surement éliminer un entier non premier de n à 2n   
13    377     240   ..etc ..480 - 353, il est > 240, d'où il ne peut supprimer un multiple de[tex]P_i\leqslant\sqrt{2n} [/tex] de n à 2n
17    493     240   ...etc ..480 -259, il est > 240, d'où il ne peut supprimer un multiple de[tex]P_i\leqslant\sqrt{2n} [/tex] de n à 2n
19    551     240 
  480 - 499  =..? > 240 et > 480 ....idem....

Le but du crible est bien d'éliminer entre n et 2n, les entiers non premiers,  ie): multiple de[tex]P_i\leqslant\sqrt{2n} [/tex]; en marquant [0]:
les entiers <= n, qui sont congru à 2n%Pi
.

avec effectivement: Tu veux parler de modulo pi avec pi∈Pi ? bien sûr , et Pi <= sqrt de 2n...

En modifiant quoi ? q,reste=divmod(j,30) ? alors tu calcules comment ton index ?

on a bien dans le processus :
après les 2 testes :if j%3!=0 and d_c!=5:

  j = X, appartenant à [7;n] et il n'est pas multiple de 3, ni de 5

donc cette ligne:
               fam =Dico[j%30] ["calcule à qu'elle famille X appartient si R==0, et comment on obtient en même temps le quotient
                if pfam['i][fam] == 0:  ..........................
                    pfam['i][fam] = j    ..........................
ce qui nous donnerait aussi l'index de X, et on par pour cribler , avec les instructions qui vont avec....on ferait le criblage à la suite..tu as détaillé toi même comment on obtient l'index dans le processus.. index = ((pfam[i'][j] - p8[j])// 30).
comme le fait ce bloc en dessous , sans avoir besoin d'appeler à nouveau pfam[0], puis [1]...[4]

je reprend ton exemple post#194: Exemple avec j=0 : Pf[0] c'est Pfam[1][0] qui vaut 271 (> 240) inutile de calculer...
              ici debut_index= (271- 11)//30 = 9  = quotient  (Le 1 c'est P8|0]

bloc que j'utilise dans la version G8Y par famille, et qui marche aussi bien que la dernière dans G9y peut importe l'une ou l'autre
.................................................................................................

#ON CRIBLE LES 8 COLONNES AVEC CHAQUE FAMILLE DE pi
    start_time = time.time()
    lenpfam = len(pfam)
    for i in range(lenpfam):
        pi=p['i]
        for j in range(8):
            index = ((pfam[i][j] - p8[j])// 30)
            while index < nbcell:
                nombres[j][index] = 0
                index += pi
 

.......................................................................................

si on teste, puis on détermine la fam , et on index, j alors dans la foulée  on peut aller cribler .....!
sans avoir à passer par le bloc ci dessus qui fait le même travail que le bloc famille pour chaque Pi ... qui lui ne fait que remplir pfam[n] pour le bloc on crible les 8 colonne,
alors qu'il place les j dans les bonnes famille ...tu as détaillé ce processus , moi j'ai vu connaissant l'algorithme, que l'on pouvait obtenir le quotient pour indexer j et donc aller cribler..dans la foulée  ...

donc  on aurait pas non plus besoin "en principe"  de faire appel à: pfam.append([0,0,0,0,0,0,0,0]) que l'on supprime, puisqu'il n'est plus question de remplir et de positionner les j, dans pfam pour les envoyer ensuite au bloc criblage......non..?

Dernière modification par LEG (11-05-2018 06:07:17)

Hors ligne

#222 10-05-2018 20:43:58

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

Re : crible en python

pour faire simple est résumer:n=240
j'ai : j = 271 obtenu à partir de R =7 et pi = 11
, qui a passé les tests j%3 et j%5

donc fam:

bloc famille de Pi :
je vais faire dans fam = Dico[j%30] c'est à dire (271 -13) / 30 != 0 , puis (271 - 1) / 30==0  et quotient = 9
je place j dans pfam [271:0 , jx:1, jy:2...etc jz:7] ; pfam est rempli, donc ok , pour le bloc : crible les 8 colonne....


ce bloc ,l'appel :
lenpfam = len(pfam) etc etc.

il va calculer encore le quotient entier soit: index = ((pfam['i][j] - p8[j])// 30) soit 271 //30 == 9,...

pour aller cribler en partant de 9 à 8 par pas de 7 (" car c'est bien pi= 7 qui crible...")

je pense que cela aurait pu se faire en une seule fois dans la foulée, sans même avoir besoin de faire:  pfam.append([0,0,0,0,0,0,0,0]) et du coup, même d'éviter j = 271 > 240...au niveau du bloc de famille de Pi et criblage....Non ?

Le problème qu'il y avait , tout au début dans le programme, la limite était while j <= n..ok , mais il calculait les j, jusqu'à n...et quelque soit n, il s'en suivait l'erreur que tu as remarquée, pour les petites valeur de n < 1200, je t'ai ensuite signalé que j'avais trouvé d'où cela venait..cette limite que j'ai changée en while j<= f. en définissant f .
mais cette limite n'empêche pas non plus de limiter j dans la zone de 7 à n, exemple du post ci dessus , de ton petit tableau...

le seul moyen et de cribler dans la foulée comme expliqué ci-dessus.. si possible.. bien entendu.

je reprend l'exemple de n = 240 soit 2n = 480., pour marquer "tes candidats" , multiples de Pi ⩽ √2n, ["selon Eratosthène mais, dans les congruences"] en marquant les entiers n tel que définis, à savoir : [tex] \equiv  {2n} {[P_i]}[/tex]

avec [tex]P_i = 11[/tex]; donc je calcule R = 2n%Pi .soit : R = 7, Pi = 11, incr = 2*11 while j<= f==326
Ri = j : 7 + incr....> 326 =
j'établis le liste des j congrus 2n%11
7   29    51    73    95    117    139    161    183    205    227    249    break > 240 271    293    315    337
je marque uniquement les congrus appartenant à P8, donc ce qui sont : !=j%3 ou j%5 et donc < 240...! ;

Afin d'éliminer les multiples de Pi de n à 2n . En notant le fait que je n'ai pas besoin de m'en occuper, car il me suffira , de compter les [1] de 7 à n, qui sont donc [tex]\not\equiv {480}[11][/tex].

congrus à 480[11] < 240 : [7, 29, 73, 139, 161, 227 ] soit 6 éléments qui aurait dû être dans Pfam(1) .. pour ensuite aller,calculer leur index, et les placer dans leur famille respective..

ce que je vais faire avec fam = Dico[j%30] : avec le reste et le quotient; R =0 indique la famille dans Dico, est le quotient indique l'index de j: ;   {"on marque la celllule [1] en [0], ce qui indique que l'entier est congrus 2n%Pi"}

7:
donc fam =Dico[j%30]=Dico[7%30]= Dico[7]est le quotient ==(0) je vais mettre (0) dans P8 == 7, indice 0 , je marque par pas de 7, de 0 à 7, car nbcell = 240/30 = 8; indice de 0 à 7, ce que tu m'as montré..

29:
fam =Dico[j%30]=Dico[29%30]= Dico[29]est le quotient ==(0) je vais mettre (0) dans P8 == 29, indice 0 , je marque par pas de 7, de 0 à 7,

73:
fam =Dico[j%30]=Dico[73%30]= Dico[13]est le quotient ==(2) je vais mettre (2) dans P8 == 13, indice 2 , je marque par pas de 7, de 2 à 7,

139:
fam =Dico[j%30]=Dico[19%30]= Dico[19]est le quotient ==(4) je vais mettre (4) dans P8 == 19, indice 4 , je marque par pas de 7, de 4 à 7,

161:
fam =Dico[j%30]=Dico[11%30]= Dico[11]est le quotient ==(5) je vais mettre (5) dans P8 == 11, indice 0 , je marque par pas de 7, de 5 à 7,

227:
fam =Dico[j%30]=Dico[17%30]= Dico[17]est le quotient ==(7) je vais mettre (7) dans P8 == 17, indice 7 , je marque par pas de 7, de 7 à 7,  ..fin du criblage pour pfj
qui ne peut donc cribler , que 8 familles ...! et marqué [0] 8 entiers  au total. Ce qui correspondent aux multiples de 11 , dans n à 2n...! D'où il n'est nul besoins de s'en occuper...!

je passe donc à Pi et R suivant = 13 et 12  , afin de réitérer la suite du criblage modulo 7.
........................... j'établis la liste des j > 12: congrus 2n%13
[12%2==0] + 13 = j
[25    51    77    103    129    155    181    207    233    259 >240 break] 285    311    337    363    389    415
..........................................
77:
fam =Dico[j%30]=Dico[17%30]= Dico[17]est le quotient ==(2) je vais mettre (2) dans P8 == 17, indice 2 , je marque par pas de 7, de 2 à 7,

103:
fam =Dico[j%30]=Dico[13%30]= Dico[13]est le quotient ==(3) je vais mettre (3) dans P8 == 13, indice 3, je marque par pas de 7, de 3 à 7, 

181:
fam =Dico[j%30]=Dico[1%30]= Dico[1]est le quotient ==(6) je vais mettre (6) dans P8 == 1, indice 6 , je marque par pas de 7, de 6 à 7,

233:
fam =Dico[j%30]=Dico[23%30]= Dico[23]est le quotient ==(7) je vais mettre (7) dans P8 == 23, indice 7, je marque par pas de 7, de  à 7, 

fin du criblage pour Pfj; qui aura marqué 4 entiers [0] congrus 2n%13

je passe à Pi et R suivant .....etc,

A la fin le programme compte les [1], qui indique le nombre de nombres premiers q, de n à 2n ;sans avoir eu besoins de s'en occuper.
Car les congrus à 2n%Pi de 7 à n , ont indiqués les multiples de Pi >= n, .....> 2n

Dernière modification par LEG (11-05-2018 10:08:49)

Hors ligne

#223 11-05-2018 10:51:40

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

Re : crible en python

Salut,

Je vois qu'on est entré dans un dialogue de sourds.
Je vais essayer d'être beaucoup plus bref...

re Yoshi

    Ça, je sais, je vois, c'est la réponse à comment sont-ils fabriqués ?

voyons , ils sont fabriqué à partir du reste R de 2n%pi puis on les augmente de k*Pi comme pour fabriquer les multiples de Pi dans Eratosthène ...Pour n=240, et Pi =7 , 480 % 7 == 4, qui est le premier R congru à 480 [7] ,d'où, R  +7+7+7..etc <= n , j'ai tous les entiers congru à 480[7; de même pour les multiples de 7, en partant de 7.+7+7..<=n]

Citation complète :

je pensais que tu savais, que ces nombres dans pfam sont les nombres qui sont congrus à 2n modulo Pi (pi ?)

Ça, je sais, je vois, c'est la réponse à comment sont-ils fabriqués ?

Traduction :
je vois et je sais que  ces nombres dans pfam sont les nombres qui sont congrus à 2n modulo Pi pi, ce n'est pas la question que je me pose puisque je connais la réponse..
Me dire que ces nombres dans pfam sont les nombres qui sont congrus à 2n modulo Pi pi, c'est croire que je ne n'ai pas vu, pas retenu, pas compris comment ils sont construits. Et ce n'est pas le cas.
Donc, j'abandonne ce sujet...

A l'avenir, je vais essayer de formuler des phrases courtes, sans question.
En outre, si tu continues à utiliser tantôt des majuscules tantôt des minuscules pour désigner le même objet, je ne ferai pas l'effort de chercher. J'ai déjà commence. Exemple :

Qui est R ? Connais pas...

Ah bon..et c'est quoi que tu calcules depuis le début.. 2n%pi...? si c'est pas R, ...?

...........................................

j'ai : j = 271 obtenu à partir de R =7 et pi = 11
, qui a passé les tests j%3 et j%5

donc fam:

bloc famille de Pi :
je vais faire dans fam = Dico[j%30] c'est à dire (271 -13) / 30 != 0 , puis (271 - 1) / 30==0  et quotient = 9
je place j dans pfam [271:0 , jx:1, jy:2...etc jz:7] ; pfam est rempli, donc ok , pour le bloc : crible les 8 colonne....

Tu écris : 271 obtenu avec R=7 et pi=11
Puis, tu enchaînes avec (271-13)/30  !=0 et (271 - 1)/30 == 0...
11 annoncé puis 13, puis 1 utilisé. Bizarre...
R doit donc être probablement P8[1]...

Tiens, pour ta gouverne :
puis (271 - 1) / 30==0

 :
>>> (271-1)/30==0
False
>>> (271-1)/30
9.0
>>> (271-1)//30
9
 

L'un des quotients est un float, l'autre un integer : la place mémoire utilisée et la vitesse de traitement ne sont pas les mêmes...
(271 - 1) / 30==0  et quotient = 9
Moi qui toujours cru que / donnait un quotient...

Je présume donc qu'il faut lire : (271 - 1) % 30==0  et quotient = 9.
Si oui, alors on écrit :
q,reste=divmod((j-1),30)

Quelques calculs d'illustration obtenus via la fonction divmod():

Pour j =   7 on a : (  7-1)//30 = 0  et (  7-1)%30 =  6
Pour j =  29 on a : ( 29-1)//30 = 0  et ( 29-1)%30 = 28
Pour j =  51 on a : ( 51-1)//30 = 1  et ( 51-1)%30 = 20
Pour j =  73 on a : ( 73-1)//30 = 2  et ( 73-1)%30 = 12
Pour j =  95 on a : ( 95-1)//30 = 3  et ( 95-1)%30 =  4
Pour j = 117 on a : (117-1)//30 = 3  et (117-1)%30 = 26
Pour j = 139 on a : (139-1)//30 = 4  et (139-1)%30 = 18
Pour j = 161 on a : (161-1)//30 = 5  et (161-1)%30 = 10
Pour j = 183 on a : (183-1)//30 = 6  et (183-1)%30 =  2
Pour j = 205 on a : (205-1)//30 = 6  et (205-1)%30 = 24
Pour j = 227 on a : (227-1)//30 = 7  et (227-1)%30 = 16
Pour j = 249 on a : (249-1)//30 = 8  et (249-1)%30 =  8
Pour j = 271 on a : (271-1)//30 = 9  et (271-1)%30 =  0

Voilà les blocs S2 et S3 (moi j'utilise ceux-là) :

   
    # 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
        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
 

Pour utiliser le bloc S2, il y a au moins un prérequis : Pfam.

Tu m'as noyé sous des pages, et je n'ai pas l'envie de les lire et relire pour trouver les éléments qui me permettraient de démarrer :
- Savoir si on se passe ou pas de ce Pfam,
  * Si oui, ce qu'on utilise à la place
  * Si non, comment le construire
- Savoir ce qu'on va faire de Dico={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}.
  Parce que j'ai eu la curieuse impression que tu voulais utiliser un Dico qui contienne l'index de chaque j.

Tu sembles dire que la solution min n'est pas bonne...
Alors, cela signifie que je n'ai toujours pas compris ce que tu veux dire par :

doit être au maximum <= f = pi*29 et et si j >= n break , on passe à Pi et R suivant;  tel que j <= n {ce que je n'ai pas réussi à faire ce matin car il y a une limites maxi pour les Pi petits  donc j <= f et si j >= n break , pour les Pi plus grands, tel que Pi*29 > n limite donc j >n l'instruction break , fait passer à Pi et R suivant; car ils cribleront  moins de 8 fam...

ni en quoi, ma suggestion n'est pas bonne..

Désolé, si mon intelligence te paraît limitée : je suis né comme ça :-((.
Tu devrais peut-être essayer de trouver un cerveau plus réceptif : je t'aurais bien conseillé developpez.net, mais là-bas, s'ils sont (très) bons, je trouve que, souvent, on y manque de compréhension et de tact avec des demandeurs qui sont pourtant les auteurs des scripts présentés, avec les envoyant bouler avec quelque chose du genre : "Ouvrez un tuto et lisez-le, faites-en les exos", quant à ta tentative sur l'Île Maths, t'as vu ce qu'elle a donné...

Je pense qu'on devrait
- d'abord utiliser la méthode avec Pfam et la modifier/simplifier jusqu'à ce qu'elle donne satisfaction,
- ensuite, instruits par l'expérience, tenter de s'en passer...

J'ai encore plein de remarques à faire sur ce que tu m'écris (qui empêche le matheux que j'étais de comprendre, parce que source de confusion), mais j'ai déjà été bien plus long que voulu.

@+


Arx Tarpeia Capitoli proxima...

En ligne

#224 11-05-2018 12:41:22

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

Re : crible en python

attend Yoshy:
j'ai repris l'exemple de tes explications en abrégeant ok.. où tu as cité le processus des 2 lignes:

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

   

  .. je vais faire dans fam = Dico[j%30] c'est à dire (271 -13) / 30 != 0 , puis (271 - 1) / 30==0  et quotient = 9 donc j'ai ramené cela à :

je vais faire dans: fam = Dico[j%30] c'est à dire (271 -13), 13%30 != 0 , puis (271 -1)= 1%/ 30 == 0  cette ligne calcul le reste
ensuite  c'est  et quotient = 9 ..c'est tout.

R doit donc être probablement P8[1]...

Effectivement...puisque c'est le rôle de cette ligne de programme , pour ensuite envoyer Pfam [.......] dans le boc de criblage ..

Je présume donc qu'il faut lire : (271 - 1) % 30==0  et quotient = 9.
Si oui, alors on écrit :
q,reste=divmod((j-1),30)

Quelques calculs d'illustration obtenus via la fonction divmod():

Donc c'est Exactement ce qu'il faudrait faire ici :,

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

   

mais comme ceci:

Pour j =   7 on a : (  7-1)//30 = 0  et (  7= Dico[j%30] == 0  soit [7:1] on a son index=0 , famille qui dans
Dico = {..,7:1,..}

Pour j =  29 on a : ( 29-1)//30 = 0  et (29= Dico[j%30] == 0  soit [29:7] on a son index =0 , famille qui dans
Dico = {..,7:1,.............,29:7}

Pour j =  51 on a : ( 51-1)//30 = 1  et  multiple de 3
Pour j =  73 on a : ( 73-1)//30 = 2  et 73= Dico[j%30] == 0  soit [13:3] on a son index=2, famille qui dans
Dico = {..,7:1,..,13:3,.. ... ...,29:7}

Pour j =  95 on a : multiple de 5
Pour j = 117 on a : multiple de3

Pour j = 139 on a : (139-1)//30 = 4  et (139= Dico[j%30] == 0  soit [19:3] on a son index=4, famille ,
Dico = {..,7:1,..,13:3,.. ,19:5 ...,29:7}

Dans la foulée, et des que j dépasse > 240 , pour cet exemple , on passe au suivant..non?

tout d'abord, je ne me permettrait pas de penser quoi que ce soit sur tes capacités.....qui m'ont permis de comprendre le processus du déroulement du programme, de tout ce que tu m'as apporté...! et excuse moi , si je m'exprime mal.

Pour utiliser le bloc S2, il y a au moins un prérequis : Pfam.

Comment alors empêcher J, dans Pfam de dépasser n..?
la seule solution était à mon sens de s'en passer, et de calculer  les J au fur est à mesure
et effectivement le fonction Dico , permet de faire les deux et pourrait être utilisé pour les index, comme tu viens de le voir...
Dico={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}. famille
Dico={. ...................................................}. index

dès lors, je pense que ce problème de limite même en laissant while <= f ne  éviterait de calculer des j qui sont > n inutilement car, il y en a énormément ce, qui bouffe de la mémoire et du temps ..

tout cela était dans le but de finir, afin d'améliorer la partie crible qui te tenait...Car il ne faut quand même pas oublier comment tu as modifié ce programme pour le rendre parfait...
.........................................................................................................................................................
voici d'ailleurs les nombres premiers q de 240 à 480.., du premier crible de base...avant même que je modifie sa limite j<= f
tu en conviens , d'avoir les nombres premiers, ne sert pas à grand chose  ça ne sert pas à grand chose :
.............................................................................................................................................................
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG3_modulo30.py =====
Donnez la valeur de n = 30k : 240
CribleG3 mod30 : Famille de chaque Pi: 0.0 seconds ---
CribleG3 mod30 : Criblage des 8 familles: 0.0 seconds ---
[269, 359, 389, 419, 449, 479, 263, 293, 353, 383, 443, 349, 379, 409, 439, 257, 317, 347, 467, 283, 313, 373, 433, 463, 251, 281, 311, 401, 431, 461, 277, 307, 337, 367, 397, 457, 241, 271, 331, 421]
On a 40 nombres premiers

pour rappel : le programme d'origine :


# ATTENTION: n doit être multiple de 30
def crible_mod30(n):
   # INITIALISATION
   start_time = time.time()
   nbcell = int(n/30)
   nombres = [[1 for _ in range(nbcell)] for _ in range(8)]
   p = eratostene(int(n))
   p = p[3:]
   lenp = len(p)
   r = []
   p8 = [1, 7, 11, 13, 17, 19, 23, 29]
   pfam = []
   print("Crible mod30 : Initialisation: %s seconds ---" % (time.time() - start_time))

   # FAMILLES POUR CHAQUE Pi
   start_time = time.time()
   for i in range(lenp):
      r.append(2*n % p['i])
      pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
      j = r[i]
      incr = p[i]*2
      d_c = str(j)[-1]
      # On elimine les restes pairs
      if d_c == '0' or d_c == '2' or d_c == '4' or d_c == '6' or d_c == '8':
         j += p[i]
         d_c = str(j)[-1]
      while j < n:
         if d_c == '5' or j % 3 == 0:  # on passe au suivant
            fam = -1
         elif d_c == '1':  # on vérifie 1 et 11
            if j % 30 == p8[0]:
               fam = 0
            else:
               fam = 2
         elif d_c == '3':  # on vérifie 13 et 23
            if j % 30 == p8[3]:
               fam = 3
            else:
               fam = 6
         elif d_c == '7':  # on vérifie 7 et 17
            if j % 30 == p8[1]:
               fam = 1
            else:
               fam = 4
         else:  # on vérifie 19 et 29 (d_c = 9)
            if j % 30 == p8[5]:
               fam = 5
            else:
               fam = 7
         if fam != -1 and pfam[i][fam] == 0:
            pfam['i][fam] = j
         j += incr
         d_c = str(j)[-1]

   print("Crible mod30 : Famille de chaque Pi: %s seconds ---" % (time.time() - start_time))

   # ON CRIBLE LES 8 COLONNES AVEC CHAQUE FAMILLE DE Pi
   start_time = time.time()
   lenpfam = len(pfam)
   for i in range(lenpfam):
      for j in range(8):
         index = int((pfam[i'][j] - p8[j]) / 30)
         while index < nbcell:
            nombres[j][index] = 0
            index += p['i]
   print("Crible mod30 : Criblage des 8 familles: %s seconds ---" % (time.time() - start_time))

   # AFFICHAGE
   for i in range(8):
      count = 0
      for cell in nombres['i]:
         if cell == 1:
            count += 1

   # CALCUL DES NOMRES PREMIERS ENTRE N ET 2*N
   start_time = time.time()
   premiers = []
   for i in range(8):
      for j in range(nbcell-1, -1, -1):
         if nombres['i][j] == 1:
            premier = 2*n-((j*30)+p8['i])
            premiers.append(premier)
   print("Crible mod30 : Extraction des premiers n à 2*n : %s seconds ---" % (time.time() - start_time))
   print(premiers)
   premiers.sort()
   return premiers


n = int(input("Donnez la valeur de N = 30k : "))
#nb = len(crible_G(n))
#print("On a "+str(nb)+" nombres premiers")
#print("---------------------------------------------------------")
nb = len(crible_mod30(n))
print("On a "+str(nb)+" nombres premiers")
os.system("pause")
 

Je pense qu'on devrait
- d'abord utiliser la méthode avec Pfam et la modifier/simplifier jusqu'à ce qu'elle donne satisfaction,
- ensuite, instruits par l'expérience, tenter de s'en passer...

Là , c'est toi le mieux placé pour juger....! Mais effectivement tu as entièrement raison
@+

Dernière modification par LEG (11-05-2018 15:14:33)

Hors ligne

#225 11-05-2018 15:13:15

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

Re : crible en python

dans ta dernière version que tu utilises, cette ligne cause une erreur ;

debut,fin,pas=r+pi*(1-r%2),1+r+pi*29,pi*2  / si je remplace /  1+r+pi*29  (par;)  min(pi*29,n)

cela m'affiche 35 premiers au lieu de 40 ...???

Mais par contre , ta remarque est justifiée, de ne pas toucher à pfam , car ce n'est que sur les petites valeur de n qu'il y a beaucoup de j <= f mais qui dans pfam, dépassent n .

Par contre dès que l'on passe à n >1500, il est pratiquement évident que le phénomène se réduit à moins d'une douzaine , donc sans incidence de temps ou de mémoire..
En effet, si je prend n = 3000 , sqrt de 2n = 77 , donc le maximum pour Pi; et 77*30 = 2310 = limite f...§ Je n'avais pas fait attention à ce cas...!

Et pourtant tout l'indiquait... les temps pour initialisation , et famille de Pi qui sont vraiment minime par famille....

Alors je pense, qu'il ne serait peut être bon de le laisser à la version finale cribleG9y_modulo30....avec tous mes remerciement....mon offre tient toujours...pour te remercier...tu vas pouvoir aller à la pêche.....LoLLLL

@++ Gilbert

Dernière modification par LEG (11-05-2018 16:56:39)

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)?
vingt moins treize
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