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 (donner le résultat en chiffres)?
trente et un moins deux
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
11-12-2018 16:51:13

re suite à une idée :
Peut être qu'il faut nommer 8 variables,créer une boucle for i...range, après l'instruction :

for i,pi in enumerate(Primes_init):
 pi = premiers
vp = 7
 j = vp *= pi
 
     while j%30 != fam:
         vp += increm
     
       increm = vp += 4 , vp+= 2, vp+= 4, vp+= 2, vp+= 4, vp+= 6, vp+=2
 

ce n'est peut être pas comme cela qu'il faut faire...

ou bien:

pour calculer le produit j de chacune des variables vp par pi ; tant que

 while j%30 != fam:

variables:
a=7  ... ..a*=pi != 1%30
b=11 ... ..b*=pi != 1%30
c=13
d= 17
e=19
f=23
g=29
h=31

car je suppose que l'on ne peut pas incrémenter une variable  i = 7  calculer le produit i*pi et on incrémente i tant que (i *pi) est différent de fam %30 == 1
i += 4,+= 2,+= 4,+= 2,+= 4,+= 6, +=2

puis si i*pi == 1%30, on calcule l'index ..etc on crible

PS, j'ai remis au #post 303 ci-dessus ta version #"v6.2# que tu connais parfaitement. et à modifier , j'ai repris donc les explications par rapport à ta version ..

LEG
11-12-2018 14:34:25

re: Je pensais qu'avec les exemples tu avais compris

A ) on va remplacer les (restes de 2n par pi) et pour chaque premier <= sqrt de 2n..ok enumeré par la fonction

B) on va calculer le produit de chaque élément de la liste des variables premières vp par pi et : pour chaque premier <= sqrt de n ok....

tu penses que lorsque la fonction

for i,pi in enumerate(Primes_init):

énumère les premiers , pour chaque premier: je ne peux pas calculer le produit de chacune des variables  de vp ou autre, afin d'utiliser ce produit.....????

donc pour le ou les produits :vp * pi
 
produit j = Pi * vp..............> tant que:  j %30 != fam:
c'est à dire :

while j % 30 != fam:
     Pi *= vp

python ne pourrait pas faire ça....???
..... voila pourquoi ils utilisent C++ pour les algorithme de crible...non ?

il faut pas l'appeler list mais variables alors...

Dans eratosthène mod30 on utilise l'index des produits pour cribler par pas de premiers et on a, obligatoirement besoin pour chaque premier <= sqrt de n extrait au début par eratosthène:  de ce groupe vp des 8 nombres premiers, appartenant à
[7 ; 31] et ce quelque soit l"une des 8 familles que l'on veut cribler..

c'est simple je veux cribler la famille 13 mod30 , avec pi = 7 ; ("donc barrer les multiples de 7")
il me faut bien partir de l'index du  produit = pi * vp; congru à 13 mod30

7*7 = 49   pas bon
7*11 = 77  pas bon
7*13 = 91 pas bon
7*17 = 119 pas bon
7*19 = 133 == 13%30  ...ok calcul de l'index 133//30 = 4
je pars de 4 et je crible par pas de 7 de 4 ......> n/30 = 30 par exemple

11110111111011111101111110111.n terminé pour pi = 7
je réitère avec pi = 11

11*7 = 77  pas bon
11*11= 121  pas bon
11*13 = 143  pas bon
11*17 = 187  pas bon
11*19 = 209  pas bon
11*23 = 253  == 13%30  ...ok calcul de l'index 253//30 = 8

je pars de 8 , je crible par pas de 11 de 8......> à 30..

11110111011011111100111110111.n terminé pour pi = 11

etc...on réitère avec 13.....

yoshi
11-12-2018 13:26:17

Re,


Pas assez synthétique pour aller vite...
Déjà, là, ça commence mal :

1) je veux calculer le produit de chacun des éléments de list ,

Normalement, un matheux parle de produit de truc... par bidule : truc * bidule
J'ai relu 3 fois, rapidement il est vrai, et je n'ai toujours pas trouvé par quoi tu multiplies chaque élément de [7,11,13,17,19,23,29,31]...

Autre remarque Python est très (trop !) permissif. Ce que tu écris là ne devrait pas passer  :
list = [7,11,13,17,19,23,29,31], parce que list est une fonction interne à Python, un mot "réservé", quoi.
list((1, 2, 3)) --> [1, 2, 3 ] transforme un tuple en liste.

Et dans l'autre sens : tuple([1, 2, 3 ]) --> (1, 2, 3)

@+

LEG
11-12-2018 05:52:20

Bonjour @Yoshi
effectivement tu as parfaitement compris qu'avec ma list de 8 nombres premiers ce n'est pas ce que tu m'as indiqué..

