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

#351 23-12-2018 11:09:54

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 501

Re : crible en python

Re,

Mon post s'est validé après fausse manipe de clavier, je l'ai repris immédiatement et complété, mais pas de bol, tu as répondu entre temps à un post incomplet...

Retourne le lire et dis-moi si ça change ta réponse...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#352 23-12-2018 12:14:58

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

Re : crible en python

Faut pas courir partout : qui trop embrasse mal étreint !...

oui mais ... il court il court le furet, le furet du bois joli...Tu as entièrement raison méaculpa...

C'est exactement comme cela que j'ai modifié la fonction et qui marche dans les deux cribles, comme tu as pu le constater avec les résultats..


Concernant ma question: en C++ on peut faire partir les Ai, les uns derrière les autres...est ce qu'en python c'est faisable aussi car on gagnerait du temps:

On a donc le [GM avec ses 8 B indicés de 0 à 7]
i= 0, B=7
i= 1 , B=11
i= 2, B=13
i= 3, B= 17
i= 4 , B=19
i= 5, B=23
i= 6, B=29
i= 7 , B=31

On a donc :


 for a in (premiers):
        for b in (GM):
            j = a * b
            if j%30 == fam:
 

i = 0 , B= 7 :va parcourir A du début à la fin, il fait partir tous ses index A, les uns derrière les autres lorsque le dernier index A à criblé par pas de A,..

on passe à l'indice suivant  i+1
i =1,B = 11: et on reitère....11 va parcourir A du début à la fin, fait partir tous ses index par pas de A...etc ..indice i+1 suivant

i = 2, B=13....

pour Fam =7 et n =3000

B = 7 , va faire partir 31 ==7%30 de lindex 7 ,...pas de 31, il n'y en a pas d'autre car 61> 53 .indice i suivant

B=11 , va faire partir 17==7%30, de l'index 6..puis il continue il va faire parti 47==7%30 de l'index 17...> n/30] fin pour B= 11, indice suivant on réitère ...etc

à la fin des 8 indices B , on fait la somme des [1] tous les A ont criblé de leur début d'index...!

Qu'est ce que tu en penses...? pour accélérer le programme...
Pour t'avoir fais galérer pour rien...et mal compris, où je t'envoie les bouteilles et le panier garni...ou autre...! car le réveillon va être fini....

Dernière modification par LEG (23-12-2018 14:55:12)

Hors ligne

#353 23-12-2018 12:50:50

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 501

Re : crible en python

Re,


for i,B in (GM):

Ne marche pas sans enumerate.
C'est quoi GM ?
Grand Maïtre ?
Groupe Multiplicatif ? Pour un matheux, cela a un certain sens, probablement pas le tien..

Certains de tes prog ont pour nom Goldbach, je ne t'ai jamais suivi sur ce terrain, parce que je ne trouvais pas ça parlant, a fortiori losqu'ils sont suivi d'un n°...
Goldbach, moi, j'en suis resté là :
Tout nombre entier pair supérieur à 3 peut s'écrire comme la somme de deux nombres premiers....
Je viens de faire une recherche m'aiguillant sur Bertrand :
Entre n et 2.n, il existe toujours un nombre premier.
Autrement-dit: l'écart entre un nombre premier p et son successeur est plus petit que p.

Et ce commentaire qui suit
Ce qui veut dire aussi que pour n > 10: il existe plus de premiers entre 1 et n qu'entre n et 2n.
Et la conjecture de LEG, quelle est-elle ?

Maintenant, je ne peux plus suivre : tes posts sont pleins de références qui me semblent ésotériques et qui m'obligeraient vu ta cadence de production à remonter des pages et des pages en arrière.
Encore un exemple : qu'est-ce que tu désignes par Ai ?...
Pourquoi utilises-tu indifféremment a et A, b et B pour désigner la même chose ? Sachant que moi, j'utilise des minuscules pour des variables, et des capitales pour les listes, dicos...
Python est sensible à la casse : pour lui a et A, ce n'est pas la même chose...
J'ai de plus en plus de mal à te suivre...
Et là :
Pourquoi commencer par
for i,b in enumerate(GM):
et ensuite
    for a in premiers[i:]: ?
Pourquoi cette inversion subite, par rapport à tout ce qui a précédé ?

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#354 23-12-2018 13:10:36

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

Re : crible en python

excuse moi pour a et A et pour Ai comme les Pi

Et là :
Pourquoi commencer par
for i,b in enumerate(GM):
et ensuite
    for a in premiers[i:]: ?
Pourquoi cette inversion subite, par rapport à tout ce qui a précédé ?

par ce que c'est comme ça que le programme fonctionne maintenant..
avec ta fonction que tu m'as écrit..
tu peux le vérifier ; Ai est un élément premier de la liste eratostene....

D'ailleurs j'ai déjà fait l'inverse et le résultat est archi faux.

