crible en python

LEG · 02-05-2018 13:52:45

pour fam, j'ai bien remis comme tu viens de le dire [0,0,0,0,0,0,0,0] effectivement cela m'imprime bien les 15j pour les 4 pi avec n=150
je pensais comme il ne reste qu'une famille p8 = 1%30 je pensais que pour fam [0]

yoshi a écrit :

Re,
Boum !
Il y a encore un autre problème
Tu initialises p8 comme ça : p8=1 Donc là, p8 est un nombre.

idem ci dessus, il ne reste qu'une famille donc j'ai mis p8 = 1,

je viens de mettre p8 = 1%30
et j'ai le même message, d'erreur ...

Et ici, je demandes quoi ??? : si il ne reste que la famille 1%30 ....? et dans p8 = ?

index = (pfam[i][j] - p8[j])//30
Et p8[j] renvoie l'erreur disant que p8 n'est pas indexable, qu'on ne peut pas y accéder avec un index vu que c'est un nombre...
@+

yoshi · 02-05-2018 14:34:29

Re,

Tu as conçu p8 comme une liste, donc p8=[valeur]
Comme je ne sais pas ce que tu bricoles, je m'en remets à toi pour remplacer valeur par le bon nombre.
Ensuite ici :

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

                fam =p8%30

si p8 est une liste, p8%30 ne peut fonctionner.
Il faut écrire fam=p8[indice]%30 : à toi de savoir quelle est la valeur de l'indice. Si p8 contient une seul élément, c'est p8[0]%30...

@+

LEG · 02-05-2018 15:54:22

ce que je bricole..:et je viens de suivre tes explications tout marche sauf que je n'ai pas les bons nombres pour la famille (1) modulo 30 uniquement .

avant p8 [1.7.11.13.17.19.23.29] représentait les 8 famille à cribler comme dans ton crible

et pour n = 150
cela nous donne pour la famille (1) modulo 30 : le résultat suivant avec G5 ou ton crible .. en rouge la famille (1) modulo 30 ensuite tu as la deuxième (7) modulo 30...etc

Donnez la valeur de n = 30k : 150
CribleG5 mod30 : Initialisation: 0.0 seconds ---
CribleG5 mod30 : Famille de chaque couple R et Pi: 0.0 seconds ---
CribleG5 mod30 : Criblage des 8 familles: 0.0 seconds ---
CribleG5 mod30 : Extraction des premiers n à 2*n : 0.0 seconds ---
[[0, 1, 1, 0, 1], [1, 1, 1, 0, 1], [0, 0, 1, 1, 0], [0, 1, 1, 1, 1], [1, 0, 1, 1, 1], [1, 1, 0, 1, 0], [1, 0, 0, 0, 1], [1, 1, 1, 1, 1]]
On a 27 nombres premiers
Appuyez sur une touche pour continuer...

je veux cribler que la famille 1 modulo 30 pour n 150 voici le résultat

Donnez la valeur de n = 30k : 150
CribleG1_mod30 : Initialisation: 0.015600204467773438 seconds ---
CribleG1 mod30 : Famille de chaque couple R et Pi: 0.0 seconds ---
CribleG1 mod30 : Criblage des 8 familles: 0.0 seconds ---
CribleG1 mod30 : Extraction des premiers n à 2*n : 0.0 seconds ---

[[1, 1, 1, 1, 0]]
On a 4 nombres premiers

