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

Répondre

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 ?64 - 51
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.

Retour

Résumé de la discussion (messages les plus récents en premier)

LEG
Aujourd'hui 15:22:24

Bonjour
j'ai laissé tourner un peu le cribleG4Y pour n = 29 970 000 000 , car je pensais qu'il "beuguait" et ben non:

Donnez la valeur de n = 30k : 29 970 000 000
Phase d'initialisation: 3.6816067695617676 seconds ---
Bloc S2_s3 : 5224.839176654816 seconds ---
Extraction des premiers n à 2*n : 31.137654781341553 seconds ---

**  152859833 nombres trouvés en 5259.658438205719 secondes **
Appuyez sur une touche pour continuer...

******************************
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG4Y_modulo30.py =====
Donnez la valeur de n = 30k : 29 100 000 000
Phase d'initialisation: 4.321207523345947 seconds ---
Bloc S2_s3 : 173.519104719162 seconds ---
Extraction des premiers n à 2*n : 7.363212823867798 seconds ---

**  148600698 nombres trouvés en 185.20352506637573 secondes **


c'est quand même curieux la différence de temps qu'il y a pour n = 29 100 000 000 pour une différence relativement faible

sqrt de 2*29970000000 et sqrt de 2*29100000000 :  ce qui représente environ un écart de 300 nombres premiers pi en plus, qui vont cribler très peu de nombres...

LEG
07-07-2018 12:06:31

voici les tests pour la fam=Dico[1] avec ta modif:

===== RESTART: E:\Documents\conjecture de Goldbach\cribleG4Y_modulo30.py =====
Donnez la valeur de n = 30k : 21000000000
Phase d'initialisation: 1.9968032836914062 seconds ---
Bloc S2_s3 : 103.94298267364502 seconds ---
Extraction des premiers n à 2*n : 5.3196094036102295 seconds ---

**  108685478 nombres trouvés en 111.25939536094666 secondes **
>>>
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG4Y_modulo30.py =====
Donnez la valeur de n = 30k : 24300000000
Phase d'initialisation: 2.3088040351867676 seconds ---
Bloc S2_s3 : 121.43061327934265 seconds ---
Extraction des premiers n à 2*n : 6.130810499191284 seconds ---

**  125009260 nombres trouvés en 129.8702278137207 secondes **

ensuite j'ai re modifié :


debut,fin,pas=j+pi*(1-j%2),pi*30,pi*2  # ici
       temoin=0
       for j in range(debut,fin,pas):
           if j%30==1:                     # ici            
             fam=Dico[1]    # modifier la valeur de la fam à cribler [1,7,11,....,29]
             if not ((1<<fam)&temoin):
 

voici les tests
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG4Y_modulo30.py =====
Donnez la valeur de n = 30k : 21000000000
Phase d'initialisation: 1.9968035221099854 seconds ---
Bloc S2_s3 : 103.35018134117126 seconds ---
Extraction des premiers n à 2*n : 5.304009199142456 seconds ---

**  108685478 nombres trouvés en 110.6509940624237 secondes **
>>>
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG4Y_modulo30.py =====
Donnez la valeur de n = 30k : 24300000000
Phase d'initialisation: 2.3400039672851562 seconds ---
Bloc S2_s3 : 122.10141444206238 seconds ---
Extraction des premiers n à 2*n : 6.146410703659058 seconds ---

**  125009260 nombres trouvés en 130.5878291130066 secondes **
>>>

Comme tu peux le voir, cela ne change pas grand chose...

C'est pour cela que je voulais modifier cette ligne afin qu'elle s'arrête des que j%30 ==1 est trouvé, puisque ensuite on va les tester à la ligne en dessous ("for j in range(debut,fin,pas):")

debut,fin,pas=j+pi*(1-j%2),pi*30,pi*2
LEG
07-07-2018 11:03:25

Maintenant, je vais regarder de plus près ta motif  du #276 et chercher pourquoi elle plante...
Quand je saurai, je me pencherai sur ton dernière suggestion...

De ce que j'ai pu comprendre ça ne criblerait pas; du fait que pour (fin,) j'ai mis (j+pi*(1-j%2))%30==1, en croyant que des l'instant où il y a j%30==1 cela terminait le processus des j , donc inutile d'aller jusqu'à pi*30.... et que l'on passerait à la phase criblage....

Je vais essayer ta modif pour la fam=Dico [1]

yoshi
07-07-2018 10:12:42

Salut,

Dans un premier temps je repars de ton post #276...
Et j'ai retouché (très peu) la v. 6.3...
Pour n =2.400.000.000 je gagne 1 s...
Voilà la partie modifiée :


    for i,pi in enumerate(Primes_init):      
        r=nn%pi
        debut,fin,pas=r+pi*(1-r%2),min(1+r+pi*29,nn),pi*2
        temoin=0
        for j in range(debut,fin,pas):
            j30=j%30                                            #ici
            if j30 in [1, 7, 11, 13, 17, 19, 23, 29]:    #ici
                fam=Dico[j30]                                  #ici
                if not ((1<<fam)&temoin):
 