car dans cette version, ce sont les A i = n qui parcourt les 8 éléments de B= GM (''que l'on m'avais dit en 2003 groupe multiplicatif..maintenant je peut l'appeler comme tu veux...")

quelque soit A qui va parcourir B, il aura toujours son index et il n'a pas besoin de parcourir tous les élément de B(premiers) équivalent aux éléments A(premiers)

Dernière modification par LEG (23-12-2018 13:11:21)

Hors ligne

#355 23-12-2018 14:01:08

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

Re : crible en python

j'ai bien écrit avec ta fonction et ta version #v.6.2#:


  # FAMILLES POUR CHAQUE Pi
    start_time = time()
    for i,pi in enumerate(Primes_init):
        for b in (GM):
            j = pi*b
            if j%30 == 1:          # chan
 

dans le Gcrible sur lequel tu travaillais avant hier :

avec ta première fonction que j'ai mise :


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 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,
        # On crible directement avec l'index
        for idx in range(index, lencrible, a):  # index qui est réutilisé ici...
            crible[idx] = 0
            #print(j)
           
    total = sum(crible)
    lprint("crible:", crible)
    print(f"Nombre premiers criblés famille {fam} : {total} -

suite à ton exemple et tes explications tu ""as dit"" que ce sont les éléments B qui criblent en partant de leur index...

Donc maintenant, B = premier= 7,11,13,17,19,23,29,et 31 ; va bien parcourir  les éléments a qui vont cribler en partant de l'index..Non?

ton exemple du post page 14
a = 7
(31, 7)

a = 11
(47, 17) (17, 6)

a = 13
(19, 8)

a = 17
(41, 23)

a = 19
(43, 27)

a = 23
(29, 22)

Dernière modification par LEG (23-12-2018 14:11:54)

Hors ligne

#356 23-12-2018 14:07:49

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 501

Re : crible en python

Re,

Bin moi, ne sachant toujours qui était G, j'ai demandé une recherche Bibmath et je suis tombé sur :

GM {7,11,13,17,19,23,29,31}

1. Pourquoi des accolades  ?...
    Peut-être GM est-il ici : GM =[7,11,13,17,19,23,29,31], les accolades c'est pour les dictionnaires. Peut-être plus en Python 3.7 ?
    On t'a peut-être dit en 2003, ce que c'était, mais moi, 1ere fois que j'entends cette expression... J'en suis navré...
    Elle est standard, i.e normalisée ? connue de tout matheux (sauf moi) ?
2. Pourquoi t'arrêter à 31 ?.
    Moi j'en suis resté à pour qu'un nombre>30 soit premier il est nécessaire (et pas suffisant, dommage !) qu'il s'écrive
    30k+p  avec [tex]p \in [1,7,11,13,17,19,23,29][/tex] et k>= 1...
    Là, avec GM, le 1 a sauté, remplacé par le 31...

3. Grpe multiplicatif, ça parle à un matheux, par ex, un extrait de cours de crypto :

2. Le groupe multiplicatif  [tex]\mathbb{Z}/p\mathbb{Z}^*[/tex]

2.1    Les éléments générateurs
Nous avons donc vu que lorsque p est premier, le groupe multiplicatif $\mathbb{Z}/p\mathbb{Z}^*$ est égal à $\mathbb{Z}/p \mathbb{Z}$  \ $\{0\}$

Ce groupe est cyclique, plus précisément :
Théorème 2.1
Soit p un nombre premier. Alors, le groupe multiplicatif [tex]\mathbb{Z}/p\mathbb{Z}^*[/tex] est cyclique. C’est-à-dire que ce groupe peut être engendré par un un élément générateur (dit aussi élément primitif).

Théorème 2.2
Le nombre de générateurs de $\mathbb{Z}/p\mathbb{Z}^*$ est égal à $\Phi(p-1)$ ou $\Phi$ est la fonction indicatrice d’Euler.

Pas tout à fait la même chanson ?

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#357 23-12-2018 14:25:57

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

Re : crible en python

Je suis bien d'accord avec toi sur le groupe multiplicatif, et GM ...
car à l'époque de nbpremier xin 32 on ne se sert que de GM qui est un groupe  multiplicatif, où en fonction de la fam choisie, on multiplie bien les 8 nombres entre-eux pour calculer l'index des couples qui vont cribler, extraire les nombres premiers > 31, qui vont cribler à leur tour...etc etc ...je ne suis pas rentrer dans les explications de ce  crible C++ ...voila...

Bien sûr que mes explications sont lourdes...donc mal comprises pour un matheux...d'où je ne sais pas comment je dois t'écrire

GM {7,11,13,17,19,23,29,31} ,
30k+p  avec p∈[1,7,11,13,17,19,23,29] et k>= 1...
    Là, avec GM, le 1 a sauté, remplacé par le 31...

Bien sûr , 31 à la place de 1..

Ce que j'ai compris quand même, c'est comment écrire GM pour le faire fonctionner dans la fonction...
GM = 7,11,13,17,19,23,29,31

sans accolade..et autre...car erreur list...!

Je viens aussi de rectifier mon erreur d'inattention, c'est bien :

for a in (premiers):
        for b in (GM):

Dernière modification par LEG (23-12-2018 14:56:57)

Hors ligne

#358 23-12-2018 16:49:38

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 501

Re : crible en python

Re

Ce que j'ai compris quand même, c'est comment écrire GM pour le faire fonctionner dans la fonction...
GM = 7,11,13,17,19,23,29,31

sans accolade..et autre...car erreur list...!

Ah bon ?
Dans ce cas, sais tu à quel type se rattache ce GM ?
Non.
As-tu posé la question à Python ? Non ?
Dommage, il t'aurait répondu :

>>> type(GM)
<class 'tuple'>

La preuve :

>>> print(GM)
(7, 11, 13, 17, 19, 23, 29, 31)

Ici, ce tuple, pour un matheux, porte le nom de octuplet...

Avec accolades, ça ne peut pas marcher, ce serait un dictionnaire, et la structure d'un dictionnaire c'est {key0:valeur0, key1:valeur1....} ou un set (je regarderas ce que c'est exactement)
Tu as de la chance :

>>> F={7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53}
>>> F
{37, 7, 41, 43, 11, 13, 47, 17, 19, 53, 23, 29, 31}
>>> F[0]

Traceback (most recent call last):
  File "<pyshell#18>", line 1, in <module>
    F[0]
TypeError: 'set' object does not support indexing

Ça ne marche qu'avec cette utilisation

for a in premiers :
    for b in GM:

As tu bien vu ci-dessus l'ordre entré des nombres dans F et l'ordre restitué : en cela il se comporterait comme un dictionnaire non ordonné.

Avec un tuple, pas de souci... sauf qu'il est impossible d'ajouter, modifier ou supprimer un élément d'un tuple...

Revenons un peu sur ce que tu dis : erreur list ??? En français  ? Ce n'est pas Python qui te cause,  alors., ni Pycharm... D'ailleurs je n'ai jamais rencontré cette erreur en Python
Donc avec une liste, ça plante ??! Et pourquoi donc ?
Voyons ça :

premiers=[7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53] # c'est une liste
GM=[7, 11, 13, 17, 19, 23, 29, 31] # c'est aussi une liste
for a in premiers:
    print ("Avec a =",a,end="    ")
    for b in GM:
        print ((a,b),end=" ") # Affichage des couples (a,b)
    print()

Sortie :

Avec a = 7    (7, 7) (7, 11) (7, 13) (7, 17) (7, 19) (7, 23) (7, 29) (7, 31)
Avec a = 11    (11, 7) (11, 11) (11, 13) (11, 17) (11, 19) (11, 23) (11, 29) (11, 31)
Avec a = 13    (13, 7) (13, 11) (13, 13) (13, 17) (13, 19) (13, 23) (13, 29) (13, 31)
Avec a = 17    (17, 7) (17, 11) (17, 13) (17, 17) (17, 19) (17, 23) (17, 29) (17, 31)
Avec a = 19    (19, 7) (19, 11) (19, 13) (19, 17) (19, 19) (19, 23) (19, 29) (19, 31)
Avec a = 23    (23, 7) (23, 11) (23, 13) (23, 17) (23, 19) (23, 23) (23, 29) (23, 31)
Avec a = 29    (29, 7) (29, 11) (29, 13) (29, 17) (29, 19) (29, 23) (29, 29) (29, 31)
Avec a = 31    (31, 7) (31, 11) (31, 13) (31, 17) (31, 19) (31, 23) (31, 29) (31, 31)
Avec a = 37    (37, 7) (37, 11) (37, 13) (37, 17) (37, 19) (37, 23) (37, 29) (37, 31)
Avec a = 41    (41, 7) (41, 11) (41, 13) (41, 17) (41, 19) (41, 23) (41, 29) (41, 31)
Avec a = 43    (43, 7) (43, 11) (43, 13) (43, 17) (43, 19) (43, 23) (43, 29) (43, 31)
Avec a = 47    (47, 7) (47, 11) (47, 13) (47, 17) (47, 19) (47, 23) (47, 29) (47, 31)
Avec a = 53    (53, 7) (53, 11) (53, 13) (53, 17) (53, 19) (53, 23) (53, 29) (53, 31)

Ça marche !

Alors qu'as-tu fait ?

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#359 23-12-2018 17:09:15

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

Re : crible en python

bin..j'ai bien fais ce que tu indiques , avec la fonction


 for a in (premiers):
        for b in (GM):
            j = a * b
            if j%30 == fam:
 

dans le programme ci dessous qui marche bien ("et aussi vite que Goldbach de N à 2N "):


from itertools import product
from time import time


def eratostene(n):
    n = int(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 demander_N():
    n = input("Donnez N: ")
    n = int(n.strip().replace(" ", ""))
    #n = int(30 * round(float(n)/30))
    #print(f"On prend N = {n}  (30 * {int(n/30)})")
    return n


def lprint(text="", liste=None):
    if len(liste) < 250:
        print(text + str(liste))


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 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,
        # On crible directement avec l'index
        for idx in range(index, lencrible, a):  # index qui est réutilisé ici...
            crible[idx] = 0
            #print(j)
           
    total = sum(crible)
    lprint("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
    premiers = eratostene(n)
    #lprint("premiers:", premiers)
    #print(f"nombres premiers entre 7 et n: {len(premiers)}")

    start_time = time()
    # On crible
    E_Crible(premiers, n, 7)
    temps = time()-start_time
    print(f"--- Temps total: {int(temps*100)/100} sec ---")


main()
 

résultat :
====== RESTART: E:\executable algo P(30)\E_Crible_ gty_modifié mod30.py ======
Donnez N: 300 000 000
Nombre premiers criblés famille 7 : 2031596 ----- 1.21
--- Temps total: 1.23 sec ---
>>>

et avec ton ancienne version que j'ai posté hier :
résultat :

======= RESTART: E:\executable algo P(30)\CRIBLE_Eratosthène_Mod30.py =======
Donnez la valeur de n = 30k : 300 000 000
Phase d'initialisation: 0.09360027313232422 seconds ---
Bloc S2_s3 : 1.0608017444610596 seconds ---
Extraction des premiers de 7 à n : 0.07800006866455078 seconds ---

**  2031596 nombres trouvés en 1.2324020862579346 secondes **
>>>

Hors ligne

#360 23-12-2018 18:13:05

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 501

Re : crible en python

Re,

J'ai dit : avec un tuple, ça fonctionne et j'ajoute mais ce n'est pas naturel...
As-tu essayé de supprimer les parenthèses autour de premiers et de GM ? Elles sont inutiles.

J'aurais voulu voir l'essai chez toi en déclarant GM=[7,11,13,17,19,23,29,31], parce que chez moi, aucun problème...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#361 23-12-2018 18:46:13

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

Re : crible en python

ok impeccable, il marche aussi avec les crochets GM= [7,11,13...31]et sans les ( )...donc je  laisse comme ça

est-ce que tu le veux transcrit en C++...? je viens juste de le recevoir de Mr Parisse Bernard....ça déménage...

Cela serait bon comme outils sur votre site...non?

Dernière modification par LEG (23-12-2018 19:00:52)

Hors ligne

#362 23-12-2018 18:49:03

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 501

Re : crible en python

Re,

je parle des crochets [] pas des accolades {}, hein...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#363 23-12-2018 18:59:00

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

Re : crible en python

crochets, accolades,  parenthèses...et cannes à pêche ...pour moi je nage....Est-ce que tu le veux transcrit en C++, à la suite des post...?

Ce qui veut dire aussi que pour n > 10: il existe plus de premiers entre 1 et n qu'entre n et 2n.
Et la conjecture de LEG, quelle est-elle ?

la même affirmation que toi..!
En effet les deux algorithmes criblent la même limite de 7 à N : pour compter le nombre de nombres premiers de 7 à N ou de N à 2N

or, il est simple de montrer que l'algorithme d'Ératosthène comptera plus de premiers de 7 à N car il n'utilise que les nombres premiers Pn $\leqslant\sqrt{N}$ pour marquer les multiples n de P .

Alors que l'algorithme de Goldbach, pour la même limite de 7 à N comptera plus d'entiers N congru à 2N modulo P , car il utilise les nombres premiers Pn  $\leqslant\sqrt{2N}$ d'où par obligation, moins de premiers entre N et 2N....!

Ce n'est pas une conjecture, mais une évidence....tu ne crois pas....?

c'est aussi pour cela que j'en ai déduit que le nombre de nombres premiers qu'il y a entre N et 2N vaut environ $ \frac{N}{Ln (2N)}$, pour N>= 15; et non $\frac{N}{Ln (N)}$ pour Ératosthène . Cela n'engage que moi, bien entendu..

Si j'utilise le terme de crible ou algorithme de Goldbach, cela vient tout simplement que pour compter le nombre de couples (p,q) qui décompose un entier pair >= 16, en somme de deux premiers p,q on utilise le même crible en ne comptant que les nombres premiers p <=N , qui n'ont pas été marqués par ce crible...Donc :("qui peut le plus peut le moins").....sans aucune prétention, simplement un hobby...


Passe une bonne fin de soirée
@+

Dernière modification par LEG (24-12-2018 07:52:41)

Hors ligne

#364 24-12-2018 07:50:11

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

Re : crible en python

Bonjour Yoshi

est ce que tu as essayé d'inverser la boucle : a,b  en b,a:


GM=[7, 11, 13, 17, 19, 23, 29, 31] # c'est aussi une liste
premiers=[7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53] # c'est une liste
for b in premiers:
    print ("Avec a =",a,end="    ")
    for a in GM:
        print ((a,b),end=" ") # Affichage des couples (a,b)
    print()

de sorte, que c'est B = 7 , qui va parcourir les éléments de a, calculer a%30==fam, puis calculer les index, pour chaque a trouvé, a part cribler ... jusqu'à la fin , on sort de la boucle,] puis on change d'indice i+=1 , B=11...et on réitère...???

il n'y aura que 8 boucles [Bi.....> a]

Hors ligne

#365 24-12-2018 20:16:20

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 501

Re : crible en python

Re,

Je ne suis pas chez moi, jusqu'au 26, mais 450 km plus loin.
Rapidement comme ça, non !
Il y a une autre idée que je voudrais tester...

Cela dit 50 boucles sur 8 nombres ou 8 boucles sur 50 nombres, ça fait toujours 400 couples de valeurs et pratiquement un couple sur 2 à éliminer (redondance).

L'idée que je voudrais tester est de ruser avec un nombre par exemple au départ de 1000 cellules pour n=30000, ne contenant que des 1.
Au lieu de gérer 1000 cases de 1, utiliser le nombre 1000, et enlever 1 à ce nombre au lieu d'écrire 1 dans la case déterminée grâce à l'index.
Il faudrait, par contre, que je sache si j'ai affaire à un "doublon" parce que dans ce cas où dans la liste j'écrirais un 0 là ou j'en ai déjà inscrit un, j''enlèverais par contre un au nombre une fois de trop...

Ça doit être faisable...
Si ça  l'est effectivement, je réduirais autant d'accès à la liste, autant d'écriture de 0 et la sommation finale : le nombre restant donnerait automatiquement le total...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#366 25-12-2018 07:34:03

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

Re : crible en python

Bonjour Yoshi
j'attendais le père noël après 21h30 ...pour qu'il m'apporte ses idées....je te remercie et j'espère que tu vas bien en profiter .

A_)
concernant tes 50 boucles.. ok..Mais je pensais vraiment que c'était plus rapide 8 boucles sur 50 nombres ..! car il y a justement le phénomène qu'après les 8 premiers sur les 50 nombres premiers, il y a de plus en plus d'écart entre ces premiers, de ce fait la congruence du produit %30 ==fam, est plus rapprochée , d'où moins d'opérations lorsque n tend vers l'infini...Sur excel , manuellement je vais plus vite...

B_)
Si c'était faisable, effectivement la sommation finale est automatique..
Mais justement le problème des doublons n'est pas gérable...

n=3000 ; fam = 7 , Pi =7
ok : on a les 1000 [1], j'ai l'index 7,pour Pi = 7; par pas de 7, j'enlève un 1 à chaque pas de 7 et autant de 0 à la place..Sachant que je vais partir de 7 ....>1000 = (993/7) +1, le premier 1 enlevé au départ . J'ai enlevé 141 + 1 [1] . Somme = 1000 -142. ON est d'accord..? sous total = 858.

Pi = 11 pour l'index 6 ; même opération par pas de 11 de 6 à.....> 1000 ; soit :(858 / 11) + 1. 72 [1] d'enlevés... Où sont les doublons parmi ces 72 [1]....Comment tu les vois..? ou comment le programme va le savoir. ..?

Sachant que les doublons vont se répéter en fonction du nombres de pas UNIQUES par Pi...dixit le TFA..("thèoreme fond de l'arith..")..cela revient à prévoir la factorisation unique d'une cellule[1]...Imagine les conséquences....

Il y a un polynôme avec 26 variables de degré 25 ; qui ne prends que les nombres premiers...donc qui élimines les doublons....

tu peux illustrer et faire un essais : j'ai marqué les deux index de départ, [(0)] =7 pour Pi = 7 ; "0" 6, pour Pi =11


111111"0"[(0)]111111(0)111111(0)111111(0)111111(0)111111(0)111111(0)111111(0)111111(0)111111(0)111111(0)111111(0)111111(0)1
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

1) la seule chose que l'on sait: c'est que la cellule d'index 6 partagé par 11 *17  se retrouvera dans 187 cell, donc d'index 6 + 187 cellules, avec comme factorisation (7,11 et bien sûr 31) = 5797 et (5797-7)/30 = l'index 193..!

Quel est la factorisation de la cellule X = (7,11, z) le ou les doublons...?

au pif: 9 * 7 = 63  au départ de la 8ème cellule = 71 cellules; moins la cellule 0 =7 , cela fait 70 cellules :
vérification : 70*30 + 7 = 2107 ; 2107/7 = 301; 301 / 11 = Faux...   le conjoint de 7 avec 11, c'est 11 + 30 = 41.
cellule 106 ok....(105*30 + 7) est /7/11 et 41.
41 qui a pour index 23 donné par (17*41) // 30 ...c'est ingérable , comme le polynôme schmoldu...à 26 variables...

Je vais regarder de mon côté ce que donne le nombre d'opérations pour 8 boucles et n nombres: avec 6000...

Joyeux Noël cher ami...
Gilbert
@+

Dernière modification par LEG (11-02-2019 07:17:35)

Hors ligne

#367 25-12-2018 09:09:06

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

Re : crible en python

re :
POUR N = 6000, c'est faisable en 46 opérations , tu peux regarder , je disais que cela allez plus vite, car pour les 8 nombres premiers A, de la liste A, des-que A%30== 7 ,l'index est calculé, A = 31 crible;
Pour le calcule de l'index suivant, on incrémente Aide  30 qui serra obligatoirement =7%30 , et donc  re calcule de l'index..de Ai = 61..qui crible, puis Ai+30 = 61 > 73 la boucle B = 7 est fini. i += 1 , B =11

B = 11; "", 11*17 ok idx = 6, 17 crible, suivant : 11* (17+30) idx = 6+11, crible, .suivant 11*(47+30) si par exemple 77 qui n'est pas dans la liste A car il n'est pas premier; pas de problème, on incrémente de 30 Ai et suivant : 77+30 = 107 >73...fin de boucle B pour i = 1, B = 11...!

("C'est à peu près le principe de l'algorithme nbpremier c++ de 2003 , car cette optimisation est justement meilleur que nbpremier")

En inversant les deux listes du programme; les 8 boucles B du GM vont parcourir la liste A des nombres premiers d'Eratosthène                         

B = [7, 11, 13, 17, 19, 23, 29, 31]   n= 6000   Fam =7    nbcell = 6000/30 = 200 à cribler
--------------------------------------------------------------------------------------------
A = 7,,,,11,,,,13,,,,17,,,,19,,,,23,,,,29,,,,31],,,37,,,41,,,43,,,47,,,53,,,59,,,61,,,67,,71,,73]
-----------------------------------------------------------------------------------------------
7 """"  """"  """"  """"  """"  """"  """"  217].,......  ,...... ,...... ,...... ,...... ,......,427..,......  ,...... ,......,
11  """"  """"  """"  187,......,......,......,......]....., ......,......,.697.,.....,......,......,.......,......,......,.
13  """ """"  """"  """"  247..,......  ,...... ,].....,......  ,...... ,...... ,...,on saute49.. ,...... ,...... ,...... ,...... ,.....,.....,
17  """"  187 ,.....  ,...... ,...... ,...... ,...... ,]..... ,...... 697....,..... ,...... ,...... ,...... ,...... ,...... ,......  
19  """"  """"  247.. ,...... ,...... ,...... ,...... ,]..... ,...... ,...... 817...,...... ,...... ,...... ,...... ,...... ,...... ,
23  """"  """"  """"  """"  """"  """"  667.. ,]..... ,...... ,...... ,...... ,...... ,......667... ,...... ,...... ,...... ,
29  """"  """"  """"  """"  """"  667.. ,...... ,]..... ,...... ,...... ,...... ,.......667.. ,...... ,...... ,...... ,...... ,
31...217..,.....,.....,.....,.....,......,...... ,..... ,].1147.....,......,......,...... ,...... ,......,2077,.....,.....,
--------------------------------------------------------------------------------------------------------