tu vois , ce ne sont pas les bon et là je n'arrive pas à trouver le bon paramètre...pour avoir
[[0, 1, 1, 0, 1]

le principe du crible est le même donc quelque soit la famille unique que je prend je devrais avoir les bonne valeur...

Sauf si je fais des "conn..."

Dernière modification par LEG (03-05-2018 11:21:25)

LEG · 02-05-2018 16:53:40

voila un exemple de la famille 1 [30] le travail et le temps sont exact mais pas le résultat final ...On peut cribler plus loin...

Donnez la valeur de n = 30k : 9000000000
CribleG1_mod30 : Initialisation: 13.400423526763916 seconds ---
CribleG1 mod30 : Famille de chaque couple R et Pi: 0.5772008895874023 seconds ---
CribleG1 mod30 : Criblage de la familles: 66.90951776504517 seconds ---
CribleG1 mod30 : Extraction des premiers n à 2*n : 24.726043224334717 seconds ---
On a 65668177 nombres premiers (# nombre faux car mal paramétré )
Appuyez sur une touche pour continuer...

voila ce qu'il faisait avant que tu décrasses tout...
là, il vérifier les deux familles 1 et 11 mod 30 , puis, 7 et 17 ; 13 et 23 et19 et29

elif d_c == '1':  # on vérifie 1 et 11

        if j % 30 == p8[0]:

          fam = 0

        else:

          fam = 2

maintenant je ne veux que la famille 1 ou 11 peut importe même que la 7 , mais une seule , donc actuellement il me fait la famille 1, exemple post ci dessus , mais je n'arrive pas à le paramétrer...

Dernière modification par LEG (02-05-2018 17:32:26)

yoshi · 02-05-2018 17:28:33

Re,

C'est peut-être presque clair pour toi, mais pour moi tu me parlerais chinois que ce serait pareil...

[[1, 1, 1, 1, 0]]
On a 4 nombres premiers
tu vois , ce ne sont pas les bon et là je n'arrive pas à trouver le bon paramètre...pour avoir
[[0, 1, 1, 0, 1]

Bin non, je ne vois rien du tout, à part que tu écris dans ton post :

avant p8 [1.7.11.13.17.19.23.29]

Tu veux dire p8=[1,7,11,13,17,19,23,29] ?
Alors, pourquoi des points et non des virgules ?
Ah et je te signale (probablement le savais-tu ?), que, en Python, les variables r et R sont deux variables différentes. Python est sensible à la casse (minuscule/majuscule) : tu avais plusieurs fois dans tes postes écrit dico à la place de Dico...

Je ne peux pas t'aider : déjà qu'avec le précédent, j'étais limite, là je ne comprends strictement rien à ton nouveau procédé...

@+

LEG · 02-05-2018 18:00:48

[yoshi]Re,

C'est peut-être presque clair pour toi, mais pour moi tu me parlerais chinois que ce serait pareil...

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

On a 4 nombres premiers

ces 5 nombres sont les 5 premiers nombres de la famille 1 de raison 30 [1,31,61,91,121] le 5ème est marqué 0 car 121 est congru à 300 modulo 7; donc 300 - 121 ne peut être premier si il était bien paramétré comme ci dessous

tu vois , ce ne sont pas les bon et là je n'arrive pas à trouver le bon paramètre...pour avoir

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

Bin non, je ne vois rien du tout, :

je reprend : [[0, 1, 1, 0, 1] est bien paramétrer ton crible actuel est le mien G5 donne ce résultat
le premier 0 c'est 1 qui est marqué par le crible donc 0, 300 -1 n'est pas premier..
le 2ème 1 , = 31 , qui n'est pas marqué par le crible..300-31 = q premier
le 3ème 1 , = 61 , qui n'est pas marqué par le crible..300-61 = q premier
le 4ème 1 , = 91 , qui est marqué par le crible..300-11 n'est pas premier.
le 5ème 0 , = 121 , qui n'est pas marqué par le crible..300-121 = q premier

tu vois la différence entre 3 nombres premiers de n à 2n au lieu de 4 dans G1 que je dois modifier...

Tu veux dire p8=[1,7,11,13,17,19,23,29]

C'est bien ça, les 8 familles ou suites arithmétiques les premières valeurs de la ligne N°0 qui augmente de 30 à chaque ligne, mais qui sont représenté par des [[1],.........[1]]

[quote
elif d_c == '1': # on vérifie 1 et 11
if j % 30 == p8[0]:
fam = 0
else:
fam = 2
[/quote ] je vais essayer d'intercaller ça dans le programme et ou le modifier afin d'obtenir la bonne ligne [0, 1, 1, 0, 1] pour n = 150

Je ne peux pas t'aider : déjà qu'avec le précédent, j'étais limite, là je ne comprends strictement rien à ton nouveau procédé...
@+

c'est pas grave, tu en as fait déjà énormément et surtout le principale que tu as décrassé, je te suis toujours redevable...
@+

yoshi · 02-05-2018 20:50:15

Salut,

Tu as une façon de savoir ce qui cloche : facile mais fastidieux...
Tu sors crayon stylo et papiers ou ton tableur préféré, et tu suis pas à pas la procédure que tu as écrite...
La difficulté sera de ne pas faire ce que tu sais être exact, mais être rigoureusement "idiot" mais discipliné et bien faire ce va faire la machine, en suivant ligne par ligne ce qu'elle fait vraiment...
Ça m'est déjà arrivé de recourir à cette méthode qui n'est pas propre à déclencher des cris d'enthousiasme : je n'y pensais plus...
Ça vient de me revenir.
Si j'ai le temps, le courage, l'envie, j'essaierai aussi demain matin, pour voir...

@+

LEG · 02-05-2018 22:08:53

yoshi a écrit :

Salut,
Tu as une façon de savoir ce qui cloche : facile mais fastidieux...
Tu sors crayon stylo et papiers ou ton tableur préféré, et tu suis pas à pas la procédure que tu as écrite...
La difficulté sera de ne pas faire ce que tu sais être exact, mais être rigoureusement "idiot" mais discipliné et bien faire ce que va faire la machine, en suivant ligne par ligne ce qu'elle fait vraiment...
Ça m'est déjà arrivé de recourir à cette méthode qui n'est pas propre à déclencher des cris d'enthousiasme : je n'y pensais plus...
Ça vient de me revenir.
Si j'ai le temps, le courage, l'envie, j'essaierai aussi demain matin, pour voir...
@+

je l'ai fait sur excel pas à pas avec mon petit fils je lui montrai au fur et à mesure ce que je faisais mais ensuite le traduire en langage python ou autre pour que le pc le comprenne ça fait deux et de plus tu me l'a fait remarquer un peu plus dans tes posts ça dépend du programmeur...comment veux que je comprenne exactement ce que fait le programme pas à pas ...je sais ce qu'il doit faire...dans l'ordre..mais ça et le langage du programme: c'est un indien qui parle avec les signes à un polonais...

tu vois bien le travail que tu as fait par rapport au crible de départ.. tu as utilisé le dico pour transcrire l'ordre des 8 famille de P8, tu ne t'ai pas planté sinon le résultat du nombre de nombres premier de n à 2n serait faux...tu as même remarqué qu'il était faux pour de petites valeurs...lorsque j'ai trouvé la solution, cela n'avait rien à voir avec ce que je faisais pas à pas et pourtant...quel rapport entre prendre j jusqu'à f et j jusqu'à n..ça va moins vite et faux ...et bien le résultat sur le crible était pas évident...lorsque je prend que la famille congrue à 11 [30] dans excel je crible la 3ème, dans le programme dico= [ ,11:2 , ] quelqu'un qui comme moi ne comprend pas du la programmation , tu me le demande je te dis : et ben c'est 11 divisé par 2 ...

comment veux tu que maintenant je lui demande de ne prendre que la famille 1 et 11 modulo 30, par exemple :
j'écris dico = [1:0,11:2]
dans p8 je met p8 = [1 ,11] et bien à la fin de la nuit je tourne en rond...
là miracle... il ne sort qu'une famille et pas dans l'ordre bien sûr et par ce que j'ai supprimé [dico] de partout...car même pas il m'ouvrait la fenêtre... Tout ça pour te dire , mon petit fils qui me disait c'est pas grave si je ne comprend pas le fonctionnement du crible...tu parles...!

pour que le programme aille cribler que deux familles 1 et 11, je ne pense pas qu'il faut mettre p8= [7,13] et dico= [1:0,11:1] parce que peut être que dans la famille 1 modulo 30, les j seront bien positionné, avec les bonnes valeurs et son Pi criblera bien, mais je doute fort que la famille 11(mod 30) soit juste...et si on vérifie, en remettant la valeur des [1] et ensuite 300 - [1] , ça m'étonnerait que l'on sorte un nombre premier q congru à 19[30]...heureusement qu'on en a pas besoin car inutile mais les nbcelle[1] qui représente les entiers, doivent être bien marquées .
c'est pareil si avec Eratosthène je crible les multiples de 7, avec pi = 11 , en partant de 7 ....jusqu'à n = 150...

Passe une bonne nuit ...Merci Yoshi....

LEG · 03-05-2018 11:19:14

Bonjour Mr Yoshi.

J'ai enfin trouvé la solution qui était toute simple, comme quoi lorsque c'est simple il faut y penser....

Je ne veux cribler qu'un famille , sur les 8...! grâce à ton idée du dico[1:0,7:1,11:2....etc..,29:7], d'où :
cela crible dans l'ordre :[la 1, puis la 7 puis la 11.....et enfin la 29]

qu'est ce qu'il me fallait modifier dans le programme, pour qu'il ne me crible par exemple que la famille 1 modulo 30 et la 11 modulo 30...?
de sorte que le programme va très vite et plus loin avec la limite n...!

@ à tout à l'heure...

yoshi · 03-05-2018 12:52:35

Salut,

J'espère que le Mr, c'est du 2nd degré, sinon laisse-tomber. D'autant que Mr n'est pas l'abréviation de Monsieur, mais celle de Mister. Pour Monsieur, employer M., et non Mr ;-)

Sinon content pour toi...
J'y ai repensé.
Je vais récrire ma dernière version avec qq idées et voir en quoi mon algorithme différera de celui de cette dernière version parce que je serai sûrement plus lent...
Et je me suis avisé hier soir (tout arrive !) que ton histoire de "familles", je l'avais ébauchée avec 6, en essayant de ramener à la raison le sieur Madjer qui prétendait avoir résolu le pb de la création automatique des premiers alors qu'il ne faisait (mal d'ailleurs) qu'un crible d'Eratosthène...
Je lui avais démontré que si un nombre était premier, il était obligatoirement de la forme 6k+1, ou 6k+5...
En poussant à 30k, si un nombre >30 est premier alors il est de l'une de ces formes : 30k+1, 30k+7, 30k+11... 30k+29 : tout autre 30k+b, étant factorisable, donc non premier...

Attention aux dicos ! Obligatoirement avec accolades...
Les dicos depuis la version Python 3.5 peuvent être ordonnés !
Dans le dico standard, tel celui que j'ai utilisé, tu pourrais écrire
Dico={17:4,7:1,11:2,23:6,13:3,19:5,29:7,1:0}
que ça ne changerait rien...

Je te ferai part de ma version lorsque j'en serai satisfait...

@+

LEG · 03-05-2018 15:56:47

Re Yoshi , le Mr c'est pour te saluer et remercier sur le travail que tu as fait dans ce crible...

Dans le dico standard, tel celui que j'ai utilisé, tu pourrais écrire
Dico={17:4,7:1,11:2,23:6,13:3,19:5,29:7,1:0}
que ça ne changerait rien...

et pourtant c'est là qu'il y a une partie de la solution , afin de cribler la famille 30k + 1 ou P[7;29] que l'on désir cribler, afin d'obtenir les nombres premiers q de la même forme, de n à 2n .

je veux "on veut" cribler les nombres premier q = 30k + 19 de 300 à 600.

on doit donc cribler la famille 30k+11 de 11 à 300

1) il faut donc changer l'ordre de Dico={1:0....,29:7}

car le crible, va cribler dans l'ordre des famille qui lui ont été établi avec p8[1,7.....29]

l'ordre de Dico, devient: Dico={11:0,1:1.....,29:7} peut importe l'ordre de la suite après 11:0...il ne va cribler qu'une famille 30k + n [1;29]

2) il faut donc changer range(8) en (1) de partout où il est sollicité. en commençant par l'initialisation, la ligne:

nombres = [[1 for _ in range(nbcell)] for _ in range(1)]

résultat:
Donnez la valeur de n = 30k : 600
CribleG1_mod30 : Initialisation: 0.0 seconds ---
CribleG1 mod30 : Famille de chaque couple R et Pi: 0.0 seconds ---
CribleG1 mod30 : Criblage des 8 familles: 0.0 seconds ---
CribleG1 mod30 : Extraction des premiers n à 2*n : 0.0 seconds ---
[[0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0]]
On a 8 nombres premiers q, de 300 à 600, tel que 600 -[1] = 30k+19

Tu peux vérifier:
la 4ème cellule la n°3, = 11 + 90 =101 suite arithmétique de raison 30, de premier terme 11....! Et:
600 -101 = 499 ,

"soit 600 se décompose en somme de deux premiers...LoLLL"

C'était vraiment bête....depuis que je cherche .....

regarde ce que donne le crible maintenant pour 9 000 000 000:

Donnez la valeur de n = 30k : 9000000000
CribleG1_mod30 : Initialisation: 14.227225065231323 seconds ---
CribleG1 mod30 : Famille de chaque couple R et Pi: 1.0920019149780273 seconds ---
CribleG1 mod30 : Criblage des 8 familles: 64.38131284713745 seconds ---
CribleG1 mod30 : Extraction des premiers n à 2*n : 22.3392391204834 seconds ---

On a 48272991 nombres premiers--- 30k+19, de 9000000000 à 18000000000.

il est simple à partir de ce crible de vérifier et prouver que la densité de premiers entre n et 2n et en moyenne générale la même est infinie...!
car tout simplement le crible, crible de façon uniforme et identique dans les 8 familles, suivant le principe d'Eratosthène , avec les nombres premiers [tex]P_i\leqslant\sqrt{2n}[/tex]

Donnez la valeur de n = 30k : 12000000000
CribleG1_mod30 : Initialisation: 20.280035495758057 seconds ---
CribleG1 mod30 : Famille de chaque couple R et Pi: 1.6224026679992676 seconds ---
CribleG1 mod30 : Criblage des 8 familles: 88.09335470199585 seconds ---
CribleG1 mod30 : Extraction des premiers n à 2*n : 29.671252250671387 seconds ---
On a 63579183 nombres premiers...30k+19, de 12000000000 à 24000000000 de la forme 3k+1

Et un dernier pour te Saluer: famille 30k+7 pour les nombres premiers q = 30k+23 de la forme 3k-1

Donnez la valeur de n = 30k : 12000000000
CribleG1_mod30 : Initialisation: 19.063233613967896 seconds ---
CribleG1 mod30 : Famille de chaque couple R et Pi: 1.6536030769348145 seconds ---
CribleG1 mod30 : Criblage des 8 familles: 89.10735654830933 seconds ---
CribleG1 mod30 : Extraction des premiers n à 2*n : 29.686851978302002 seconds ---
On a 63579248 nombres premiers

Tu peux même utiliser le compteur de temps pour la densité du nombre de premiers par famille...et faire breveté le principe.....Lolll
la fonction [tex]\pi{(G)}[/tex] qui compte les entiers de 7 à n, non congrus à 2n modulo Pi , vaut lorsque n tend vers + l'infini :[tex]\frac{n}{Ln 2n}[/tex]...

Dernière modification par LEG (03-05-2018 15:58:27)

LEG · 03-05-2018 16:01:33

Je te joint ton crible modifié pour la circonstance :" réglé sur le criblage de la famille 30k+7.

import os

import math

import time

def eratostene(n):

    n = int((2*n)**0.5)

    m = (n-1) // 2

    b = [True]*m

    i = 0

    p = 3

    premiers = [2]

    while p*p < n:

        if b[i]:

            premiers.append(p)

            j = 2*i*i + 6*i + 3

            while j < m:

                b[j] = False

                j = j + 2*i + 3

        i += 1

        p += 2

    while i < m:

        if b[i]:

            premiers.append(p)

        i += 1

        p += 2

    return premiers[3:]

def cribleG1_mod30(n):

    # INITIALISATION

    start_time = time.time()

    nbcell,nn = n//30,n*2

    nombres = [[1 for _ in range(nbcell)] for _ in range(1)]

    p = eratostene(n)

    r = [nn%pi for pi in p]

    p8 = [1,7,11,13,17,19,23,29]

    pfam = []

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

    # pour ne cribler que 2 fam, changer range (8) en 2 , partout.et l'ordre de dico.

    print("CribleG1_mod30 : Initialisation: %s seconds ---" % (time.time() - start_time))

    # FAMILLES POUR CHAQUE Pi

    start_time = time.time()

    for i,pi in enumerate(p):

        pfam.append([0,0,0,0,0,0,0,0])

        j = r[i]

        f=j+pi*29

        incr = pi*2

        d_c = j%10

        #  si la terminaison du reste est paire on ajoute directement pi et on verifie

        if d_c %2==0:

            j += pi

            d_c = j%10

        while j <= f:

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

                fam =Dico[j%30]

                if pfam[i][fam] == 0:

                    pfam[i][fam] = j

            j += incr

            d_c = j%10

            #print(j)

    print("CribleG1 mod30 : Famille de chaque couple R et 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):

        pi=p[i]

        for j in range(1):

            index = ((pfam[i][j] - p8[j])// 30)

            while index < nbcell:

                nombres[j][index] = 0

                index += pi

    print("CribleG1 mod30 : Criblage des 8 familles: %s seconds ---" % (time.time() - start_time))

    # CALCUL DES NOMRES PREMIERS ENTRE n ET 2*n

    start_time = time.time()

    premiers = []

    for i in range(1):

        for j in range(nbcell-1, -1, -1):

            if nombres[i][j] == 1:

                premiers.append(nombres[i][j] == 1)

    print("CribleG1 mod30 : Extraction des premiers n à 2*n : %s seconds ---" % (time.time() - start_time))

    #print(nombres)

    premiers.sort()

    return premiers

n = int(input("Donnez la valeur de n = 30k : "))

nb = len(cribleG1_mod30(n))

print("On a "+str(nb)+" nombres premiers")

os.system("pause")

yoshi · 03-05-2018 17:48:29

Salut,

Voilà, j'ai réalisé mon criblage naïf modèle 8 familles (mon code est très ramassé) et il fonctionne, mais le temps pour n=24000000 est prohibitif : 248 s au total pour 4 s au total pour mon dernier modèle commun...
J'ai donc de quoi phosphorer : pourquoi ton code est-il si rapide ?
La réponse, qui ouvre un grand chantier, est : parce que j'ai beaucoup trop de tours de boucles...

@+

LEG · 03-05-2018 18:51:36

yoshi a écrit :

Salut,
J'ai donc de quoi phosphorer : pourquoi ton code est-il si rapide ?
La réponse, qui ouvre un grand chantier, est : parce que j'ai beaucoup trop de tours de boucles...
@+

c'est presque le temps faut à G1 pour 23 000 000 000....Loll
regarde : je pense que la limite se situe sur mon pc à 24 000 000 000:

il y a beaucoup d'enseignement à en tirer ...Déjà le postulat de Bertrand il y a au moins un nombre premier entre n et 2n, rime à rien...autant dire qu'il y a une goute d'eau dans l'océan...

tu vois que le criblage est linéaire et ce, quelque soit la famille choisie...

pourquoi ce crible est si rapide, déjà il ne travaille que dans des suites arithmétique de raison 30 donc il progresse modulo Pi*30 car si tu regarde le cribleG_(n) qui lui , comme Eratosthène classique, travaille dans l'ensemble des entiers naturels à partir de 1...il progresse modulo Pi...soit 30 fois moins vite...lorsque Pi = 500 000, et ben il fait des sauts de 15 000 000 ...

est que tu positionnes ta limite j < f où f = Pi*29
ton calcul des reste R 2n%Pi à quel moment tu le fais dans le crible...car ça conditionne le temps de criblage .

tu dois : Etape A)
1) limite n ,
2) avoir la liste des Pi < sqrt de 2n ("eratosthène") ou répertoire de donné que le programme va aller chercher en fonction de sqrt de 2n,
3_) ensuite tu as dans l'ordre soit tu établi tes j = ri comme tu l'as fait dans G1 ..mais en prenant au fur et à mesure chaque Pi, puis calule du reste R , calcul des 15j à partir de R +Pi si pair ou R+2Pi si impair..
ensuite teste , position dans sa famille , criblage , retour au j suivant, réitère : teste position criblage...les 8 familles criblées avec ce Pi.
retour au Pi suivant et tu réitères...à la fin comptabilite des [1]

ou:
Etape B)
tu calcules après l'étape 1) et 2)
tous les restes R ce que tu as fait au début dans G1 ...pourquoi ? il te faut à chaque fin de criblage des 8 famille avec Pi aller chercher à nouveau le Pi suivant, et le R suivant....le reste ensuite ne changera pas ..
preuve: regarde les temps linéaires du criblage..

ensuite la vrai raison tu as été bon et tu as bien compris ce que mon crible devait faire et deux têtes pensantes peuvent donner de très bon résultats....preuve ci dessous...

tu as G1, si cela t'amuse dans l'étape A) fait le cacule des R après avoir été chercher Pi, au fur et à mesure du criblage des 8 familles et compare les temps en plus avec G1 tu sélectionne le criblage que d'une famille...