voici ma liste de variables vp = 7,11,13,17,19,23,29,31 qui permet de calculer le produit de pi * vp

tu connais parfaitement le programme version "v 6.2# ci dessus,  puisque tu me l'as fait...Donc à partir de la ligne :


la suite du programme ne changera pas on remplacera reste par produit soit :

Mais attention, on changera la première ligne de Eratosthène qui va cribler jusqu' la sqrt de n et non de 2n
Ce qui donnera par obligation :


def eratostene(n):
  n = int(n**0.5)

En résumé, on va faire avec produit = vp * pi ce que l'on fait avec reste que, dans ton programme on a apelé j
C'est pour cette raison qu'il nous faut la list des 8 premiers [7;31] 1, n'est pas premier.

*******************************************************************
on a entré:
n = 3000

on a extrait les premiers avec ératostene < sqrt n et retourner les premiers[3:]

on a initialisé les 1 , 3000 /30 = 100, soit 100 cellules de 1

Exemple voila ce que cela donnerai à partir de la fonction 

for i,pi in enumerate(Primes_init):

:
puis: on a vp [7 ; 31]

je prends pi = 7

je calcule le produit j = vp*pi

vp *7……….donc on peut avoir 8 produits au maximum, tant que le produit %30 != 1 car on crible la fam 1.

[7*7, 7*11, 7*13 == 1%30 ]; donc ok et je n’ai pas besoin d’aller jusqu’à vp = 29 pour calculer 7*29, d’accord….

Puis je vais calculer son index: j = 91 , 91//30 = 3
Que Je positionne cellule 3 et je crible par pas de premiers = 7…de 3 à n//30 on remplace les [1] par [0] tous les 7 pas….etc… on réitère avec pi = 11…..premiers <= sqrt de n et non de 2n, car c’est Eratosthène….modulo 30

[11*7,11*11 == 1%30 ]; ok
calcul de l'index :
j //30 = 4
que l'on positionne cellule 4, crible par pas de 11 de 4 à n//30 ...etc on réitère avec pi = 13....

13*7 == 1%30 ok, position index = 3, crible par pas de 13 de 3....>n//30 ...on réitère pi = 17 ...

[17*7, 17*11, 17*13, 17*17, 17*19, 17*23 == 1%30 ]; ok position index = 13, crible par pas de 17de 13....>n//30 ...etc

********************************************************************
On supprime donc les lignes en rapport avec 2n et /ou reste=2n%pi
Ce programme serra nommé ECrible , E pour Eratosthène mod30.

l'explication est : deux cribles:

E criblera par Famille les premiers de 7 à N.. la famille 1 où 1 n'est pas premier commencera à 31.

G criblera  par famille de 1 à N en partant du reste et non du produit...car on crible les congruents de Pi...et non les multiples..etc, donc les premiers de N à 2N.

Ils ont la même propriété .!
d'où on peut affirmer que le nombre de nombres premiers G(n) de N à 2N vaut au minimum N / log 2N
par conséquent $pi(2n)$ vaut environ : [(N / log N) + (N / log 2N)] lorsque N tend vers + l'infini....

yoshi
10-12-2018 19:22:18

Re,

Allez explique-toi quand même, en termes aussi clairs et précis que possible : pas le pourquoi tu veux faire ça, mais techniquement, que cherches-tu à faire avec tes tuples

Et si, on peut multiplier une liste ou un tuple par un nombre : [1,2,3]*3 --> [1, 2, 3, 1, 2, 3, 1, 2, 3] ; (1,2)*3 --> (1, 2, 1, 2, 1, 2)
Ou encore :
[(1,2)]*3 ---> [(1, 2), (1, 2), (1, 2)]  ;    [[1,2,3]]*3 --->  [[1, 2, 3], [1, 2, 3], [1, 2, 3]]
Mais ce n'est certainement pas ce que tu attends...

@+

LEG
10-12-2018 18:12:57

ok @Yoshi
je comprend, mais je suis bien obliger de dire la vérité..je ne vais quand même pas m'octroyer un travail que je n'ai pas fais ..
Ceci dit, ça fait trois jours que je bataille pour modifier trois lignes du programme et je n'ai toujours pas trouver la réponse ...ni avec un ou des tutos Python, qui me font tourner en rond...à part me dire que l'on ne multiplie pas une liste par un nombre ou que c'est un tuple dont les valeur ne sont pas modifiable , C'est bien pour ça que je l'ai utilisé et comment on utilise les valeurs pour calculer le produit pour chaque premiers appelé..???? peau de balle et variété...

Merci quand même
cordialement
leg

yoshi
10-12-2018 15:18:59

Salut,

