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

#1 19-08-2020 12:44:34

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

modifier un programme Python

Bonjour
@Yoshi

Tu te rappelles du programme Ératosthène modulo 30 que je reposte ici


from itertools import product
from time import time
from os import system
import math

def candidate_range(n):
    cur = 5
    incr = 2
    while cur < n+1:
        yield cur
        cur += incr
        incr ^= 6  # or incr = 6-incr, or however


def eratostene(n):
    n = int(n**0.5)  
    prime_list =[2,3]
    sieve_list = [True] * (n+1)
    for each_number in candidate_range(n):
        if sieve_list[each_number]:
            prime_list.append(each_number)
            for multiple in range(each_number*each_number, n+1, each_number):
                sieve_list[multiple] = False
    #print(prime_list[3:])
    return prime_list[3:]  


def demander_N():
    n = input("Donnez N: ")
    n = int(n.strip().replace(" ", ""))
    n = int(30 * round(float(n)/30))
    return n


def E_Crible(premiers, n, fam):
    start_crible = time()
 
    # On génère un tableau de N/30 cases rempli de 1
    crible = n//30*[1]
    lencrible = len(crible)
    GM = [7,11,13,17,19,23,29,31]     ### on remplace 7 par 37####
    # On calcule les produits: j = a * b
   
    for a in premiers:
        for b in GM:
            j = a * b
            if j%30 == fam:
                index = j // 30  # Je calcule l'index et On crible directement à partir de l'index
        for idx in range(index, lencrible, a):  # index qui est réutilisé ici...
            crible[idx] = 0
        #print(index)
           
    total = sum(crible)  ## à la place on utilise ce tableau d'Ératosthène criblé, pour utiliser ce tableau dans le crible de Goldbacn, on return "crible:", crible
    print("crible:", crible)  
    print(f"Nombre premiers criblés famille {fam} : {total} ----- {int((time()-start_crible)*100)/100}")


def main():
    # On demande N a l'utilisateur
    n = demander_N()

    # On récupère les premiers de 7 à √N   ###on remplacera 7 par 11 de partout où il y a 7###
    premiers = eratostene(n)
    #print(f"nombres premiers entre 7 et (n**0.5): {len(premiers)}") # nombre de premiers qui criblent

    start_time = time()
    # On crible
    E_Crible(premiers, n, 1)  ## pour changer de Fam(i) on remplace la dernière valeur ### ou par (1,11,13,17,19,23,29,37) nouvelle Famille ###
    temps = time()-start_time
    print(f"--- Temps total: {int(temps*100)/100} sec ---")


main()
system("pause")
 

1 ) Mon but est de supprimer les multiples de 7 et de commencer à cribler à partir de $P_i = 11$
d'où :

GM = [11,13,17,19,23,29,31,37]

2 ) il me faut les entiers naturels et non leur représentation par 1


  # On génère un tableau de N/30 cases rempli de 1
    crible = n//30*[1]  ## ici ##
    lencrible = len(crible)
    GM = [11,13,17,19,23,29,31,37]
 

Mais le problème on va travailler modulo 210 à partir de N > 199
où  les 8 Famille commence ainsi :


  1 11  13  17  19  23  29  37
  31  41  43  47  79  53  59  67
  61  71  73  107 109 83  89  97
  121 101 103 137 139 113 149 127
  151 131 163 167 169 143 179 157
  181 191 193 197 199 173 209 187
 Puis on progresse modulo 210k
 211  221 223 227 229 233 239 247
  241 251 253 257 289 263 269 277
  271 281 283 317 319 293 299 307
 

Donc pour la fam(1) on aura 1,31,61,121,151,181,211,241,271,......> N limite fixée.

le debut du programme ne change pas sauf la ligne return on remplace 3 par 4 puisque l'on élimine 2,3,5, et 7


 #print(prime_list[4:])
    return prime_list[4:]  
 

Ensuite
la partie modifiée que je ne suis pas arrivé à faire fonctionner avec Fam (1) et N = 3000.


def E_Crible(premiers, n, fam):
    start_crible = time()
 
    # On génère un tableau de N/30 cases rempli de 1
    crible = n//30*[1]    ### ici ,on a la liste des entiers naturels selon le modèle ci-dessus ###
    lencrible = len(crible)
    GM = [11,13,17,19,23,29,31,37]   ### on a remplacé 7 par 37 ###
    # On calcule les produits: j = a * b
   
    for a in premiers:
        for b in GM:
            j = a * b
            if j%30 == fam:
                index = j     ### ici l'index devient la valeur de J ###
        for idx in range(index, lencrible, a):  ### ici l'index qui a changé var cribler modulo ($a*30$) à partir de l'index = J ;qui est réutilisé ici...
            crible[idx] = 0
 