Ce qui supprime toutes les opérations de calcule: produit et modulo pour tout Ai > 31 .
incrément = 30 : Ai + 30, +30 ...+30k  et on peut "aussi" incrémenter l'index de: Bi si c'est plus rapide...

D'où , il n'y a que les 8 boucles GM quelque soit le nombre de Ai, de la liste A .
Ainsi que les 8 opérations au maximum, des Ai <= 31, pour trouver les 8 index et ensuite : Bi * [Ai +30k]

C'est faisable...?

illustration, en partant du carré des nombres premiers Bi de la liste GM :

Exemple : on a choisie fam =1 , i = 0, Bi=7:
7*7, 7*11, (7*13) == 1%30. L’index du couple est 3 ; [7 et 13] vont cribler par pas de 7 et de 13, de 3 → n//30.

Une fois terminé on fait un break et on les incrémente de 30, pour réitérer et continuer avec Bi+30 ; (7+30 , 13 +30)qui sont bien dans la liste des Ai(premiers), (« sinon on augmente de 30 jusqu’à fin de liste des Ai(premiers) donc <= 89. »).

Ce qui donne :(Ai)² = 37*37 , calcul index et criblage, puis 43*43, index et criblage. Break ; on incrémente à nouveau ces deux Ai (37 et 73 )de 30 ; soit: 67*67, index et criblage ; puis 73*73, index , criblage ; fin pour ces deux Familles Bi[30].
On passe à Bi suivant.

