Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#201 08-05-2018 19:06:41
#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
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 948
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
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 :
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 :
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...
Hors 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 948
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...
Hors 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
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 948
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 queA,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=[],0print (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
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...
Hors 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 948
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...
Hors 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 948
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...
Hors ligne
#216 09-05-2018 22:05:37
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 690
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...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 948
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 ?
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
23
>>> reste
3
>>>
Un peu de synthèse.
Soient les deux blocs :
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...
Hors 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 :
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 948
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 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 :
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).
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
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...
Hors 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 <= 2n, congrus 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
.................................................................................................
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 948
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%5donc 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 = 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...
Hors 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:
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 :,
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 de3Pour 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