Bibm@th

Forum de mathématiques - Bibm@th.net

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

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

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

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

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

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

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

Re : crible en python

Re,

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

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

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

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

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


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

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

Dernière partie S4 inchangée...

Normalement, tu as du grain à moudre...

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

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

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

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

Re : crible en python

re bonsoir

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

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

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

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

d'où attention à la modification de :

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

fam , Dico(j%30) donne le reste,et q; = Dico(1%30) donne Dico{1:0} soit P8 [1] et en récupérant le quotient , on a le début d'index = Dico{1:0} on continu , on part cribler par pas de Pi = 7; de 9 > à 8 dans ton exemple, ...etc
Ou tout simplement, mettre début d'index dans pfam de 0 à 7 à la place des j, de 0 à 7 et passer à la phase 3 criblage, ce qui supprime la division ; : ce passage:
for j in range(8):
            debut_index=(Pf[j]-P8[j])//30.

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

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

Dernière modification par LEG (13-05-2018 16:33:45)

Hors ligne

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

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

Re : crible en python

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

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

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

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

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

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

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

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

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

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

En Conclusion, le crible de Goldbach, à les mêmes propriété qu le crible d'Eratosthène, de n à 2n , c'est un corollaire du T.N.P et du T.F.A,
d'où un entier naturel > 0, peut être congru de façon unique à l'ordre près de ses facteurs...
le nombre minimum de nombres premiers de $n$ à $2n$ , pour $n = 210$ est $39$, plus généralement pour $n$ de la forme de $30k$ et $ n \geqslant {210}$ vaut lorsque n tends vers + l'infini ,$\frac{n}{Ln 2n}$

Dernière modification par LEG (13-05-2018 06:34:15)

Hors ligne

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

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

Re : crible en python

Salur,

Je rentre HS...
Je verrai demain

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

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

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

Re : crible en python

Bonsoir,

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

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

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

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

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

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

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

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

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

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

Re : crible en python

yoshi]Bonsoir, Re

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

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


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

oui

pour mettre des 0, dans la liste nombres.

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

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

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


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

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

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

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

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

Si rien n'est évident,

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

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

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

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

@+

Hors ligne

Réponse rapide

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

E-mail (obligatoire)

Message (obligatoire)

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

Quel est le résultat de l'opération suivante ?17 + 31
Système anti-bot

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

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

Pied de page des forums