Suivant Bi=11 : (11*11) == 1%30 ; index 4 et crible par pas de 11, de 4 → n/30.
Break ; on incrémente Bi de 30 ; soit Ai = 41, produit = 41*41 ; index, criblage,break et on incrémente à nouveau de 30 tant que Ai +30k est <= à  sqrt n fixé, soit 89 pour cet exemple.
Donc :71*71 , index, criblage ; fin pour cette Famille Bi[30].
On passe au suivant.
Bi suivant = 17 car la famille Bi = 13[30] a déjà été utilisé et finie….

17*17, 17*19, 17*23 == 1%30 ; calcule de l’index pour le couple (17,23)//30 = 13 le couple va cribler par pas de 17 et de 23 ; de 13 → n/30 , break, on incrémente de 30 : 17 et 23 , produit des carrés, index, criblage fin des deux Familles Bi = 17 et 23 [30]
etc ….etc.
On réitère avec Bi suivant = 19…. etc…jusqu’à la dernière Famille Bi=31[30].
A la fin on fait le total des [1] qui donnera le nombre de nombres premiers : q[n ; 2n].

le programme est un peu plus difficile, mais on supprime beaucoup d'opérations...

Dernière modification par LEG (11-02-2019 08:38:56)

Hors ligne

#368 25-12-2018 09:17:48

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 501