Maintenant, je vais regarder de plus près ta motif  du #276 et chercher pourquoi elle plante...
Quand je saurai, je me pencherai sur ton dernière suggestion...

@+

LEG
06-07-2018 18:49:51

donc ce n'est pas énorme en mémoire car prenons n = 30 000 000 000 soit 1 de nombre en progression arithmétique de raison 30, que l'on ne va pas écrire en totalité, et au pire chaque nombre prendrait en moyenne 2 octets soit au maximum 20 000 Pi qui cribleront modulo Pi*30 .
d'où plus Pi est grand, moins on écrit de nombres en progression Pi*30 entre 7 et n/30, et cela en partant de j = 1%30 si on crible la famille p8 = 1.
dans l'exemple du post ci-dessus avec Pi<= 83 . cela donne :

{151,361,571,781,991,1201,1411,1621,1831,2041,2251,2461,2671,2881,3091 ,3301,3511}

61,391,721    1051    1381    1711    2041    2371    2701    3031    3361  fin pour pi = 11

271 ,661,1051,1441,1831,2221,2611,3001,3391

première colonne sont les débuts index puis criblage modulo pi*30

451    ;961    1471    1981    2491    3001    3511
                       
151    ; 721    1291    1861    2431    3001    3571
                       
1    ;691    1381    2071    2761    3451   
                       
211    ;1081    1951    2821           
                       
721    ;1651    ,2581    3511           
                       
1021    ;2131,    3241               
                       
271    ;1501    ,  2731               
                       
1051    ;2341                   
                       
1231    ;2641                   
                       
151    ;1741,    3331               
                       
61    ;1831                   
                       
1771    ;                   
                       
31    ;2041                   
                       
1591    ;                   
                       
1141    ;3331                   
                       
1591    ;                   
                       
1141    ;

ce qui donne bien 52 nombres premiers de 3600 à 7200 , congrus à 29 [30]

yoshi
06-07-2018 17:06:55

Re,


J'ai questionné Python pour savoir quelle taille mémoire occupait la liste nombres pour n=300 000 000 .
Réponse : 6400000512 octets, soit 6,4 Go...

Je reprends.
1 octet c'est 8 bits.
1 en base deux c'est 00000001
2 en base deux c'est 00000010
3 en base deux c'est 00000011
............................
127 en base deux c'est 011111111
255 en base deux c'est 111111111

De gauche à droite, chaque bit vaut 128, 64, 32, 16, 8, 4, 2, 1 multiplié par 0 ou 1...
Avec 4 octets, soit 32 bis, on peut coder n'importe quel nombre entre  0 et 2**32-1 =  4294967295
Avec 8 octets, soit 64 bits, on peut coder n'importe quel nombre entre  0 et 2**64-1 = 18446744073709551615.

En binaire :
4294967295 = 11111111111111111111111111111111
Je vais reprendre mes essais parce que l'idée de départ était bonne, mais les durées sont - curieusement - invraisemblables par rapport à la construction d'une liste de 8000000000 de 1 !!!
La liste nombres, c'est au départ 8 lignes de nbcell nombres égaux à 1..
Pour n=30 000 000 000, on obtient nbcell= 1 000 000 000.
Soit pour la liste nombres 8 lignes de 1 milliard de 1...