il y a un souci : comme on a supprimé les multiple de 7 en criblant ($a*30$) chaque valeur serra remplacé par 0 = multiple de ($a$), il faut sauter cet entier multiple de 7, absent et continuer en rajoutant ($a*30$)

Exemple :$ Fam(11)$ , $N =3000$ , $J = 121$ on crible à partir de $121$, avec $a = 11$ en rajoutant $11*30 = 330$ et on marque les multiple de 11 par 0.

[1,31,61,121,151,181,211,241,271,331,361,391,421,451=0,481 =0,541,571,601,631,661,691,751,781=0,811,841,871=0,901,961,991,1021,1051,1081,1111=0,1171,1201,1231,1261=0,1291....etc ..>$N<3000$ ]

Mais 1441 + 330 =1771 ne peut exister car multiple de 7, donc il faut que le programme , continue et augmente tel que 1771+330 =2101, qui serra marqué 0

Puis on réitère avec j%30 == fam = 13*37 ; on peut cribler en partant de $J = 481$ soit : 481=0 avec le modulo $13*30 = 390$ , puis ensuite directement avec modulo $37*30 = 1110$ ...etc


A la fin on fait la somme des nombres premiers, et on peut sauvegarder les nombres premiers par fichier de 500 000 par exemple...ou les éditer....

Dernière modification par LEG (16-09-2020 07:55:08)

Hors ligne

#2 19-08-2020 13:04:57

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

Re : modifier un programme Python

Re,


Concrètement, tu cherches quoi, tu veux quoi ?
Améliorer ton programme, le corriger parce qu'il y a un bug quelque part ?...
Tes chaînes d'égalité m'interpellent beaucoup : ta présentation ne m'apparaît pas très claire :

[1,31,61,121,151,181,211,241,271,331,361,391,421,451=0,481 =0,541,571,601,631,661,691,751,781=0,811,841,871=0,901,961,991,1021,1051,1081,1111=0,1171,1201,1231,1261=0,1291....etc ... ]


J'ai une idée d'une personne qui lirait tes explications (il ne programme pas, ni en Python, ni C, ni C++, ni...).
Je suis, en plus de ma revue (eh oui, le mois de septembre approche à grands pas...), sur un gros coup : lorsque ce sera publié (grâce à cette personne), je te donnerai un lien, tu pourras aller voir...). A ce moment-là, je questionnerai mon petit camarade pour lui expliquer et lui demander s'il veut bien regarder et chercher s'il y a une faille...
Si oui, alors tu seras définitivement fixé.

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#3 19-08-2020 13:30:43

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

Re : modifier un programme Python

@Yoshi , il n'y a pas de faille dans le programme de l'algorithme que tu as fais.
Dans la chaine , en rouge ce sont les multiples de 11, en bleu les multiple de13 pour la Fam(11) . le hic serait dans la modification avec l'absence des multiples de 7...qui pourrait peut être créer un bug, si dans l'exemple cité il ne trouve pas la valeur $1441 + 330 =1771$ pour la remplacer par 0 suite à la modification...
.................................

Mais j'ai besoins des valeur réelles des nombres premiers représenté par des 1 : [11,41,71,101,131,0,191,0,251....etc ]
Fam 11, par exemple avec le programme actuel
crible: [1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0]

A moins qu'à la fin du programme il restitue directement et à la demande les valeurs des 1 , en rajoutant 30k...ce qui peut être est plus facile ...je n'y ait pas pensé.

C'est pour cela que j'ai pensé au départ, à modifier le code du programme et en supprimant les multiples de 7, qui prendrait de la mémoire .
Mais peut être que cela risque de rendre le programme ainsi modifié, plus lent même sans les multiples de 7 ....? Plutôt que de restituer les valeurs des 1 .

Je viens de faire un essais et je pense que c'est inutile; vue le temps qu'il met,  rient que pour éditer les 1...
Je pense que python n'est pas fait pour ça et qu'il faut du C++. J'aurai dû commencer par là avant de poser mon problème de modification...
pour N = 600 000 000 Temps total: 586.17 sec -

Pour une base de données de un milliard de nombres premiers.....ça va trainer...

Dernière modification par LEG (19-08-2020 14:02:57)

Hors ligne

#4 19-08-2020 13:53:21

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

Re : modifier un programme Python

Ave,