Re : crible en python

Re,

Noyeux Joël à toi aussi...
Je ne m'attendais pas à une réponse un 25 déc.
A) Ton objection est à examiner de près...

B) Je pensais bien que ce serait coton... Je n'espérais pas une solution obtenue d'un simple claquement de doigt.  Je suis têtu, un peu Saint Thomas et probablement un lointain descendant de Guillaume d'Orange :
Il n'est pas  nécessaire d'espérer pour entreprendre ni de réussir pour persévérer...

Sinon, j'ai une 2e idée en réserve, un peu plus ch... ou moins, c'est selon, mais probablement plus lente.
* Considérer une liste de 1000 nb 1
* Ecrire à la place un nb binaire de 1000 bits égaux à 1 (ce qui correspond au décimal $2^{125}-1$)
* transformer le bit n° idx (compté à partir de la gauche) en un 0
* Lorsque c'est fini, compter le nb de 1

2e variante (douteuse) :
....
* transformer le bit idx (en partant de la droite et en progressant de D à G cette fois) en un 0
* transformer le nombre binaire restant une fois fin en décimal

Mais tester ce genre de choses demande de disposer d'un petit confoert de programmation, ce que je n'ai pas ici...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#369 26-12-2018 07:24:36

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

Re : crible en python

Donc tu penses que même en incrémentant Ai de 30 , pour calculer l'index suivant...de la liste des Ai, ça ne ferait pas tellement gagner de temps ("il faut quand même vérifier que Ai+30 est bien dans la liste Ex 13*19; puis 13 * (19+30) faux out, donc 13*(49+30) > 73 donc out..on passe à Bi suivant =17...
Pourtant lorsque l'on incrémente Ai de 30, on incrémente par la même son idx de Bi appartenant au GM:
EXemple fam = 7: B1 = 11 ; Ai = 17 , idx = 6 ; on aura donc Ai +30 = 47 , donnera idx + 11 =17