L'idée m'était venue de remplacer par exemple [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] par le nombre binaire 1111111111111111 soit en décimal :
65635 et donc remplacer la liste de 8 listes de 1 000 000 000 de 1 par un seul nombre dont la représentation binaire était composée de 1 milliard de 1, mais le temps de calcul de ce nombre exact est vraiment vraiment prohibitif : il comprend, en base dix, 125 000 000 de chiffres, il vaut très exactement [tex]2^{1\,000\, 000\, 000}-1[/tex].
J'avais trouvé comment remplacer un bit dans n'importe quelle position de  n'importe quel nombre et le mettre à 0 quand il vaut 1 et le laisser à 0, sinon.
Dommage ! (mais je n'ai pas renoncé à l'idée même si je ne vois pas trop comment m'en sortir)

donc un entier n compris entre 7 et n/30 , quelque soit cet entier il ne prendrait qu'un octet....?

J'ai dit :
avec 1 octet on peut représenter n'importe quel nombre entre 0 et 255 (=[tex]2^8-1[/tex])  --> 8  = 8 * 1
avec 2 octets on peut représenter n'importe quel nombre entre 0 et 65535 (=[tex]2^{16}-1[/tex])  --> 16 = 8 * 2
avec 3 octets on peut représenter n'importe quel nombre entre 0 et 16777215 (=[tex]2^{24}-1[/tex]) --> 24 = 8 * 3
avec 4 octets on peut représenter n'importe quel nombre entre 0 et 4294967295 (=[tex]2^{32}-1[/tex]) --> 24 = 8 * 4
............................................
avec 8 octets on peut représenter n'importe quel nombre entre 0 et 18446744073709551615 (=[tex]2^{64}-1[/tex]) --> 64 = 8 * 8

Donc l'idée est économique, mais le temps de calcul du nombre est lui inacceptable.
Pourtant, j'ai la sensation de rater quelque chose...

Je vais essayer de regarder ce que tu racontes...

@+

LEG
06-07-2018 15:32:17

moi j'ai tester 36 000 000 000, mais pour une famille soit : 1 200 000 000 octets....voila pourquoi il faut cribler uniquement par famille, il en est de même pour Eratosthène modulo 30 ...où je vais jusqu'à 15 000 000 000 octets par famille...

Par contre tu dis que 255 ou 1, ne prend qu'un octet.. donc un entier n compris entre 7 et n/30 , quelque soit cet entier il ne prendrait qu'un octet....? car si c'est le cas on a pas besoins du tableau de 1 pour une famille ....mais cela m'étonnerait...!

Dans cette hypothèse il suffit de cribler modulo pi*30 en partant de R = j tel que j est le reste de nn%pi

exemple n= 3600 soit, 3600/30 = 120 [1] ok...

donc :nn =7200 ; pi = 7 on veut cribler la fam, Dico={1:0} donc : fam=Dico[1]

j = 7200%7 == 4
on cherche j < 7*30 , congru a 1 modulo 30

  il faut que cette ligne soit modifiée 

debut,fin,pas=j+pi*(1-j%2),pi*30,pi*2  

afin de ne s'occuper que de j%30==1
exemple :
4+7 = 11 qui correspond à j+pi*(1-r%2), 11 != 1%30 , on incrémente 11+14 = 25 ; 39 ; 53;  67; 81 != 1%30 ;95; 109; 123;137 ;
151 = 1%30 on passe à la phase criblage modulo pi*30 = 210

d'où :
151 +210+ 210 +210.....etc +210  jusqu'à <=3600 ce qui donne le nombre de [0] 16 +1 = 17 [0]   fin pour pi =7
et on stock les valeurs pour connaître les doublons afin de ne pas supprimer des [1] qui seraient marquer plusieurs fois ....autrement dit les valeurs sont les [0], une valeur qui apparaît plusieurs fois, ne vaut qu'un [0]
ce qui donne :
{151,361,571,781,991,1201,1411,1621,1831,2041,2251,2461,2671,2881,3091    ,3301,3511}
************************************
on passe à pi =11 on réitère 7200%11 == 6
6+11=17 on incrémente jusqu'à j%30==1 ; 17+22, +22 = 61 et 61%30 == 1 ok, on passe au criblage modulo pi*30 = 330

61 + 330 ....etc <= 3600

ce qui donne 10 [0] car il y a un doublon en rouge :

61,391,721    1051    1381    1711    2041    2371    2701    3031    3361  fin pour pi = 11
****************************************
on passe à pi =13 on réitère 7200%13 == 11
11+26 on incrémente jusqu'à j%30==1 ; 37+26, +26+26+26+26+26+26+26+26 = 271 et 271%30 == 1 ok, on passe au criblage modulo pi*30 = 390

271 ,661,1051,1441,1831,2221,2611,3001,3391
ce qui donne 7 [0] car il y a 2 doublons en rouge :
***************************************

etc....etc  jusqu'à pi = 83  il est clair que les derniers pi, ne vont pas marquer grand chose à part des doublons...

ensuite, à la fin comme tu l'as dit, on retranche le nombre de [0] de la somme des [1] = 120...

Est ce plus simple et plus rapide pour de grandes valeurs de n.....? est ce que l'on va à n = 30 mds....? car il faut trier les doublons....je doute que cela soit plus efficace....que de modifier cette partie , afin de chercher j=1%30 , et passer à la phase criblage , pour chaque pi:


  j=nn%pi
 debut,fin,pas=j+pi*(1-j%2),pi*30,pi*2
        temoin=0
        for j in range(debut,fin,pas):    
            if j%30==1:
 

j'ai remplacer le r par j, et on aurait pas besoins d'aller jusqu'à pi*30 pour une majorité des pi , puisque la fin est ordonnée par j%30==1

il suffit ensuite de changer j%30==p8;  par l'une des 8 familles que l'on veut cribler...

yoshi
06-07-2018 13:05:18

Salut,

Oui, je cherche toujours...
Mais je bute sur le remplacement du fichier final nombres qui ne contient que 1 ou 0.
Que ce soit 0, 1 ou 255 ça occupe 1 octet en mémoire...
Avec n=30 000 000 000
Ce fichier occupe 30 000 000 0000/30 *8 soit 8 000 000 000 octets, soit 8 Go...
Chez moi le test avec cette valeur de n plante : memory out...
Tous les essais de contournement se sont révélé prohibitifs en temps...
Je n'ai pas perdu tout espoir ...

Je vais me pencher sur ton pb...

@+

LEG
06-07-2018 10:36:14

Bonjour @Yoshi

Je ne sais pas si tu cherches toujours à amélioré , mais voila la partie du programme que j'ai "modifié" , mais qui crible faux...

par exemple pour n=240 j'ai 8 comme résultat et pour n = 24 300 000 000 j'ai 8 fois plus de premiers Mais , c'est le temps mis qui est intéressant 37 seconde au lieu de 131...Alors peut être que c'est dû au fait qu'il est faux ....?

voila la partie modifiée juste en dessous de la ligne r=nn%pi remplacé par j=nn%pi

en tenant compte que dans le programme j=r+pi*(1-r%2), qui correspond au début, on vérifie si j%30==1 , qui indique la fin sinon on incrémente par pas de ,pi*2... des que le j%30==1 est trouvé on passe au criblage


 debut,fin,pas=j+pi*(1-j%2),(j+pi*(1-j%2))%30==1,pi*2    # j'ai modifié (fin) afin qu'il s'arrête des que j%30==1
        temoin=0
        for j in range(debut,fin,pas):    
            if j%30==1:          # j'ai donc modifié  
              fam=Dico[1]
              testbit=(1<<fam)&temoin
              if not testbit:
                 temoin=(1<<fam)|temoin
                 debut_index=j//30
                 Nombres_fam=nombres[fam]
                 for index in range(debut_index, nbcell,pi):
                   Nombres_fam[index] = 0  
 

partie d'origine programme actuel :


j=nn%pi
 debut,fin,pas=+pi*(1-j%2),pi*30,pi*2
        temoin=0
        for j in range(debut,fin,pas):    
            if j%30==1:
                fam=Dico[1]
                testbit=(1<<fam)&temoin
                if not testbit:
                    temoin=(1<<fam)|temoin
                    debut_index=j//30
                    Nombres_fam=nombres[fam]
                    for index in range(debut_index, nbcell,pi):
                        Nombres_fam[index] = 0  
 

C'est donc cette partie, que je n'arrive pas à résoudre pour qu'il crible au fur et à mesure , et pour chaque pi en gagnant du temps et de la mémoire .


 debut,fin,pas=r+pi*(1-r%2),(r+pi*(1-r%2))%30==1,pi*2    # j'ai modifié (fin) afin qu'il s'arrête des que j%30==1 et qu'il crible.
        temoin=0
        for j in range(debut,fin,pas):    
            if j%30==1:          # j'ai donc modifié
 

Mais je patine dans la choucroute.....
@+

LEG
28-06-2018 13:53:48

Bonjour.

["Pour la conjecture de Goldbach , je me suis peut être mal exprimé.
Ma question porte uniquement sur une famille, parmi les 8 familles de premiers.
Si par exemple je prend la famille d'entier n = 30k + 7 soit 2n = (2*30k) + 14 ; est ce qu'il existe 2* (30k + 7) qui ne satisferait pas la conjecture , on sait avec le crible que la densité de nombres premiers q [30k ; 2*30k +14] vaut $0,375 *\frac{30k + 7}{Ln (2*(30k+7))}$
on sait que pour $n\leqslant210$ la conjecture est vraie en règle générale, mais par exemple uniquement pour la famille 30k+1 on sait que 2n = 152 n'est pas somme de deux premiers (p,q )appartenant uniquement à cette famille. C'est d'ailleurs la seule, ce qui s'explique aisément avec l'écart entre les premiers < 150 dans cette famille..."]

Effectivement le crible permet de montrer la densité de nombres premiers [n ; 2n] , par famille ou pour les 8 familles. Ce qui après étude, permettra peut être de revoir la conjecture sous un autre angle et peut être ensuite de la résoudre...C'est pour cela, que je disait prenons l'un des 8 familles  30k + n, n[2;28]. Pour faire simple, la famille arithmétique 30k+7 , existe t'il un 2n = 2*(30k+7) qui n'est pas la somme de deux premiers (p,q) appartenant à cette famille...? Plus généralement avec les 3 familles arithmétiques de raison 30, de premier terme {7, 1,  13}...C'est pour les matheux....

Pour en revenir au crible: Pour une seule Fam.

On connaît le nombre maximum de 1 dans a liste.
Partir de ce nombre.
Lui soustraire 1 quand on remplaçait un 1 par un 0.

....? Là, tu vas vite...Car comment tu cribles les 1 par pas de Pi en partant de son index....???

Tu peux toujours dire,  Exemple Pi = 7 j'ai n= 240, soit 240/30 = 8 , donc 8/7 = 1 il te faut soustraire 1 deux fois...ok..?
comment tu fais pour les autres Pi = 11,13,17,19 bien sûr connaissant l'index, compris entre 0 et 7 tu sauras que si l'index est compris de 0 à 7 , cela te donnera le nombre de 1 à soustraire...par contre tu ne sauras jamais si il y a des doublons dans la liste des 1, pour n= 3000 par exemple , d'où impossible de cribler sans erreur...! Et pour les 8 familles encore plus compliqué..!

On a pas le choix ..on est obligé d'initialiser la liste de 1 de 0 à n/30, justement pour cribler par pas de Pi, marquer les doublons, et on ne sait pas où ils se trouvent.
(" sauf bien entendu si on écrivait les valeurs de [1]..Et dans ce cas là , on en revient à une perte de temps et de mémoire car il faudrait écrire les entiers en progression arithmétique de raison 30, de Pi = {7,11,13,17,19,23,29,31} à n/30 ...").

Par contre on peut gagner en temps et en mémoire, si et uniquement par Famille : Exemple la famille j%30 == 1

1) On édite les Pi avec : Primes_init = eratostene(n)..... Cà on a pas le choix..

2) c'est dans cette partie du programme que cela se passe..[" ce que je n'ai pas réussi à faire"]