==== RESTART: E:\Documents\conjecture de Goldbach\cribleG1_par Famille.py ====
Donnez la valeur de n = 30k : 23400000000
CribleG1_mod30 : Initialisation: 198.29194831848145 seconds ---
CribleG1 mod30 : Famille de chaque couple R et Pi: 15.92762804031372 seconds ---
CribleG1 mod30 : Criblage des 8 familles: 180.46111679077148 seconds ---
CribleG1 mod30 : Extraction des premiers n à 2*n : 59.264504194259644 seconds ---
On a 120565878 nombres premiers
>>>
==== RESTART: E:\Documents\conjecture de Goldbach\cribleG1_par Famille.py ====
Donnez la valeur de n = 30k : 23700000000
CribleG1_mod30 : Initialisation: 205.35876083374023 seconds ---
CribleG1 mod30 : Famille de chaque couple R et Pi: 17.59683084487915 seconds ---
CribleG1 mod30 : Criblage des 8 familles: 182.567120552063 seconds ---
CribleG1 mod30 : Extraction des premiers n à 2*n : 63.66371178627014 seconds ---
On a 122046948 nombres premiers
>>>
==== RESTART: E:\Documents\conjecture de Goldbach\cribleG1_par Famille.py ====
Donnez la valeur de n = 30k : 23910000000
CribleG1_mod30 : Initialisation: 299.7545266151428 seconds ---
CribleG1 mod30 : Famille de chaque couple R et Pi: 24.13324236869812 seconds ---
CribleG1 mod30 : Criblage des 8 familles: 184.96952486038208 seconds ---
CribleG1 mod30 : Extraction des premiers n à 2*n : 71.94732642173767 seconds ---
On a 123083742 nombres premiers
>>>