Tu as peut être raison, car les deux algorithmes curieusement sont aussi rapides l'un que l'autre...et traduit en C++ , même temps d'exécution pour une même limite N = 128 700 000 000; en 13 secondes...!
l'un calcule des restes que l'on incrémente de 2*pi jusqu'au %30==fam, pour ensuite calculer l'idx....et l'autre calcule les produits (b*a) ....>%30 == fam ; puis idx..., et :

1)_ Criblage de l'idx par de pas $p_i\leqslant\sqrt{2n}$ , pour Goldbach .
2)_Criblage de l'idx par de pas $A_i\leqslant\sqrt{n}$ , pour Ératosthène .

Alors que G, crible avec plus de premiers que É ....? De plus, G crible de l'idx plus petit que celui de E..d'où plus de cellules à marquer...? Comme quoi cela n'influence pas beaucoup le temps d'exécution...Que ce soit en python ou en C++ .

Par contre en C++ par rapport à python il n'y a pas photo....en terme de rapidité * 500 et de limite * 4 ...! Et encore j'utilise Code:bloc qui est en 32 bits sous Windows et non en 64.... ils l'on testé en 64 bits il a mis un peu moins de 60 secondes pour n = 450 000 000 000 ce qui donne pour G de 450 GO à 900 Go...!

Un petit résultat :

Avec Goldbach ; fam 7: nombre de nombres premiers entre 510 000 000 000 et 1020 000 000 000 =
2 331 532 960 en : 55,111 secondes

Avec Ératosthène ; fam 7: nombre de nombres premiers de 7 à : 510 000 000 000 =
2 459 907 472  en : 55,158 secondes

Je les ai testé jusqu'à 1200 GO en 75 secondes chacun à 2 secondes près..

Record ou Pas : sur le site Bibm@th du plus grand nombre de nombres Premiers criblés élémentairement, entre N et 2N ..?