for i,pi in enumerate(Primes_init):      
        r=nn%pi
        debut,fin,pas=r+pi*(1-r%2),1+r+pi*29,pi*2
        temoin=0
        for j in range(debut,fin,pas):    
            if j%30==1:    # modifier le reste de la fam à cribler (1,7,11,....,29)
 

A mon avis: on calcule pour chaque Pi, au fur et à mesure,  le  r=nn%pi , puis les j jusqu'à j%30 == 1 
des qu'il est trouvé, stop ou fin.

ce qui fait modifier cette ligne : debut,fin,pas=r+pi*(1-r%2),1+r+pi*29,pi*2 . Là , on ne stock rien...ok
on a le j%30==1 on passe de suite à la partie suivante pour cribler:

3)


for index in range(debut_index, nbcell,pi):
                        Nombres_fam[index] = 0  
 

une fois que Pi à criblé, on passe au Pi suivant, on réitère : calcul de   r=nn%pi , calcul du J%30==1
puis re criblage...etc...

Donc tu vois on va gagner un peu,  on évite de stocker tous les r=nn%pi , pour les rappeler ensuite , on ne stock pas les j...que l'on va ensuite classer dans leur famille, car il nous en faut qu'un seul celui qui est = à j%30==1; de plus, on sait qu'il se trouve entre r et pi*29 . On a plus besoins de Pfam...