LEG · 03-05-2018 18:53:33

yoshi a écrit :

Salut,
Voilà, j'ai réalisé mon criblage naïf modèle 8 familles (mon code est très ramassé) et il fonctionne,
@+

tu n'as pas mis le code...pour qu'on regarde en commun moi le criblage et toit le programme...

yoshi · 03-05-2018 20:06:08

Re,

Bin non, je n'avais pas le mis le code puisque je n'en suis pas satisfait.
Mais le voilà quand même :

fromtimeimporttime

def eratostene(n):

    n = int((2*n)**0.5)

    m = (n-1) // 2

    b = [True]*m

    i = 0

    p = 3

    premiers = [2]

    while p*p < n:

        if b[i]:

            premiers.append(p)

            j = 2*i*i + 6*i + 3

            while j < m:

                b[j] = False

                j = j + 2*i + 3

        i += 1

        p += 2

    while i < m:

        if b[i]:

            premiers.append(p)

        i += 1

        p += 2

    return premiers[3:]

def Crible_mod30(n):

    # INITIALISATION

    start_time = time()

    k_max=2*n//30

    k_min=n//30

    p = eratostene(n)

    max_test=len(p)-1

    total=0

    Ajouts=[1,7,11,13,17,19,23,29]

    K=[k*30 for k in range(k_min,k_max)]

    si=time() - start_time

    print("Initialisation : %s secondes ---" % (si))

    # Tri

    for n1 in K:

        for ajout in Ajouts:

            nb=n1+ajout

            flag=1

            for i,test in enumerate(p):

                if nb%test==0:

                    flag=0

                    break

            if i==max_test and flag:

               total+=1

    sc=time() - start_time

    print("Criblage des 30k+b : %s secondes ---" % (sc)) 

    return total,si+sc

n = 1500000

nbr,tot= Crible_mod30(n)

print ("\n** ",nbr,"nombres trouvés en %s secondes" % tot,"**")

Initialisation : 0.014000892639160156 secondes ---
Criblage des 30k+b : 5.399308919906616 secondes ---

** 102661 nombres trouvés en 5.413309812545776 secondes **

@+

LEG · 03-05-2018 21:19:09

Ben on dirait que tu testes comme Eratosthène modulo P et non modulo P*30 car dans range "range" "il y a une limite de K qui va augmenter"
ligne 8: K=[k*30 for k in range(k_min,k_max)] tu fais l'inverse, c'est à dire que tu prends le nombre de K, qui ensuite seront de la forme nb=30k+ajout , et qu'en fonction de ta liste de Pi, tu va tester ces nb un par un par les P qui ont été énuméré ; à savoir si il sont congru à 2n modulo P si oui (" je suppose flag == 0 donc ce i est transformer en 0, sinon flag == 1 , puis tu continues ta boucle avec i +=1 donc le suivant... et à la fin break tu sorts..") donc tu progresses modulo P...non???

dans notre crible, lorsque P crible, en partant de sa position dans chacune des 8 familles il crible modulo P*30 (additivement), car il compte les cellules donc les [1] par famille...exemple famille 30k+7 je représente sur une ligne :

n= 480. énumération de P = [7;11;13;17;19;23; et 29]

1 ,1 ,1,1,0,1,1,1,1,1,1,0,1,1,1,1,max =15*30 + 7
7 +k*30................................ max= 457

premier test avec P = 7 et son reste R = 1 J = Ri, je progresse j + 2*p ..qui va donner 127. je n'ai fait que des additions sauf pour le calcul du reste R....

Je place 127 = cellule n°4 la 5ème, et à partir de cette position, je compte 7 cellules, je marque la marque d'un 0, terminé pour cette famille avec p =7 .
j'ai bien criblé modulo 210 par addition...! sans faire de division.....!

toi dans cette famille tu testes 16 nombres pour savoir ce qui sont congrus à 2n modulo pi , avec chacun des Pi de ta liste énuméré P énuméré......?
donc 16 divisions dans cette famille....

alors que p= 17.19.23. et 29 ("même 13, dont le reste = 11 sa position serra 11+26=37; donc, position n° 1 et 1+13 marquera la cellule n° 14 point barre , Pi suivant et son R.. sans faire de division...")

les autres ne peuvent en faire aucune puisqu'il n'y a que 16 cellules....! C'est à dire 16 nombres = 30k +7 soit : [7.37.67.97.......457.]

Mais surtout je pense que même en criblant par par Famille ça n'apportera rien...

la ligne

K=[k*30 for k in range(k_min,k_max)]

dans le crible G et une grand importance avec la ligne Dico ={} ou P8 =[]...

Tout ça , sous réserve que j'ai bien interprété le fonctionnement de ton programme....Mais dis moi si tu crible modulo Pi *30....par famille
car si tu cribles les nombres30k + ajout , alors tu ne peux pas cribler modulo Pi*30....!
dort bien....
@+++

j'avais oublié :

Donnez la valeur de n = 30k : 1500000
CribleG6 mod30 : Initialisation: 0.04680013656616211 seconds ---
CribleG6 mod30 : Famille de chaque couple R et Pi: 0.0 seconds ---
CribleG6 mod30 : Criblage des 8 familles: 0.04680013656616211 seconds ---
CribleG6 mod30 : Extraction des premiers n à 2*n : 0.04680013656616211 seconds ---
On a 102661 nombres premiers

0+0+0+0 '' = 0'',1 10ème . Va à 23 mds ...LoLLLL

et pour la famille 30k+7 :

Donnez la valeur de n = 30k : 1500000
CribleG1_mod30 : Initialisation: 0.0 seconds ---
CribleG1 mod30 : Famille de chaque couple R et Pi: 0.015599966049194336 seconds ---
CribleG1 mod30 : Criblage des 8 familles: 0.031200170516967773 seconds ---
CribleG1 mod30 : Extraction des premiers n à 2*n : 0.0 seconds ---
On a 12827 nombres premiers

Dernière modification par LEG (04-05-2018 11:14:34)

LEG · 04-05-2018 11:48:58

Je na sais pas si vraiment tu as compris que dans le CribleG1..ou..6 ,

On ne fait au Max, pour les 8 Familles, 16 divisions par Pi, afin de positionner j = Ri dans une des 8 familles le reste ensuite c'est à dire le criblage c'est du comptage principe Eratosthène mais par Famille, donc obligatoirement modulo Pi*30 ie, modulo P par familles...!
Dans cet Ex ci dessous , le minimum serait 14 divisions , si les deux dernier j serait 3m ou 5m ...