RÉSULTAT Pour N = 3 billions , fam = 11: par Gcrible_mod 30
  nombre de premiers criblée de 3 billions à 6 billions = 12 880 098 499 en  734,93 secondes

Par E_crible_mod30 :
Pour N = 3 billions, nombre de premiers  11 mod 30, de 7 à N : 13 542 540 483 en 735,5 secondes

Voila un bon crible de noël , Mr ..YOSHI..
@+ LEG

Dernière modification par LEG (27-12-2018 12:58:20)

Hors ligne

#370 02-01-2019 09:04:19

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

Re : crible en python

Bonjour à tous
j'espère que 2019 verra tous vos projets se concrétiser, et qu'elle vous apporte le meilleur de cette nouvelle année...
@Yoshi je te remercie pour toute l'aide que tu m'as apporté en 2018, en espérant que 2019 te le rende passe une très très belle année.
A +
Gilbert.

Le crible converti en C++ a une limite de 7500 000 000 000 , et pour Goldbach de N à 2N = 15 000 000 000 000 .
je pense que même en améliorant Ce crible Ératosthène , comme indiqué ci dessus  pour l'optimiser, change de beaucoup sa limite et vitesse.. Mais c'est comme cela qu'il devrait fonctionner, en incrémentant de 30 les Ai> 31.

pour info:
Crible É
Pour n = 6000 mds, nombre de premiers  13 mod 30, 26 422 717 616 en 1 677,97 secondes
Pour n =7500 mds, nombre de premiers 13 mod 30, 32 770 358 492 en 2142,95 secondes

Grible G, pour fam = 13
Pour n = 6000 mds , nombre de premiers  17 mod 30, entre 6000 et 12 000 mds = 25 161 218 215  en 1 625,3 secondes
Pour n = 7500 mds , nombre de premiers  17 mod 30, entre 7500 et 15 000 mds = 31 217 840 128  en 2181,1 secondes

Dernière modification par LEG (11-02-2019 08:44:10)

Hors ligne

#371 14-01-2019 14:14:22

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

Re : crible en python

Bonjour @Yoshi