Voila ce que l'on peut gagner...
Ensuite augmenter la ram comme tu dis...ce n'est pas le plus important...

De toutes les façons on serra limité...à environ n /30 = 15 000 000 000.
c'est ce que fait Eratosthène modulo 30 par Famille et il est plus simple; car on n'utilise que 8 Pi, les autres sont extraits au fur et à mesure, ils criblent et sorte du programme...
On a donc en mémoire la liste des 15 000 000 000 de [1], que l'on marquera par des [0].
Mais on est obligé aussi de les écrire...il est beaucoup plus rapide car on ne fait que compter par pas de Pi;
c'est le groupe multiplicatif des 8 premiers, qui avance comme un rouleau....qui extrait les Pi > 31 , afin qu'ils aillent cribler....etc...etc.

yoshi
28-06-2018 09:18:45

Bonjour,

Je vois que tu t'amuses bien...
Quant à moi, j'ai essayé, de temps en temps, de gagner du temps, sans succès notable...
Ce matin, il m'est venu une idée (sans chercher)...
Il  va falloir que j'approfondisse : si ça marchait, je pense qu'on gagnerait du temps et de la mémoire (concernant la place : si tu augmentes ta quantité de RAM, tu iras plus loin...)

Donc l'idée...
Constat.

                    for index in range(debut_index, nbcell,pi):
                        Nombres_fam[index] = 0  

On bâtit une liste immense ne contenant que des 1 pour avoir le plaisir d'en remplacer certains par des zéros et compter les 1 à la fin...
Je caricature un peu.
Modif envisagée.
On connaît le nombre maximum de 1 dans a liste.
Partir de ce nombre.
Lui soustraire 1 quand on remplaçait un 1 par un 0.
Avantage : plus besoin de ladite liste et donc de la remplir, puis de sommer tous ses éléments.
Problème : on va soustraire 1 plusieurs fois de trop. C'est là-dessus que je veux me concentrer.

Ça doit être faisable, mais il ne faudrait pas ralentir, ni bouffer de la mémoire...

LEG a écrit :

Autrement dit, est ce que l'on s'est posé la question : existe t'il un entier 2n = 30k + n, avec n [2;28] pair, et k > 10 ; qui ne satisfait pas la conjecture pour une et une seule des 8 familles, avec n⩾210 ....

Ça, c'est étrange, parce que :
[tex]2n=30k+n[/tex] c'est une évidence. Si je pars de [tex]n =30k[/tex]  alors [tex]2n=30k+n,\;3n=30k + 2n,\;4n=30k+3n\cdots[/tex]
Et d'autre part, si [tex]n \in [2\,;\,28][/tex] je ne vois pas comment on pourrait avoir n=30k...

Qu'est-ce que tu voulais dire ? Existe-t-il un entier 2n = 30k + p, avec [tex]p \in [2\,;\,28][/tex] pair, et k > 10 (...) ?
Si oui, tu poses p=2q, et tu demandes :
Existe-t-il un entier n = 15k + q, avec [tex]q\in [1\,;\,14][/tex] , et k > 10 (...) ?