On ne tient pas compte des Restes pairs
Prenons au pif un reste R = 1 et son Pi = 7 et criblons au fur et à mesure les j != D-c == 5,
Donc avec D_c = [1,3,7,9] et D_c == 5 "serra sauté" on passe au suivant

puis on teste %9 sachant que :

["les 4 familles 3k+1, %9 == {1,4,7} donc P8 ou Dico = (1,7,13,19) ]

[et les 4 familles 3k-1 %9 == {2,5,8} donc P8 ou Dico = (11,17,23,29)]

De ce fait les multiples de 3 ne peuvent pas être pris en compte sans avoir déjà besoins de faire les 16 divisions par 3....

je peux énumérer les 15j puis retourner au début et tester..ce n'est pas une obligation car je peux le faire au fur et à mesure..

Ri = J

1, %9 = 1 famille 30k+1 " sous réserve" flag == 0, j est positionné dans P8 =1, je mod P = 7 additivement , puis retour à j suivant

15 d_c== 5 j suivant

29 %9 = 2 famille 30k+29 = 29 " sous réserve" flag == 0; j est positionné dans P8 =29, je crible P = 7, puis j suivant

43 %9 = 7 famille 30k+13 ("flag == 0; j est positionné dans P8 =29, je crible P = 7, puis j suivant)

57 %9 = 3m j suivant

71 %9 = 8 famille 30k+ 11 ("flag == 0; j est positionné dans P8 =11, je crible P = 7, puis j suivant)

85 D_c == 5 m suivant

99 %9 = 3m suivant

113 %9 = 5 famille 30k+23 ("flag == 0; j est positionné dans P8 =23; je crible P = 7, puis j suivant)

127 %9 = 1 famille 30k+7 ("flag == 0; j est positionné dans P8 =7; je crible P = 7, puis j suivant)

141 %9 = 3m suivant

155 D_c == 5 suivant

169 %9 = 7 famille 30k+19 ("flag == 0; j est positionné dans P8 =19, je crible P = 7, puis j suivant)

183 %9 = 3m suivant

197 %9 = 8 famille 30k+17 ("flag == 0; j est positionné dans P8 =29, je crible par addition mod P = 7.. Break
-------fin,
je retourne à la liste P et je réitère ....

fin des tests, comptabilité des "flag== 1" ou des nbcell=[1]...!

Dernière modification par LEG (04-05-2018 12:00:17)

yoshi · 04-05-2018 12:39:47

Salut,

Je na ,,sai,s pas si vraiment tu as compris que dans le CribleG1..ou..6 ,

L'art d'enfoncer les portes ouvertes...
Je t'ai toujours dit que je n'étais intervenu dans ton programme qu'au niveau de la technique et que j'allais devoir me pencher sur le fond.
La seule façon de plonger était d'écrire ma propre version. J'ai annoncé un procédé naïf...
Naïf, mais logique, quand même.
J'ai chargé l'ensemble des $P_i$ que j'allais utilisr : tous [tex]\leqslant \sqrt{2n}[/tex].
Ensuite, étant donné qu'une condition nécessaire pour qu'un nombre nb tel [tex]n<nb<2n[/tex] est qu'il soit un multiple de 30, plus 1, 7,11, 13, 17, 19, 23 ou 29, je teste un un par les restes de ces nombres (30k+b) avec chacun des $P_i$, je sors de la boucle dès que l'un des restes est nul et je mets mon drapeau (flag) à 0.
Si aucun reste n'est nul et que j'ai effectué toutes les divisions, alors, j'incrémente le nombre de premiers de 1.
Mon système marche mais est bien trop lent.
J'ai employé le qualificatif de prohibitif...

Ce qui prouve que le procédé est peut-être logique mais pas optimisé du tout...
C'est là que tu interviens et ce qui m'intéresse est le pourquoi : si je connais la réponse au pourquoi, le comment, j'en fais mon affaire...

Donc allons-y et t'es pas sorti de l'auberge.

on ne fait que 8 divisions par Pi, afin de positionner j = Ri dans une des 8 familles le reste ensuite c'est à dire le criblage c'est du comptage principe Eratosthène mais par Famille, donc obligatoirement modulo Pi*30...!

Ce n'est fondamental pour toi, que parce que tu maîtrises ton algorithme...
Pour moi, c'est une phrase creuse...

1. Appelons un chat un chat
a) Qu'est-ce que Pi ? Ce que moi j'ai noté pi soit p['i] dans ton prog ?
J'ai une habitude : je fais commencer les listes par des majuscules et les nombres par des minuscules (ce n'est pas standard, c'est un choix personnel... Je vais d'ailleurs modifier le nom de ma variable b en ajout en minuscules...
b) Il est recommandé par contre d'utiliser des noms "transparents", alors j=Ri, hein...
Que représente j exactement ? Qu'appelles-tu Ri ? je dois me reporter au dernier "programme commun" ? R=[nn%pi for pi in p] ?
c) afin de positionner j = Ri dans une des 8 familles. Tes 8 familles regroupent les nombres du type 30k+1, 30k+7, 30k+11... 30k+29

2. Procédé
a) Si effectivement ton R =[nn%pi for pi in p], cela veut dire que
pour n=1500, on a, avec tes notations :
p=[7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]
et
r (ou R ?) =[4, 8, 10, 8, 17, 10, 13, 24, 3, 7, 33, 39, 32]
r est l'ensemble des restes de 3000 dans la division avec chacun des p['i]... Je ne m'étais jamais posé de questions de fond.
Et ce sont ces restes que tu traites l'un après l'autre via la variable j et que tu incrémentes de incr=29*p['i] à chaque tour jusqu'à être supérieurs à la limite f = j+29*p['i]...
Donc pour j=4 : 4 est pair, tu corriges en j=4+7=11 (oui, 3000%7=4) mais pourquoi ? pourquoi pas une autre valeur multiple de 7 ?
Quelle est la "philosophie" qui sous-tend ça ?
Puis tu testes 11 : ni congru à 0 mod 3 ni mod 5... Tu traites..
Puis que tu aies traité ou non, tu passes j de 11 (ou autre) à 11 + incr, Pourquoi augmenter de cette valeur précisément ?

b) Prenons "au pif" un reste R =1 et son Pi =7.... Pour quelle valeur de n ?
Parce que pour n =1500, aucun des r['i] ne vaut 1...

Ri = J
1, %9 = 1 famille 30k+1
15 %9 =6
29 %9 = 2 famille 30k+29 = 29

Et ce 9, tu le sors d'où ?
1%9 = 1 famille 30k+1 là je me dis, pourquoi pas ?
Et arrive
29 %9 = 2 famille 30k+29 = 29 Ah ????....

Et voilà pfam :
[[151, 67, 11, 193, 137, 109, 53, 179], [151, 217, 41, 283, 107, 19, 173, 239], [361, 127, 101, 283, 257, 49, 23, 179], [331, 127, 161, 433, 467, 229, 263, 59], [511, 397, 131, 283, 17, 169, 473, 359], [631, 217, 401, 493, 677, 79, 263, 539], [361, 187, 71, 13, 767, 709, 593, 419], [241, 427, 551, 613, 737, 799, 923, 179], [151, 817, 521, 373, 77, 1039, 743, 299], [991, 7, 581, 253, 827, 499, 1073, 89], [721, 1237, 1151, 463, 377, 979, 893, 119], [1261, 697, 791, 133, 227, 979, 1073, 509], [721, 1357, 191, 403, 827, 1039, 1463, 509]]

Les restes mod p['i] de tous les éléments de chaque pfam['i] sont
pfam[0] tous = 4 (r[0])
pfam[1] tous = 8 (r[1])
pfam[2] tous = 10 (r[2])
...
pfam[11] tous = 39 (r[11])

Au passage j'ai relevé un doublon : 361 figure dans pfam[2] et dans pfam[6]

Bon, je crois vraiment que je vais devoir suivre le conseil que je t'ai donné et ressortit ton fichier Excel pour suivre pas le programme manœuvre après manœuvre bêtement comme une machine, parce que j'en reviens à vouloir savoir le pourquoi... Tant que je n'ai pas intégré la pourquoi, le comment que j'ai sous les yeux me paraît arbitraire alors qu'il ne l'est pas...

Je vais voir comment j'arrange mon après-midi...

@+

PS : je n'avais vu ta modif de 11 h 00 17

Dernière modification par yoshi (04-05-2018 12:43:47)

LEG · 04-05-2018 16:08:42

Ok : J'ai chargé l'ensemble des Pi que j'allais utilisrr : tous ⩽√2n.
1) n<nb<2n ok nb = 30k+b et tu vas tous les tester avec P_i ce que j'ai bien suivi...

2)

Si aucun reste n'est nul et que j'ai effectué toutes les divisions, alors, j'incrémente le nombre de premiers de 1

Ca veut dire que tu prends le nombres premier P_i suivant, exemple: le 1er =7, suivant = 11 [......P_i ⩽√2n]

a) Qu'est-ce que Pi ? Ce que moi j'ai noté pi soit p['i] dans ton prog ? le même premier que toi, ci-dessus...(7 ,11....P_i ⩽√2n

b)

alors j=Ri, hein...
Que représente j exactement ? Qu'appelles-tu Ri ? je dois me reporter au dernier "programme commun" ? R=[nn%pi for pi in p] ?

R_i c'est le reste R tel que R=[nn%pi for pi in p] , qui ensuite est augmenté de P_i si R est pair; il devient j = R_i , Si R est impair augmenté de 2*P_i il devient donc aussi j = R_ij..

c)

afin de positionner j = Ri dans une des 8 familles.

oui dans une des 8 Familles arithmétique de raison 30 , de premier Terme: 1 ou P_i[7;29] soit : dans le programme P8 [1,7,11,13,17,19,23,29] ou dans ton Dico = {1:0,...,29:7}

on positionne ce j = Ri pour indiquer la position de départ du crible avec son P_i par famille et pour les 8 Familles ...
puis on passera au couple P_i et R suivant soit p=11 et R=8, et la liste des (j = r['i]) <= f.
.

pour n = 1500 p= [7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53] ok

pour n = 1500 :r (ou R ?) =[4, 8, 10, 8, 17, 10, 13, 24, 3, 7, 33, 39, 32] ok
qui ensuite vont être utilisés ; sont augmenté de P_i si pair ou 2P_i si impair, les fameux j

 j = r['i]

        f=j+pi*29

        incr = pi*2

r est l'ensemble des restes de 3000 dans la division avec chacun des p['i]... Je ne m'étais jamais posé de questions de fond.

Oui

Et ce sont ces restes que tu traites l'un après l'autre via la variable j et que tu incrémentes de incr=29*p['i] à chaque tour jusqu'à être supérieurs à la limite f = j+29*p['i]...

oui. et non , car j est incrémenté de 2*P_i jusqu'à la limite f qui vaut j+ P_i*29 ; c'est à dire le premier j tel que R +P_i bien sûr afin de les positionner dans P8[...]

ci dessous : j += incr et incr = 2*P_i

  while j <= f:

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

                fam =Dico[j%30]

                if pfam[i][fam] == 0:

                    pfam[i][fam] = j

            j += incr

cela te donnera 16 j <= f au maximum et pour chaqueP_i.

Ce qui répond à ta question ci-dessous :

Donc pour j=4 : 4 est pair, tu corriges en j=4+7=11 (oui, 3000%7=4) mais pourquoi ? pourquoi pas une autre valeur multiple de 7 ?
Quelle est la "philosophie" qui sous-tend ça ?
Puis tu testes 11 : ni congru à 0 mod 3 ni mod 5... Tu traites..
Puis que tu aies traité ou non, tu passes j de 11 (ou autre) à 11 + incr, Pourquoi augmenter de cette valeur précisément ?

dans l'ordre R = 4 et non j je corrige pour que R + 7 , devienne le 1er j = 11 pour ce Pi =7 , que je vais incrémenter
de 2Pi jusqu'à f = 11 + 7*29 = 214...
mais pourquoi ? pourquoi pas une autre valeur multiple de 7 ? Mais pour Positionner le départ de 7 dans chacune des 8 Famille de P8...! car c'est 7 qui va cribler pas j , J donne la position de départ de 7 dans chaque famille..

tu passes j de 11 (ou autre) à 11 + incr, Pourquoi augmenter de cette valeur précisément ?
car il te faut bien les 8 positions de départ de 7 , dans les 8 familles , donc il te faut les 8 j que tu obtiens par incrémentation < 214 = f (" et ce pour chaque P_i qui criblera")

Puis tu testes 11 : ni congru à 0 mod 3 ni mod 5... Tu traites.. je testes car il faut bien que j=11, soit placé dans sa bonne Famille = 11 ('"modulo 30 additivement") et ("selon cette fonction ci de-dessous en principe:")
ceci correspond dans l'algorithme à :
(11 - 11) // 30 == 0 d'où position de 7 cellule n° 0, famille 11 car le quotient == 0 ; ou si j = 11%30 == 0 soit dans Dico={11:2} la 3ème famille , quotient ==0, position de 7 nbcell n° 0 cette cellule =[1] se transforme en [0];
P_i = 7...va donc cribler cette famille , en marquant toutes les 7 cellules [1] en [0] criblage modulo 7 additivement....
on passe au j suivant , que l'on teste...etc.
une fois les 8 familles criblées on passe à P_i =11 qui est le suivant et on réitère tout {" le R les 16j les 8 criblage des 8 familles...) la

 fam =Dico[j%30]

                if pfam[i][fam] == 0:

                    pfam[i][fam] = j

(" je crois que j'ai détaillé à la page 3, la progression de j , il positionne 7, et 7 part cribler "sans oublier de transformer les [1] en [0] ")

_{b) Prenons "au pif" un reste R =1 et son Pi =7.... Pour quelle valeur de n ?}
Peu importe, c'est un exemple, qui montre comment on traite les j , à qu'elle famille ils seront affecté, pour : en fonction du quotient où "autre méthode" indiquer la position de P_i dans les 8 familles afin que P_i crible ses 8 familles , puis passer au P_i suivant...

Et ce 9, tu le sors d'où ? je l'ai sorti de ma poche "en réserve"
1%9 = 1 famille 30k+1 là je me dis, pourquoi pas ? bien vue
Et arrive
29 %9 = 2 famille 30k+29 = 29 Ah ????....

tu n'as pas tout lu !!! la forme 3k-1, sont les 4 familles {11,17,23,29} qui modulo 9 auront pour reste {2,5 ou 8) ou plus simple additionne les chiffres d'un nombres jusqu'à sa dernière D_c, ex: 29 = 2+9 = 11 ,1+1 = 2,
ou chaque fois que tu obtient 9 soit 0%9 tu annules le 9; d'où 29 = D_c == 2. donc famille 29 [30] car il se termine par 9 si cela avait eu pour reste {1,4 ou 7} et bien cela aurait été la famille 19[30] (principe de la preuve par 9 ..
{"Oubliée depuis des lustres. que j'utilise toujours de tête"}

je te répond pour la fin de ton post @+

LEG · 04-05-2018 17:29:37

1)

Les restes mod p['i] de tous les éléments de chaque pfam['i] sont
pfam[0] tous = 4 (r[0])
pfam[1] tous = 8 (r[1])
pfam[2] tous = 10 (r[2])
...
pfam[11] tous = 39 (r[11])

tu calcules les restes de tous ces éléments par les 13 Pi.. mais que veut dire tous = 4 , 8, 10..
je suppose que (r[0]) sont des N° d'ordre...?

P8 =[1,7,11,13,17,19,23,29]

comment à tu exactement obtenue ces nombres ?, Un exemple avec un élément de pfam == 151 :

pour éliminer les 3m et les 5m, de la liste pfam, qu'ensuite, tu vas tester pour savoir si il sont congrus à 2n modulo Pi donc marqué [0] à la place de [1] dans le programme commun..il y en a 50 par famille, maxi - min = 100 - 50 = 50 testes * 13

tu auras donc 104 éléments ensuite à tester , au lieu 195...mais combien à tu fais de divisions pour supprimer les 3m et les 5m...?
Car à ce stade tu n'as pas encore criblé... Mais on sait que ces 104 éléments tu vas en avoir besoin pour les positionner dans leur famille respective afin de cribler à partir de ces 104 élément.. et si j'ai compris, ensuite tu vas cribler comment (comme modulo Pi additivement par famille avec les 13 Pi....

pfam =

[151, 67, 11, 193, 137, 109, 53, 179], avec Pi == 7; le reste de 3000 % 7 == 4, 4+7 = 11 et + incr jusqu'à 7*29..== pfam ;cribleG6

.........................................> 151%9 == 7, dans P8 [1] à la position 5 (" 1+5+1 = 7, famille 1 et 150/30 = 5") criblage mod Pi...
.........................................> 67 %9 == 4, dans P8 [7] à la position 2 (" 6+7=13, 1+3= 4,famille 7 et 60/30 = 2") criblage mod Pi

.........................................> 179 %9 == 8, dans P8 [29] à la position 5 (" 1+7 = 8, famille 29 et 150/30 = 5") criblage mod Pi..fin

pfam suivant , on réitère...

[151, 217, 41, 283, 107, 19, 173, 239] : avec 11

[361, 127, 101, 283, 257, 49, 23, 179], :avec 13
[331, 127, 161, 433, 467, 229, 263, 59]
[511, 397, 131, 283, 17, 169, 473, 359]
[631, 217, 401, 493, 677, 79, 263, 539],
[361, 187, 71, 13, 767, 709, 593, 419]
[241, 427, 551, 613, 737, 799, 923, 179]
[151, 817, 521, 373, 77, 1039, 743, 299],
[991, 7, 581, 253, 827, 499, 1073, 89]
[721, 1237, 1151, 463, 377, 979, 893, 119]
[1261, 697, 791, 133, 227, 979, 1073, 509]
[721, 1357, 191, 403, 827, 1039, 1463, 509]

je pense que mon fichier excel va te prendre la tête si tu veux je t'envoie le nouveau lien fichier Word si les explications ci-dessus et le post ci-dessus, ne t'on pas convaincu..Ce qui maintenant, m'étonnerait @ toi...

Dernière modification par LEG (04-05-2018 18:33:17)

yoshi · 04-05-2018 18:15:21

RE,

Avec n=1500...
Je démarre ma boucle
i=0 --> p[0]=7 et r[0]=4.
limite (f) =4+7*29=207
incr = 7*2 =14
j=4
j%2=0 ?
oui donc j=4+7=11 (j forcément impair à partir de maintenant --> d'où test avant while)
j<=207 ?
oui --> test: j%3!=0 et j%5!=0 ? Oui --> j%30 =11 --> Dico[11]=2 alors pfam[0][2]=11 et on passe au j suivant : j+14=25

j<=207 ?
oui --> test : j%3!=0 et j%5=0 ? Non ! --> j=25+14=39

j<=207 ?
oui --> test : j%3!=0 et j%5=0 ?Non --> j=39+14=53

j<=207 ?
oui --> test : j%3!=0 et j%5=0 ? Oui --> j=39+14=53 --> j% 30 = 29 --> Dico[27]=7 d'où pfam[0][7]=53
C'est vu...

j%2 on incrémente de 7 et on trouve un impair,
Une fois qu'on a un impair, il faut incrémenter avec un pair(7*2) pour que la somme reste impaire et que dans les deux cas le j obtenu soit congru à 4 modulo 7, tout comme le j du départ
ok !
Je vois 7 parce que c'est p[0] et qu'on est parti de r[0]...
J'ai constaté que pour n=1500 le f maximum était de 1569... Je l'attendais proche de 3000 : si le maxi est 1569 et que j <=1569, alors tous les éléments de pfam sont<=1569... Ce qui est vérifié... Pourquoi une limite aussi basse ?
Que représentent donc ces nombres de pfam ? ils sont 104... Et c'est à partir de ces 104 (doublons inclus : j'en ai trouvé 3) que ton prog arrive à trouver 191 nombres premiers ??!...
Ça, c'est fort... Mais c'est un autre épisode...
Déjà, celui-là me pose beaucoup de questions...

Donc tu répartis tous les j obtenus en 13 (il y a 13 $P_i$ et donc 13 $R_i$) groupes de 8, chaque nombre en position de 0 à 7 à partir d'un j de base = r['i] pour i de 0 à 12 (inclus), lesquels $R_i$ sont les restes de 3000 dans la division par les $P_i$...
Es-tu capable de justifier que, quel que soit le n choisi multiple de 30, tu obtiendra toujours le bon nombre de premiers entre n et 2n ?
Je l'ai vérifié sur pas mal d'exemples, mais en bon matheux, je sais que ça ne constitue pas une preuve...

C'est toutes manipes que tu désignes par "Familles pour chaque $P_i$"

Hmmm... Cet algorithme est entièrement de toi ou bien l'as-tu pêché qq part ?
Parce que ça m'en bouche un coin !!!

@+

[EDIT]

tu calcules les restes de tous ces éléments par les 13 Pi.. mais que veut dire tous = 4 , 8, 10..

ça :

[151, 67, 11, 193, 137, 109, 53, 179] reste attendu : 4
4 4 4 4 4 4 4 4
[151, 217, 41, 283, 107, 19, 173, 239] reste attendu : 8
8 8 8 8 8 8 8 8
[361, 127, 101, 283, 257, 49, 23, 179] reste attendu : 10
10 10 10 10 10 10 10 10
[331, 127, 161, 433, 467, 229, 263, 59] reste attendu : 8
8 8 8 8 8 8 8 8
[511, 397, 131, 283, 17, 169, 473, 359] reste attendu : 17
17 17 17 17 17 17 17 17
[631, 217, 401, 493, 677, 79, 263, 539] reste attendu : 10
10 10 10 10 10 10 10 10
[361, 187, 71, 13, 767, 709, 593, 419] reste attendu : 13
13 13 13 13 13 13 13 13
[241, 427, 551, 613, 737, 799, 923, 179] reste attendu : 24
24 24 24 24 24 24 24 24
[151, 817, 521, 373, 77, 1039, 743, 299] reste attendu : 3
3 3 3 3 3 3 3 3
[991, 7, 581, 253, 827, 499, 1073, 89] reste attendu : 7
7 7 7 7 7 7 7 7
[721, 1237, 1151, 463, 377, 979, 893, 119] reste attendu : 33
33 33 33 33 33 33 33 33
[1261, 697, 791, 133, 227, 979, 1073, 509] reste attendu : 39
39 39 39 39 39 39 39 39

[721, 1357, 191, 403, 827, 1039, 1463, 509] reste attendu : 32
32 32 32 32 32 32 32 32

Dernière modification par yoshi (04-05-2018 18:37:21)

LEG · 04-05-2018 20:24:46

Es-tu capable de justifier que, quel que soit le n choisi multiple de 30, tu obtiendra toujours le bon nombre de premiers entre n et 2n ?

c'est trivial est nul besoins de démonstration, car cela revient à dire que si c'était faux il en serait de même du crible d'Eratosthène de 1 à n et si tu veux de 7 à N dans les 8 familles de nos cribles..
ces cribles sont de moi , je les ai construit sur le principe d'Eratoshène
Eratosthène rappel : Pi <= sqrt de n ; je part de 2, je marque les mulitples de 2 tous les deux nombres puis 3, n'est pas marqué donc premier, je barre les mulitples de 3, tous les trois nombres...5 n'est pas marqué, donc premiers , je marque les 5m tous les 5 nombres...etc jusqu' sqrt de n

Et tu me demandes si j'ai bien barré tous les multiples de Pi, et si les nombres barrés sont bien des nombres premiers...tu connais la réponse en bon Matheux sans avoir besoin de démonstration depuis + de 2000ans

je peux le faire dans les 8 suites arithmétique modulo30, de premier terme P8[1.7.11.13.17.19.23.29] crible que j'ai construit [nbpremier win] il y a deux méthodes celle que j'utilise dans le cribleG6 ou Eratosthène mod30, par famille..!

cribleG_(n) de 1 à n; principe d'Eratosthène ...idem: Pi <= sqrt de 2n, je part de R qui est les reste de 2n% Pi Pi[2,3,5,7...sqrt 2n]
j'ai la liste des R et leurs Pi R(0) et Pi(0) ; R(1) et Pi(1)....

je part du premier reste R(0) que j'ai positionné dans la liste des entier de 1 à n , et la peux importe que R soit pair ou impair...
n=1500 R(0) ==0 Pi(0) ==2 je part donc de 2 et je barre tous les congruents à 2, tous les deux nombre ....> n ("comme Ri= 0, cela revient à barrer les multiples de 2 qui seront tous congrus à 2n modulo 2...!")

R(1) == 0 et Pi(1)==3, idem je part de 3 et je barre tous les cogruent à 3 tous les trois nombres, qui sont les mutiples de 3 ...> n.

R(2) ==0 et Pi(2) ==5 idem tu connais Eratosthène.....> n tu vas me demander si j'ai bien barré les entiers congrus à 2,2 et 5 jusqu'à n.?? où Eratosthène est faux..?

R(3) == 4; et Pi(3) == 7 et bin je part de 4 et je marque tous les congruents à 4 modulo 7, tous les 7 nombres....>n ("pour faire simple j'appelle ces entiers congruents de Pi==7")

R(4) == 8; et Pi() == 11 et bin je part de 8 et je marque tous les congruents de 11, tous les 11 nombres....>n

tu as compris ou je continue jusqu'à 53...Je pense que c'est inutile et que l'évidence n'a aucun besoin de démonstration à moins de dire que Eratosthène est faux depuis >2000ans...

Donc tu me demandes en bon matheux, si les [1] qui ne sont donc pas barrés, ("car les barré sont les [0]") sont bien et ce quelque soit n choisi, constitus les nombres premiers q de n à 2n ; tel que 3000 -[1] == q premier pour cet exmple et bien entendu quelque soit n, comme Eratosthène qui donnera tous les entiers qui ne seront pas barré [1] les nombres premiers >1 jusqu'à n quelque soit n ....> vers l'infini...!

Ou Alors tu penses que dans tous tes pfam, en fonction de leurs P_i , il y en aurait : qui ne sont pas congrus à R (modulo Pi)...Je peux te garantir que tous tes pfam son bien congrus à 3000 [Pi] preuve ci-dessus...!

Tu as quand même remarqué, que dans le crible G(n) on utilise 1 car si 1 est marqué [0] 2n - 1 ne peut être un nombre premier...

Comme tout ce qui touche au crible d'Eratosthène et qui ont été prouvé, il en est de Même du CribleG , autrement dit:
la fonction du TNP qui dit que [tex]\pi{(n)}[/tex] vaut (n / ln n) lorsque n....> vers + l'infini , ce qui caractérise le crible d'Eratosthène;

Il en serra de même du cribleG, mais étant donné que l'on utilise les [tex]P_i\leqslant\sqrt{2n}[/tex] la fonction [tex]\pi{(n)}[/tex] devient [tex]\pi{(g)}[/tex] et le corollaire du TNP devient :[tex]\pi{(g)}[/tex] vaut (n / ln 2n) lorsque n....> vers + l'infini , ce qui caractérise le cribleG_(n) en réfèrence à Goldbach..... et le postulat de Bertrand ....je leur laisse, car inutile...!

Cher Yoshi sur ce, bonne nuit @+ demain il fera beau...et on verra la suite de ton algo ...

Dernière modification par LEG (04-05-2018 20:38:48)

yoshi · 04-05-2018 21:24:34

Bonsoir,

Non, je n'ai encore pas formulé de pourquoi pour le dernier épisode...
J'ai assez de sujets de réflexion avec la partie centrale qui me préoccupe.

si le maxi est 1569 et que j <=1569, alors tous les éléments de pfam sont<=1569... Ce qui est vérifié... Pourquoi une limite aussi basse ?
Que représentent donc ces nombres de pfam ? ils sont 104...

Cela fait deux questions, j'espère deux réponses...

En tout cas, toutes mes félicitations, je suis admiratif : j'aurais été bien incapable de trouver un truc pareil...
Et pourtant, j'en ai vu et écrit des "algos tordus"...
D'autant que 1569, c'est à peine supérieur à 1500.
Je pourrai donc dans l'avenir penser à la façon de récrire la partie centrale même s'il n'est pas du tout évident que ce soit possible (en plus rapide, même si ça l'est déjà pas mal !), puis la dernière partie...
Bah : il n'est pas nécessaire d'espérer pour entreprendre, ni de réussir pour persévérer... Guillaume d'Orange, dit "le taciturne".

@+

LEG · 05-05-2018 06:28:21

Bonjour Yoshi:
pour les deux réponses c'est bon..., car il te suffit de calculer tes 13, pfam < = 1500.

Comme je ne sais pas "encore" comment ton programme va cribler ensuite, à partir de pfam(0) , R =4 , et avec Pi = 7,: il te faut cribler modulo 210 = Pi*30; le reste de tes entiers congru à 3000 [7]. C'est à dire, le programme ajoute aux 8 valeurs de pfam(n) Pi *30, et pour chacune de tes 13 pfam... ok...

("ce que je faisais avec excel, dans les tableaux que je joins, en dessous de ta citation") :

[151, 67, 11, 193, 137, 109, 53, 179] reste attendu : 4
............ 4 , 4, 4, 4 , 4 , 4 , 4 , 4

tableau excel: crible des congruent de 7, modulo 210 pour pfam(0) <= 1500

P8 = 1 7 11 13 17 19 23 29 Pi = 7 R=4

pfam(0)=..+ (Pi*30 = 210)

.....[151 , 67 , 11 , 193 , 137 , 109 , 53 , 179]
361 277 221 403 347 319 263 389
571 487 431 613 557 529 473 599
781 697 641 823 767 739 683 809
991 907 851 1033 977 949 893 1019
1201 1117 1061 1243 1187 1159 1103 1229
1411 1327 1271 1453 1397 1369 1313 1439
[..................1481........................................] limite n= 1500

tableau excel: crible des congruent de 11, modulo 330 pour pfam(0) <= 1500

P8 = 1 7 11 13 17 19 23 29 Pi = 11 ,R = 8

pfam(1) + (Pi*30 = 330)

[151 217 41 283 107 19 173 239
481 547 371 613 437 349 503 569
811 877 701 943 767 679 833 899
1141 1207 1031 1273 1097 1009 1163 1229
1471 ...... 1361 ..... ..1427 1339 1493 ....... ] limite n= 1500

dans ton programme une fois pfam(n) établi, tu programmes pour qu'à partir de pfam(n) il ajoute P_i *30 wile <= 1500; d'où il criblera modulo Pi*30 additivement, pour les 13 P_i et les 13 pfam...ça va déménager...Lolll

Cela évite de compter les cellules, par famille modulo P_i, afin de changer les cellule [1] en [0] qui sont les congruents de P_i...Valeurs que tu n'auras plus qu'à compter, pour connaître le nombre de premiers de n à 2n.

Avantage, tu soustraits ces valeurs à 3000 et tu à les nombres premiers q, sans avoir à les reconstruire à partir d'une cellule [1] ce que tu peux programmer en fin de programme ...et il te sort directement les nombres premier q ....("tu as les p et les q"..bon je sort..)

Inconvénient, les valeurs prenne plus de mémoire que les 1...

Pour info , il y a une méthode mais qui doit être ch...., à programmer , c'est de copier le masque des Pi cellules et de le recopier Pi ligne en dessous pour les 8 colonne jusqu'à la limite de la dernière ligne (50 pour n=1500) "c'est ce que je fais dans excel manuellement ça évite de compter..."...

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

Forum de mathématiques - Bibm@th.net

#126 02-05-2018 13:52:45

Re : crible en python

#127 02-05-2018 14:34:29

Re : crible en python

#128 02-05-2018 15:54:22

Re : crible en python

#129 02-05-2018 16:53:40

Re : crible en python

#130 02-05-2018 17:28:33

Re : crible en python

#131 02-05-2018 18:00:48

Re : crible en python

#132 02-05-2018 20:50:15

Re : crible en python

#133 02-05-2018 22:08:53

Re : crible en python

#134 03-05-2018 11:19:14

Re : crible en python

#135 03-05-2018 12:52:35

Re : crible en python

#136 03-05-2018 15:56:47

Re : crible en python

#137 03-05-2018 16:01:33

Re : crible en python

#138 03-05-2018 17:48:29

Re : crible en python

#139 03-05-2018 18:51:36

Re : crible en python

#140 03-05-2018 18:53:33

Re : crible en python

#141 03-05-2018 20:06:08

Re : crible en python

#142 03-05-2018 21:19:09

Re : crible en python

#143 04-05-2018 11:48:58

Re : crible en python

#144 04-05-2018 12:39:47

Re : crible en python

#145 04-05-2018 16:08:42

Re : crible en python

#146 04-05-2018 17:29:37

Re : crible en python

#147 04-05-2018 18:15:21

Re : crible en python

#148 04-05-2018 20:24:46

Re : crible en python

#149 04-05-2018 21:24:34

Re : crible en python

#150 05-05-2018 06:28:21

Re : crible en python

Réponse rapide

Pied de page des forums