je met ci dessous le crible Ecrible Ératosthène en C++, que Mr B Parisse à eut la gentillesse de transformé , sur la base de ton programme Python.
il faut faire attention au ['i] où il faut enlever l'apostrophe ' que j'ai dû mettre pour pouvoir l'éditer.


// -*- compile-command: "/usr/bin/g++ -g goldbache.cc" -*-
#include <vector>
#include <iostream>
#include <cmath>
#include <stdlib.h>
#include <time.h>
using namespace std;
// fill Erathosthene sieve crible for searching primes up to 2*crible.size()*32+1
// crible is a (packed) bit array, crible[i] is true if 2*i+1 is a prime
// crible must be set to true at startup
void fill_crible(vector<unsigned> & crible,unsigned p){
  crible.resize((p-1)/64+1);
  unsigned cs=crible.size();
  unsigned lastnum=64*cs;
  unsigned lastsieve=int(std::sqrt(double(lastnum)));
  unsigned primesieved=1;
  crible[0] = 0xfffffffe; // 1 is not prime and not sieved (2 is not sieved)
  for (unsigned i=1;i<cs;++i)
    crible[i]=0xffffffff;
  for (;primesieved<=lastsieve;primesieved+=2){
    // find next prime
    unsigned pos=primesieved/2;
    for (;pos<cs;pos++){
      if (crible[pos/32] & (1 << (pos %32)))
  break;
    }
    // set mutiples of (2*pos+1) to false
    primesieved=2*pos+1;
    unsigned n=3*primesieved;
    for (;n<lastnum;n+=2*primesieved){
      pos=(n-1)/2;
      crible[(pos/32)] &= ~(1<<(pos %32));
    }
  }
}
unsigned nextprime(vector<unsigned> & crible,unsigned p){
  // assumes crible has been filled
  ++p;
  if (p%2==0)
    ++p;
  unsigned pos=(p-1)/2,cs=crible.size()*32;
  if (2*cs+1<=p)
    return -1;
  for (;pos<cs;++pos){
    if (crible[pos/32] & (1<<(pos%32))){
      pos=2*pos+1;
      // if (pos!=nextprime(int(p)).val) CERR << "error " << p << endl;
      return pos;
    }
  }
  return -1;
}

typedef unsigned long long ulonglong;

size_t GCrible(const vector<ulonglong> & premiers,ulonglong n,int fam){
  int cl=clock();
  size_t lencrible=n/30,nbpremiers=premiers.size();
  vector<bool> crible(lencrible,true);
  // ulonglong n2=2*n;
  vector<ulonglong> indices(nbpremiers);
  for (size_t i=0;i<nbpremiers;++i){
    ulonglong p=premiers[i];
    ulonglong produit;
    int GM[]={7,11,13,17,19,23,29,31};
    for (size_t j=0;j<sizeof(GM)/sizeof(int);j++){
      produit = p*GM[j];
      if (produit %30==fam){
  produit /= 30;
  break;
      }
    }
    indices[i]=produit;
  }
  ulonglong nslices=lencrible/3000000,currentslice=0;
  if (nslices==0) nslices=1;
  for (;currentslice<nslices;++currentslice){
    size_t slicelimit=currentslice+1;
    slicelimit=slicelimit==nslices?lencrible:(currentslice+1)*(lencrible/nslices);
    for (size_t i=0;i<nbpremiers;++i){
      ulonglong p=premiers[i];
      size_t index;
      for (index=indices[i];index<slicelimit;index+=p)
  crible[index]=0;
      indices[i]=index;
    }
  }
  size_t total=0;
  for (size_t index=0;index<lencrible;++index)
    total += int(crible[index]);
  cout << "Nombre premiers criblés famille " << fam << " plus petits que "<< n <<": " << total << " time " << (clock()-cl)*1e-6<< endl;
  return total;
}

int main(int argc,char ** argv){
  vector<unsigned> crible;
  ulonglong N;
  int fam=1;
  if (argc>1){
    N=atoll(argv[1]);
    if (argc>2)
      fam=atoi(argv[2]);
  }
  else {
    cout << "Syntaxe " << argv[0] << " N fam. Donnez N puis fam: " ;
    cin >> N;
    cin >> fam;
  }
  double sqrtN=unsigned(std::sqrt(double(N)));
  fill_crible(crible,sqrtN);
  vector<ulonglong> premiers;
  for (ulonglong p=7;p<=sqrtN;){
    premiers.push_back(p);
    p=nextprime(crible,p);
    if (p==unsigned(-1))
      break;
  }
  GCrible(premiers,N,fam);
  cin>>N;
}
 

Ce qui permet d'avoir les deux cribles E et G, en C++, par famille arithmétique de raison 30
@+
Leg

Dernière modification par LEG (11-02-2019 08:40:49)

Hors ligne

#372 17-03-2019 16:56:57

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

Re : crible en python

Bonjour et Salut @Yoshi.

si tu superposes le criblage des cellules [1] avec le crible G de Goldbach sur le même criblage  crible É des cellules [1]  par exemple fam {1} pour les deux cribles , et tu prends n = 3000, ensuite tu re cribles avec crible G pour n+15; inutile de re cribler Ératosthène qui te donneras les mêmes [1] premiers . Ce qui et normal la racine de n ne change pas  . Tu vas trouver l'anomalie du raisonnement absurde de la conjecture de G....!

mais en rouge les 1 qui se superposent G esur É , et en bleu les 1 de la ligne en dessous de G qui se superpose à nouveau avec É ...

puis tu regardes ce qui c'est passé, dans le même plan vertical entre les deux criblage de G, donc pour n et n+15...

si tu veux le document , tu me le fais savoir par mail. Car je ne peux le poster publiquement pour l'instant.

à+

Dernière modification par LEG (21-03-2019 16:48:17)

Hors ligne

#373 23-03-2019 07:04:56

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

Re : crible en python

Re Salut @Yoshi

Ecris à yoshik _at_ no-log.org
(Remplacer _at_ par @)

c'est fais..
@ +
leg

Hors ligne

#374 25-03-2019 06:58:27

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

Re : crible en python

Salut @Yoshi
En Définitive le criblage de (l'Ensemble C) , Ec est surjectif sur Ep, (l'ensemble P).
l'image de Ec est surjectif sur Ep.
Si l'image de Ec est vraie , Ep est vraie....  non?

Hors ligne

#375 25-03-2019 08:32:11

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 501

Re : crible en python

Re,

Boufre !
Tu m'en poses des questions !...
Il y a des dizaines d'années que je n'ai pas manipulé cette notion de surjection, faut donc que je me replonge dedans...
En attendant, voilà ce qu'en dit le dico de Bibmath :
http://www.bibmath.net/dico/index.php?a … ction.html

l'image de Ec est surjective sur Ep

Questions
1. Qu'est-ce exactement (ensemble) EC ? Que contient-il ?
2. Qu'est-ce exactement (ensemble) Ep ? Que contient-il ?
3. Tu utilises le terme d'image. Tu le prends bien dans son sens mathématique, ? C'est à dire si on considère deux ensembles E et F une fonction f de E dans F, qui à un élément x de E fait correspondre un élément y, noté f(x), de F, x est l'antécédent f(x) l'image...

Je ne crois pas dans ce cas que ta formulation ait un sens : une fonction peut être surjective, pas un élément et donc une image au sens mathématique.

Il va te falloir définir très précisément la fonction f qui à un élément de Ec associe un élément de Ef...
Après quoi, on verra si la fonction en question est surjective ou pas...

Qu'est ce que signifie  : Si l'image de Ec est vraie ?
Dans quel cas dis-tu qu'une image est vraie (et on en revient à la définition d'une image pour toi).

J'ai lu tous tes documents. A mes yeux, ils ne répondent pas à la structure attendue par un memorandum sur la démonstration de la conjecture de Goldbach... Le document final proposé ne me parait pas assez didactique : les pointures dans ce domaine, déterminent en 1 ou 2 min si elles vont continuer à lire ou pas...
Il faut pouvoir éveiller leur intérêt très vite, d'autant qu'un "amateur" qui se pointe et annonce qu'il a résolu une conjecture qui résiste depuis 1742, d'entrée de jeu, ça laisse dubitatif...

Je vais donc m'atteler à la rédaction d'un plan détaillé que je te communiquerai et dont tu développeras les "parties techniques" qui te concernent et laissées vides...
Ça te va ?

Jusqu'à présent, ce qu'elle énonçait exactement ne me dérangeait pas trop : je me contentais de programmer... Mais maintenant les choses sérieuses commencent, alors je suis allé rafraîchir ma mémoire et je n'ai trouvé que ça :
Tout nombre entier strictement positif peur être écrit comme la somme d'au plus 3 nombres premiers
(lettre de Goldbach à Euler)
ou http://villemin.gerard.free.fr/ThNbDemo/GoldbaPr.htm

Ce que j'ai retenu de tout ce à quoi j'ai participé :
tu calcules le nombre de nombres premiers entre n = 30k et 2n et tu les répartis en 8 familles que tu peux dénombrer et lister.
Quel rapport avec la conjecture de Goldbach citée ci-dessus ?
Il y en a une autre que Wikipedia (par ex) n'est pas foutu de citer ?

@+


Arx Tarpeia Capitoli proxima...

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 (donner le résultat en chiffres)?
cinquante et un plus trente neuf
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