En vérifiant la densité de premiers , par rapport à la conjecture de Goldbach, ce crible permet d'affirmer, que si la conjecture est vraie pour tout entier n⩾30k alors quelque soit l'une des 8 familles choisie, elle vraie aussi...!

Bon, d'un point de vue strictement mathématique, le programme n'apporte aucune preuve, juste de fortes présomptions...
Tu n'as pas vérifié pour tout entier [tex]n\geqslant 210[/tex] mais pour  [tex]210\leqslant n\leqslant \cdots[/tex].
C'est ce que tu répondra n'importe quel mathématicien...

@+

LEG
26-06-2018 09:48:52

Bonjour @Yoshi

Voila comment j'ai modifié ta dernière version du crible, qui marche très bien mais sans avoir amélioré la limite, qui se situe vers:
29 850 000 000.


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

## V. 6.3 ##

def eratostene(n):
    n = int((2*n)**0.5)
    m = (n-1) // 2
    limite=1+n
    b = [True]*m
    premiers = [2]
    for i,p in enumerate(range(3,limite,2)):
        if b[i]:
            premiers.append(p)
            j = 2*i*i + 6*i + 3
            debut,pas=j,2*i+3
            for j in range(debut,m,pas):
                b[j] = False
    debut=i
    for i in range(debut,m):
        if b[i]:
            premiers.append(p)
        p += 2
    return premiers[3:]

def CribleG4Y_mod30(n):
    # INITIALISATION
    global fam,temoin
    start_i= time()
    Primes_init = eratostene(n)
    nn,nbcell=n*2,n//30
    nombres=[]
    for i in range(1):
        nombres.append([1]*nbcell)
    P8=OrderedDict={1:0}    # modifier la fam que l'on veut cribler {1:0,7:1,....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):      
        r=nn%pi
        debut,fin,pas=r+pi*(1-r%2),1+r+pi*29,pi*2
        temoin=0
        for j in range(debut,fin,pas):    
            if j%30==1:    # modifier le reste de la fam à cribler (1,7,11,....,29)
                fam=P8[1]  # modifier la valeur de la fam à cribler [1,7,11,....,29]
                testbit=(1<<fam)&temoin
                if not testbit:
                    temoin=(1<<fam)|temoin
                    debut_index=j//30
                    Nombres_fam=nombres[fam]
                    for index in range(debut_index, nbcell,pi):
                        Nombres_fam[index] = 0  
    s_23=time()-start_time
    print("Bloc S2_s3 : %s seconds ---" % s_23)

    # CALCUL DES NOMRES PREMIERS ENTRE n ET 2*n
    start_time = time()
    total = 0
    for sous_liste in nombres:
        total+=sum(sous_liste)      
    s_4=time() - start_time
    s=s_1+s_23+s_4
    print("Extraction des premiers n à 2*n : %s seconds ---" % s_4)
    return total,s

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

En vérifiant la densité de premiers , par rapport à la conjecture de Goldbach, ce crible permet d'affirmer, que si la conjecture est vraie pour tout entier $n\geqslant{30k}$ alors quelque soit l'une des 8 familles choisie, elle vraie aussi...!
car le crible progresse de raison 15 ou 30 peut importe .
Donc par exemple, pour un entier 30k +1, +7, +11...etc ... Cela revient à cribler, n = 30k sans perte de généralité ...

J'ai criblé 30k +1, les trois familles concernées sont : la fam = 1, 13 et 19 ("qui peuvent satisfaire Goldbach")
et pour 30k+7 ,  les trois familles concernées sont : la fam = 1, 7 et 13   

Quelques résultats   :
fam :1 ,   
Donnez la valeur de n = 30k : 3000001  ; 24473 nombres trouvés en 0.00700068473815918 secondes **     
fam : 13
n = 30k : 3000001 ;     24497 nombres trouvés en 0.031001806259155273 secondes **
fam : 19
n = 30k : 3000001 ;    24527 nombres trouvés en 0.034002065658569336 secondes **

pour n = 300 000 001
fam :1 ,                     1883781 nombres trouvés en 1.2948017120361328 secondes **
fam :13 ,                   1883976 nombres trouvés en 1.2636022567749023 secondes **
fam :1 9,                  1883814 nombres trouvés en 1.2792022228240967 secondes **

pour n = 3000 000 007
  fam :1                    16885842 nombres trouvés en 13.907795429229736 secondes **
  fam :7                   16887883 nombres trouvés en 13.908795833587646 secondes **
  fam :13                 16887274 nombres trouvés en 13.936745405197144 secondes **

Autrement dit, est ce que l'on s'est posé la question : existe t'il un entier 2n = 30k + n, avec n [2;28] pair, et k > 10 ; qui ne satisfait pas la conjecture pour une et une seule des 8 familles, avec $n\geqslant{210 }$ ....

LEG
17-06-2018 16:07:54

Tu avais raison, mais ce n'est peut être pas un pouième de pouième