Encore une fois, tu tombes mal : décembre, mars, juin septembre sont des mois délicats puisque j'ai ma revue trimestrielle sur les bras...
Je m'apprêtai à te répondre vite fait sur le message d'erreur, quand j'ai vu : https://www.developpez.net/forums/d1920 … me-crible/, alors je me suis abstenu...
J'aurais répondu de toutes façon, la même chose.

Cela dit, je prends le risque d'être mauvaise langue, tu as déclaré :
- ne pas être le programmeur,
- que le prg est dû à ton petit-fils.

Alors tu as de fortes chances :
* de te faire renvoyer vers un tuto de Python,
* de te te faire renvoyer vers ton petit-fils...

Bonne chance

@+

LEG
10-12-2018 07:15:23

Bonjour
j'ai un petit souci: le but étant d'avoir deux cribles équivalents; pour cribler de N à 2N "Goldbach" et de 7 à N "Eratosthène" :
Afin de justifier les deux fonctions relatives à $\pi(n)$ et $G(n)$ : $\frac{n}{log . n}$ et $\frac{n}{log . (2n)}$
Voici la partie que je voudrai modifier pour utiliser GCrible de Goldbach dans Ecrible Eratosthène :

Voici la partie du progr origine  que je dois modifier:
1)    On remplacera la première ligne de def eratostene

def eratostene(n):
    n = int((2*n)**0.5) par n = int(n**0,5)

*****************************


## V. 6.2 ##

def eratostene(n):
    n = int((2*n)**0.5)  ## ligne à modifier  ##
    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
    #print(premiers)
    return premiers[3:]

def CribleG3Y_mod30(n):
    # INITIALISATION
    global nombres,nbcell
    start_i= time()
    Primes_init = eratostene(n)
    nn,nbcell = n*2,n//30
    nombres = []
    for i in range(1):
        nombres.append([1]*nbcell)
    P8 = {1:0}                       #pour 8 fam remettre les 8[1,7,...,29]
    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):      
       j = nn%pi
       debut,fin,pas = j+pi*(1-j%2),min(pi*30,n),pi*2
       Fam = [0]                   #pour 8 fam remettre les 8[0,0,...,0]
       for j in range(debut,fin,pas):
           if j%30 == 1:          # changer le paramètre pour une fam choisie
             fam = P8[1]      # changer le paramètre pour une fam fxée , pour P8fam remettre [j%30]
             if not Fam[fam]:
                Fam[fam] = 1
                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)
    #print(j)

 

#################################################################

Voici la partie que je veux modifier mais qui ne marche pas :

là on crible pareil,  mais on n’a plus besoin de calculer le reste r de 2n par premiers…
Il faut par contre, une fonction tableMulti pour calculer le produit des 8 variables de vp = {a=31,b=7, c=11, d=13, e=17, f=19, g=23, h=29}
Par pi, et que l’on réitèrera. Pour chaque premier…
De sorte que le produit j = pi * vp ,  pour chaque premier , on calculera ensuite l’index…pour cribler ;  au lieu du reste, dans Goldbach.
et ensuite que : j %30 == 1

exemple :
n = 3000 on a initialiser les 1 , 3000 /30 = 100, soit 100 cellules de 1
je prends premiers = 7

je calcule J = vp *7……….donc 8 produits au maximum, en vérifiant si j %30 == 1 car on crible la fam 1.

7*1 , 7*7, 7*11, 7*13 == 1%30 ; donc ok et je n’ai pas besoin d’aller jusqu’à pi = 29  pour calculer 7*29, d’accord….
Puis je vais calculer son index j = 91 , 91//30 = 3

Je positionne cellule 3 et je crible par pas de premiers = 7…de 3 à n//30  on remplace les [1] par [0] tous les 7 pas….etc… on réitère avec premiers = 11…..premiers <= sqrt de n et non de 2n, car c’est Eratosthène….modulo 30

**************************

le reste du programme, ne change donc pas.



Et ensuite je le ferai ...si possible...en C++ comme ci- dessus post d'hier .....

LEG
08-12-2018 20:18:49

Bonjour
Alors @Yoshy ...du boulots..
voila le programme fait en C++ par une âme charitable de l'univ - grenoble-Alpes
il envoie et j'ai testé pour N = 60 mds temps 120 secondes

je te met le programme car je dois bien ça sur  ton forum...


// -*- compile-command: "/usr/bin/g++ -g goldbachs.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 reste=n2 % p;
    if (reste %2==0)
      reste += p;
    ulonglong pi2=2*p;
    while (reste %30!=fam)
      reste += pi2;
    reste /= 30;
    indices[i]=reste;
  }
  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 << " entre "<< n << " et " << n2 <<": " << 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 sqrt2N=unsigned(std::sqrt(2*double(N)));
  fill_crible(crible,sqrt2N);
  vector<ulonglong> premiers;
  for (ulonglong p=7;p<=sqrt2N;){
    premiers.push_back(p);
    p=nextprime(crible,p);
    if (p==unsigned(-1))
      break;
  }
  GCrible(premiers,N,fam);
  cin>>N;
}
 