Rien que là :
[1,31,61,121,151,181,211,241,271,331,361,391,421,451=0,481
Ton = c'est plutôt $\equiv$? Si oui, il est où le modulo ?...
Ca s'emploie comme ça en principe : $1771 \equiv 0\;\;[7]$

J'ai bien vu que de 1 à 421 c'étaient des multiples 30, +1...
Tu vas jusqu'à 421, soit une liste de 13 nombres qui n'est plus égale qu'à 0 et 481 ???
Et paf, ligne suivante, ta liste fait l'accordéon augmente, diminue... Tu fais quoi ?

Quant à ce que j'ai dit ensuite, ça portait sur ta démonstration de la conjecture et plus particulièrement ta version d'un raisonnement par l'absurde pour savoir si oui ou non, ta démonstration est sans faille ou pas...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#5 19-08-2020 14:27:45

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

Re : modifier un programme Python

A ) : Pour la conjecture , personne ne m'a donné de réponse sur la dernière formulation et notamment sur le dernier fichier que j'ai posté dans  les posts de ce forum programmation...http://www.bibmath.net/forums/viewtopic.php?id=10154&p=16 #post 389.

1) L'égalité en jaune (propriété récurrente de l'algorithme) qui était élémentaire à démontrer .
(Au départ il pensait que je ne pourrai pas la démontrer ...et que je devais avoir une erreur .... Donc il a fallu que je leur donne la réponse afin qu'il trouve ma soi-disant erreur ....mais nada il n'y en a pas, ....et là....motus; plus aucun commentaire, il est vrai que c'était tellement élémentaire, et n'ayant pas du tout étudié l'algorithme avec ses propriétés qu'ils s'en faisaient une fausse idée !)

2) La fin du document sur la fonction qui estime le nombre de couples p+q = 2n, elle ne peut être nulle, autrement dit il ne peut exister un entier 2n > 290 quelque soit la famille 30k +(i) utilisée, où cette fonction serait = 0...
Car il faudrait utiliser les restes R (de 2n - 30; 2n - 60...etc) précédents ayant vérifiée la conjecture pour ces limites ; ce qui est absurde... D'autant que cette fonction donne toujours 2 résultats : 1) l'estimation du résultat réel pour la limite 2n vérifiée, donc vraie ; 2) mais aussi pour cette même limite 2n vérifiée, l'estimation qui vérifiera la conjecture pour cette limite suivante, le nombres de couples p+q = 2n+30 ...! Par conséquent , la fonction ne peut pas être nulle et non nulle pour une même limite 2n . Fonction qui utilise le nombre de premiers $\pi(2n)$ et comme facteur , la constante $C_2$ des premiers jumeaux : 1,320323... La fonction $c_2*\frac{\pi(2n)}{ln\:\pi(2n)}$ ; fonction que l'on peut utiliser par famille avec le nombres de premiers par famille...

Par exemple limite n = 3 000 000 : nombre de premiers Fam (30k +7) < (2n = 6 000 000) = 51 646 la fonction donne une estimation de couples p+q = 2n de 6283 couples pour un réel de Nombres P' non congruent à [pi] de 1 à 3000000 famille 7, nombre de couples p+q=2n: 6230 ----- 0.01 Estimation légèrement supérieur, mais dès que la limite 2n augmentera  on passera sous la valeur réel du nombre de couples.


(Le détail des explications est dans les autres pdf que j'ai posté ).... (on verra...)

https://www.cjoint.com/c/JKviTzczeme


B ) : Pour en revenir à ta question; le modulo , il n'y a plus le modulo 30 c'est pour  cela que la suite  des entiers fait l'accordéon , ni de congru, sauf pour définir la valeur de j= a*b ; si j%30== fam , par rapport à la famille fixée. Et 121%30 == 1 pour la Fam (1) fixée.

[1,31,61,121,151,181,211,241,271,331,361,391,421,451=0 on le marque 0, car multiple de 11 ("sinon il faudrait écrire $451\equiv {0}[11]$ ce qui n'apporte rien") , puis 481 marqué 0 car multiple de 13
On écrit les entiers  B + 210k  ce qui supprime les multiples de 7, dans cette famille (1), avec B = [1,31,61,121,151,181] et on crible modulo (P*30) en partant de j = a* b .

Donc j'utilise pour cribler cette famille d'entier le modulo (P*30)k ; pour 11 au carré en partant de j = a*b = 11*11, que l'on marque 0; ensuite on marque 0 les multiples de 11, modulo (11*30) et non plus par pas de P, comme dans l'ancien programme; on utilise directement les valeurs ... Mais ça risque d'être long, même sans les multiples de 7 pour preuve voir ci-dessous....

Déjà rient que pour N = 3000 000 000 ça fait 40 minute qu'il traîne pour éditer les 1 = premiers dans la famille (1).
D'où les multiples de 7 ne sont pas un problème dans la fonction du crible avec notre programme

def E_Crible(premiers, n, fam):

.

C'est l'édition qui est longue et en plus ce ne sont que des 1 ou des 0.

Dernière modification par LEG (07-12-2020 08:35:13)

Hors ligne

Pied de page des forums