===== RESTART: E:\Documents\conjecture de Goldbach\cribleG4_modulo30.py =====
Donnez la valeur de n = 30k : 24000000000
Phase d'initialisation: 2.8548049926757812 seconds ---
Bloc S2_s3 : 119.7614107131958 seconds ---
Extraction des premiers n à 2*n : 6.0996105670928955 seconds ---

**  123530551 nombres trouvés en 128.71582627296448 secondes **
>>>
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG4_modulo30.py =====
Donnez la valeur de n = 30k : 27000000000
Phase d'initialisation: 2.5740044116973877 seconds ---
Bloc S2_s3 : 138.06024265289307 seconds ---
Extraction des premiers n à 2*n : 6.8328118324279785 seconds ---

**  138301355 nombres trouvés en 147.46705889701843 secondes **
>>>

===== RESTART: E:\Documents\conjecture de Goldbach\cribleG4_modulo30.py =====
Donnez la valeur de n = 30k : 29100000000
Phase d'initialisation: 3.104405403137207 seconds ---
Bloc S2_s3 : 150.4622642993927 seconds ---
Extraction des premiers n à 2*n : 7.378813028335571 seconds ---

**  148600698 nombres trouvés en 160.94548273086548 secondes **
>>>
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG4_modulo30.py =====
Donnez la valeur de n = 30k : 29400000000
Phase d'initialisation: 3.744006395339966 seconds ---
Bloc S2_s3 : 166.06229162216187 seconds ---
Extraction des premiers n à 2*n : 7.628413438796997 seconds ---

**  150069716 nombres trouvés en 177.43471145629883 secondes **
>>>

il ne me reste plus qu'à vérifier si il passe à 30 mds....

la modif des 5 lignes est relatif au criblage par famille :


for i in range(8):    # on remplace 8 par 1

 P8=[1, 7, 11, 13, 17, 19, 23, 29]   #on remplace par P8=[1] il ne reste qu'une famille, la 1

    Dico=OrderedDict={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}  #on ne garde que {1,0} , il ne reste qu'une famille la 1:0

 if j%30==1:  # Car on ne va cribler que la famille 1 modulo 30, se terminant par 1

                fam=Dico[1]  # car on a testé ci dessus, si j = 1 modulo 30, d'où calcul du modulo inutile
 

Et malgrès cela , le chilmiliblic n'avance guerre plus vite , un peu plus de capacité mémoire...on est presque à 30mds....

Voila ....Yoshi , Mais c'est un très bon crible avec un bon programme...Je t'en remercie ....


Pour la conjecture de Goldbach, on sait que l'on a suffisamment de nombre premiers q, pour satisfaire la conjecture ...
On peut même calculer la densité des trois familles P8 = [1,7,13] relatif à 2n = 30k + 14, où : uniquement ces trois familles peuvent  satisfaire Goldbach .

La densité est d'environ : ((15k + 7) / Ln (30k + 14)) * 0,375
Pour n = 3 000 007 , on a 73509 premiers q [n ; 2n] , pour une estimation de la fonction ((15k + 7) / Ln (30k + 14)) * 0,375  = 72081

Pour 29 850 000 000 il met 319 secondes , mais pas d'amélioration sur la limite < 29 910 000 000...ce qui n'a pas d'importance
@+

LEG
17-06-2018 14:56:29

Bonjoiur Yoshi
je vois que cet algorithme te tient....
Tout d'abord:
a) même si on supprime la division de fam=Dico[j%30] on ne gagnerai rien...

b) comme tu l'as surement remarqué même si on ne stock plus cela ne changerai pas grand chose

c) Donc je ne pense pas que le criblage des j au fur et à mesure, de la fonction


 debut,fin,pas=r+pi*(1-r%2),1+r+pi*29,pi*2
        temoin=0
        for j in range(debut,fin,pas):
 

changerait quoi que ce soit à par 1 ou 2 secondes

d) car le résultat que j'ai testé en est une preuve suffisante

e) Je vais donc charger ta nouvelle version en cribleG4Y_modulo30 et voir ce que cela donne pour le criblage de la fam , P8 = 1

je te met trois résultats où j'ai modifié les lignes des cribles G9Y,G2Y et G3Y :


 for i in range(8):
 P8=[1, 7, 11, 13, 17, 19, 23, 29]
    Dico=OrderedDict={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}
 if j%3!=0 and j%5!=0:
                fam=Dico[j%30]
 

Afin de ne cribler que par famille...Je ferai ensuite de même avec G4Y et son résultat..
   
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG9Y_modulo30.py =====
Donnez la valeur de n = 30k : 29400000000
Phase d'initialisation: 3.2604055404663086 seconds ---
Famille de chaque Pi: : 4.336807727813721 secondes ---
Criblage des 8 familles: 155.1110725402832 seconds ---
Extraction des premiers n à 2*n : 7.534813642501831 seconds ---

**  150069716 nombres trouvés en 170.24309945106506 secondes **