installer codeblocks sous windows (selectionner le setup codeblocks + mingw pour installation)
Puis File>New>Empty File
puis Build>Compile et Run

Passe une bonne soirée A+
Cordialement LEG

leg.01
23-10-2018 20:01:02

Bonjour Yoshi

1) c'est exact, mais je ne pouvais pas modifier l'erreur de la ligne :
# On crible directement à partir de l'index avec pi
par rapport au message #296

donc tu peux supprimer le #299.

2) Mais, le nouveau code dans son intégralité a bien été publié #293.
avec cette phrase erronée "# on crible directement avec le reste "

Pour ta question personnelle , ce n'est pas moi qui vais te dire le contraire car j'ai du mal à digérer que les programme doivent être écrit en anglais, alors que la langue Française est largement plus riche en nuances... que cette langue pourrie....! Ca n'engage que moi...!

Il en est de même des démonstrations Mathématique qui doivent être publiées en anglais et non dans la langue du pays d'origine.
Jusqu'à preuve du contraire c'est pas les anglais qui ont découvert les Mathématiques , ni le fil à couper le beurre.....

yoshi
23-10-2018 08:13:05

RE,

Copie conforme du message #296.
J'ai eu (et ai toujours) d'autres chats à fouetter.
Quelques remarques :
1. Il aurait été bien que tu publies  le nouveau code intégral et pas un petit morceau,
2. Là, c'est personnel : je ne supporte pas, que dans la programmation, pour la raison que le langage est en Anglais, on mette aussi les noms des variables voire des fonctions ou des classes auss en anglais i (j'en ai déjà discuté avec mon neveu : lui, il considère que c'est normal, moi je trouve que c'est au mieux du snobisme, au pire une capitulation devant l'impérialisme... de la langue anglaise).
3. A quand une communication à l'Académie des Sciences ou à Cédric Villani ? ^_^

@+

leg.01
22-10-2018 14:57:37
leg.01 a écrit :

De ce que j'ai compris , il a repris tes idées sur ta dernière version , pour l'adapter à son programme la partie s2 s3 et la  fin pour le comptage des 1: total = sum(crible)
car avant il mettait 3 fois plus de temps que ta dernière version.

tout est là dedans ... et on n'à plus besoins "des pfam"


  if reste % 2 == 0:
      reste += premier
    pi2 = 2*premier
    while reste % 30 != fam:
      reste += pi2
    # Ensuite on divise ri par 30 pour obtenir l'indexe
    reste //= 30
    # On crible directement à partir de l'index avec pi
    for index in range(reste, lencrible, premier):
      crible[index] = 0

  total = sum(crible)
 

LEG
04-10-2018 18:51:14
yoshi a écrit :

RE,
Le 0 n'a rien à faire dans un crible, pourtant...
Curieux !
@+

je suppose que tu fais allusion à l'index = 0

Ce qui est vrai , car on travaille par famille et la famille en question dans ce crible est la famille 1, donc si le reste de 2n%Pi = 1; l'index de 1 par 30 serra bien =  à 0 .

d'où la première cellule [1] a pour indice 0 , la cellule d'indice 1 vaut 31 ; 61 ;....etc 1 + 30k.

Si je crible la famille 7, la cellule d'indice 0 vaut 7 ; puis 37 ; 67 ;..etc 7 + 30k. Donc si le reste de 2n%Pi est 7 , l'indexe = 0.....etc

LEG
04-10-2018 18:33:27

re : pour info, j'ai remplacer le crible _G(n), qui crible de 0 à n... de la première page par la version modifiée . qui s'inspire de la dernière version ci-dessus qui crible par famille ... GCrible(premiers, n, 1) il suffit de remplacer le 1 par {7,ou 11,13,17,19,23, ou 29}
@+

leg.01
03-10-2018 21:02:51

De ce que j'ai compris , il a repris tes idées sur ta dernière version , pour l'adapter à son programme la partie s2 s3 et la  fin pour le comptage des 1: total = sum(crible)
car avant il mettait 3 fois plus de temps que ta dernière version.

tout est là dedans ... et on n'à plus besoins "des pfam"


  if reste % 2 == 0:
      reste += premier
    pi2 = 2*premier
    while reste % 30 != fam:
      reste += pi2
    # Ensuite on divise ri par 30 pour obtenir l'indexe
    reste //= 30
    # On crible directement avec l'index
    for index in range(reste, lencrible, premier):
      crible[index] = 0

  total = sum(crible)
 

Pied de page des forums