=== RESTART: E:\Documents\conjecture de Goldbach\cribleG2Y_par Famille.py ===
Donnez la valeur de n = 30k : 29400000000
Phase d'initialisation: 4.10280704498291 seconds ---
Bloc S2_s3 : 161.14828300476074 seconds ---
Extraction des premiers n à 2*n : 7.566013336181641 seconds ---

** 150069716 nombres trouvés en 172.8171033859253 secondes **

===== RESTART: E:\Documents\conjecture de Goldbach\cribleG3Y_modulo30.py =====
Donnez la valeur de n = 30k : 29400000000
Phase d'initialisation: 3.9000065326690674 seconds ---
Bloc S2_s3 : 156.5618748664856 seconds ---
Extraction des premiers n à 2*n : 7.503613471984863 seconds ---

**  150069716 nombres trouvés en 167.96549487113953 secondes **

il y a des variables de temps qui s'expliquent en fonction de l'écart de temps pour lancer un nouveau test entre les trois cribles; mais l'un dans l'autre à 1 ou 2 seconde près cela ne change rien...Ce qui veut dire que ta dernière version ne gagnerait rien par rapport à la version V.6.2 = G3Y même en modifiant les 5 lignes ci dessus , afin de ne cribler que par famille et supprimer la division de  fam=Dico[j%30] qui devient inutile par famille...

@+

yoshi
17-06-2018 11:09:34

Re,

J'ai encore dû gagner un pou_ième en passant par un test bit à bit.
Je ne maîtrise pas totalement ça encore totalement, mais ça marche.
| est un opérateur binaire : 0|0=1, 0|1=1, 1|0  =1  et 1 |1 =1 qui force un bit précis à 1.
& est un autre opérateur binaire qui teste l'état d'un bit et renvoie 0 ou 1,2,4,8,16,32,64,128 dont les valeurs booleennes sont True...
J'initialise une variable temoin à 0
Sa représentation binaire est 00000000.
Supposons que fam=2
Je stocke la valeur booleenne du bit n° fam de temoin dans la variable testbit par testbit=(1<<fam)&temoin
Si testbit vaut False, je force la valeur du bit n° fam de temoin à 1 :
temoin=((1<<fam)|temoin
et je continue.
Ça remplace l'accès à la liste : je n'utilise qu'un temoin dont la valeur va varier de 1 à 255...


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

## V. 6.3 ##

def eratostene(n):
    n = int((2*n)**0.5)
    m = (n-1) // 2
    limite=1+n
    b = [True]*m
    premiers = [2]
    for i,p in enumerate(range(3,limite,2)):
        if b[i]:
            premiers.append(p)
            j = 2*i*i + 6*i + 3
            debut,pas=j,2*i+3
            for j in range(debut,m,pas):
                b[j] = False
    debut=i
    for i in range(debut,m):
        if b[i]:
            premiers.append(p)
        p += 2
    return premiers[3:]

def Crible_mod30(n):
    # INITIALISATION
    global fam,temoin
    start_i= time()
    Primes_init = eratostene(n)
    nn,nbcell=n*2,n//30
    nombres=[]
    for i in range(8):
        nombres.append([1]*nbcell)
    P8=[1, 7, 11, 13, 17, 19, 23, 29]
    Dico=OrderedDict={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}
    s_1=time()-start_i
    print("Phase d'initialisation: %s seconds ---" % s_1)
   
    # FAMILLES POUR CHAQUE Pi
    start_time = time()
    for i,pi in enumerate(Primes_init):      
        r=nn%pi
        debut,fin,pas=r+pi*(1-r%2),1+r+pi*29,pi*2
        temoin=0
        for j in range(debut,fin,pas):    
            if j%3!=0 and j%5!=0:
                fam=Dico[j%30]
                testbit=(1<<fam)&temoin
                if not testbit:
                    temoin=(1<<fam)|temoin
                    debut_index=j//30
                    Nombres_fam=nombres[fam]
                    for index in range(debut_index, nbcell,pi):
                        Nombres_fam[index] = 0  
    s_23=time()-start_time
    print("Bloc S2_s3 : %s seconds ---" % s_23)

    # CALCUL DES NOMRES PREMIERS ENTRE n ET 2*n
    start_time = time()
    total = 0
    for sous_liste in nombres:
        total+=sum(sous_liste)      
    s_4=time() - start_time
    s=s_1+s_23+s_4
    print("Extraction des premiers n à 2*n : %s seconds ---" % s_4)
    return total,s

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

Pour n=360000000
Version 6.3

Phase d'initialisation: 0.6170353889465332 seconds ---
Bloc S2_s3 : 16.123922109603882 seconds ---
Extraction des premiers n à 2*n : 0.9270529747009277 seconds ---

**  17922760 nombres trouvés en 17.668010473251343 secondes **

Version 6.2

Phase d'initialisation: 0.6210355758666992 seconds ---
Bloc S2_s3 : 16.406938314437866 seconds ---
Extraction des premiers n à 2*n : 0.9250528812408447 seconds ---

**  17922760 nombres trouvés en 17.95302677154541 secondes **

Et encore, les variations de temps me paraissent aléatoires...

@+

Pied de page des forums