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)?
vingt neuf plus quatre-vingt 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)

Wiwaxia
28-09-2020 17:07:07

@ 48PierrelePetit

Bonjour,

48PierrelePetit a écrit :

... Avec la commande pfgw64 -od -qp(200000000) ( programme pfgw64 installé sur mes PC ) pfgw programme développé par primeform group, j'obtiens en moins d'une seconde chrono 4222234441 pour le 200 millionième nombre premier et pareil pour tout grand nombre premier ... / ...
J'ai testé le programme suivant en utilisant PFGW64 qui fonctionne sous DOS pour Windows.
Le programme est écrit dans un fichier pro.txt et la commande sous DOS est pfgw64 pro.txt.
... / ...
Qui donne après 14 minutes et 35 secondes les réponses suivantes :
2 038 074 743 pour p(100 000 000)

Il semble qu'il y ait une incohérence dans les délais de calcul annoncés, à moins que quelque chose ne m'ait complètement échappé dans la détermination du nombre premier de rang (N)... Peut-être s'agit-il de deux algorithmes différents ?

La première donnée incite à se documenter à fond sur le logiciel en cause !

LEG
28-09-2020 15:50:50

@48pierrelePetit

Cela semble donner une proportion moyenne de premiers 1 modulo 30 de 1/8, et aussi 1/8 pour les -1 modulo 30,     
Merci à tous et bonne journée

C'est normale il y a 8 familles de nombre premier >5 ,  de la forme 30k + i
Et comme l'algorithme qui crible ses 8 familles avec le même nombre de nombre premiers P inférieur à racine de n, est le même; tu as par conséquent une densité moyenne de 1/8 par famille .

LEG
28-09-2020 14:30:25

Bonjour

===== RESTART: E:\Documents\Conjecture de Goldbach\Crible_ Era_gty_mod30.py ====
Donnez N: 16000000
Nombre premiers criblés famille 13 : 128937 ----- 0.07
--- Temps total: 0.09 sec ---
>>>

Ce programme @Yoshi, à la base il était était archaïque ...toi tu l'as refait entièrement à partir de l'algorithme ....

Tout comme celui que j'ai mis ci-dessus qui donne le nombre de couples P+q = 2n ...c'est quand même toi qui me l'a fait intégralement en python ...

En définitive ce qui est long c'est d'écrire tous les nombres premiers criblé < n fixé et non de calculer leur nombre .

Ensuite il est clair que certain algorithme et programme sont très rapide en fonction du langage, de la complexité de l'algorithme, du calculateur ou Pc utilisé..

ex : le 400 milliardième premier est : The 400,000,000,000th prime is 11,618,595,583,891; en moins de 1,5 secondes et je suppose qu'il y a plus rapide...

Bref disait moi et non Pépin ... @Wiwaxia ou 48PierrelePetit y'en a t'il un, pour retranscrire en C++ le crible en python que j'ai mis  ci-dessous... si possible bien entendu...

Actuellement pour n = 16 000 000 000 il me donne :

======= RESTART: E:\Documents\Conjecture de Goldbach\Crible_EG2_mod30.py =======
Donnez n: 16000000060
Nombres P' non congruent à [pi] de 1 à 16000000060 famille 7, nombr de couples p+q=2n: 15 133 152 ----- 227.22 secondes
>>>
Donnez n: 16000000075
Nombres P' non congruent à [pi] de 1 à 16000000075 famille 7, nombr de couples p+q=2n: 14 349 243 ----- 211.01

Donnez n: 16000000090
Nombres P' non congruent à [pi] de 1 à 16000000090 famille 7, nombr de couples p+q=2n: 13 131 524 ----- 213.3
>>>


Avec les nombres premiers Pn et qn : Pn = 30k+7 et qn = 30k +13

En utilisant la fonction modifiée $\pi(n)$ pour le nombre de premiers 30k +7 et la constante des nombres premiers jumeaux $C_2$ :
Nombre de premiers $30k + 7  < 16000000030 = 89 101 240$
l'estimation me donne 6 426 691 couples qui représentent $2n = 32 000 000 060$ en somme de deux nombres premiers p+q .

Pratiquement la moitié du nombre réel de couples p+q ... Ce qui est quand même très curieux,  car il suffit de multiplier par 2 le résultat de la fonction d'estimation pour obtenir une moyenne générale ...

La fonction est : pour un nombre de nombre premiers de la forme de $30k + i$ ; $i\in(1,7,11,13,17,19,23,29)$ et une limite fixée : $n = 15k + i$

$\frac{\pi(n)}{ln\:(\pi(n))}$ sachant aussi que cette fonction indiquera le nombre de couples qui représenteront la limite suivante 2n + 30 sans avoir le besoins de cribler car la fonction est réccurente...

Elle représente aussi le nombre d'entiers A pas obligatoirement premiers de la forme 30k +7 en progression arithmétique de raison 30, non congrus modulo P : $(2n+30)\not\equiv{A}[P]$ avec $P\leqslant\sqrt{2n+30}$

Si on prend les trois limites $n$ suivante on aura une moyenne de 14 204 639 couples = 2n ; pour une estimation de 12 853 383 .

======= RESTART: E:\Documents\Conjecture de Goldbach\Crible_EG2_mod30.py =======
Donnez n: 16000000105
Nombres P' non congruent à [pi] de 1 à 16000000105 famille 7, nombr de couples p+q=2n: 13 467 806 ----- 210.81
>>>
======= RESTART: E:\Documents\Conjecture de Goldbach\Crible_EG2_mod30.py =======
Donnez n: 16000000120
Nombres P' non congruent à [pi] de 1 à 16000000120 famille 7, nombr de couples p+q=2n: 14 334 132 ----- 243.58
>>>
======= RESTART: E:\Documents\Conjecture de Goldbach\Crible_EG2_mod30.py =======
Donnez n: 16000000135
Nombres P' non congruent à [pi] de 1 à 16000000135 famille 7, nombr de couples p+q=2n: 16 239 823 ----- 186.15
>>>
Comme quoi ce crible / algorithme de Goldbach par famille $30k + i$, cache bien des choses...

yoshi
28-09-2020 13:52:47

Bonjour,

Je vais me répéter...
Python est langage interprété, haut niveau, donc peu rapide...

Je précise :
quand j'ai écrit : un vrai TGV, je comparais la vitesse d'exécution de ce script avec d'autres sur le même sujet, écrits en Python et non avec le langage tartempion...
Seule dérogation : lorsque j'ai comparé le temps mis par ce script Python avec le script de Pierre-le-Petit en Visual Basic, programme réputé - à juste titre - plus rapide que Python, parce que le temps annoncé (plusieurs minutes) m'avait surpris

Python est lent, certes, mais je l'apprécie pour sa clarté, pour la palanquée de bibliothèque tierces présentes en natif ou installables, sa lisibilité satisfaisante même pour quelqu'un qui ne connaît pas le langage...
Petit bémol : son parti pris de "typage dynamique" qui, à cause de sa souplesse, oblige à faire encore plus attention aux types et aux noms de variables...

Je rectifie ce qu'a dit LEG : je n'ai fait qu'optimiser (j'avais divisé par 30 la vitesse de travail), un script existant, je ne l'ai pas écrit. A partir de quoi, il a été modifié, anglicisé à outrance, ce qui me colle des boutons au point que j'ai renoncé à en comprendre les modifications...
Je sais, ce n'est pas bien, mais on se refait pas... ^_^

@+

Wiwaxia
28-09-2020 13:07:54

Bonjour,

yoshi a écrit :

... Le crible utilisé par LEGécrit en Python sur ma machine qui n'est pas une bête de course mais 16 Go RAM :
- le millionième premier est 15 485 863
- temps de calcul 6,2 s  (un vrai TGV)
- je tape assez large avec $16 \times 10^6$
je sors à 1000000 de premiers ...

Je ne résiste pas à la tentation de tester le temps d'exécution d'un petit programme rédigé en Pascal:
6 secondes environ, pour trouver la réponse à la même question (15 485 863).
Je triche en partant du 4me nombre premier (7), et en limitant la recherche aux entiers de la forme n = 6k ± 1 .


 PROGRAM Nprem_RangN;

 USES Crt, E_Texte;

 CONST Prem4 = 7; Rang7 = 4; RangMax = 1000000;

 VAR Np, Rp: Z_32;

 PROCEDURE Aff_NpRp;
   CONST C1 = 5; L1 = 5; o = 9;
   BEGIN
     E(1015); Wt(C1, L1 - 1, 'Nombre premier:   Np = ');
     E(0012); Write(Np:o);
     E(0015); Wt(C1, L1 + 1, 'Rang:             Rp = ');
     E(0010); Write(Rp:o); A_
   END;

 FUNCTION TestPrim(VAR N_: Z_32): Bool;
   VAR DeltaQ, q, Rn: Z_32; Test: Bool;
   BEGIN
     q:= 1; DeltaQ:= 4; Rn:= Trunc(Sqrt(N_)); Test:= False;
     REPEAT
       Inc(q, DeltaQ); DeltaQ:= 6 - DeltaQ; Test:= ((N_ MOD q)=0)
     UNTIL ((q>Rn) OR Test);
     Result:= (NOT Test)
   END;

 PROCEDURE Enumeration(VAR P_, R_: Z_32);
   VAR DeltaP, k, p: Z_32;
   BEGIN
     p:= Prem4; k:= Rang7; DeltaP:= 4;
     REPEAT
       Inc(p, DeltaP); DeltaP:= 6 - DeltaP;
       IF TestPrim(p) THEN Inc(k);
     UNTIL (k=RangMax);
     P_:= p; R_:= k
   END;

 BEGIN
   Enumeration(Np, Rp);
   Aff_NpRp
 END.

LEG
28-09-2020 08:38:02

Bonjour
@48PierrelePetit
Ce que dit @Yoshi concernant mon algorithme qu'il a programmé en python , il a aussi été programmé en C++..
Et effectivement les limites et temps de calcul ne sont pas comparable, pour une limite $n = (4 222 234 441 + 29)$ ou pour $2n$ concernant le deuxième algorithme qui donne le nombre de nombres premiers entre $n\: et\: 2n$,

pour info pour $n$ la limite de ton nombre premier 4 222 234 441 + 29 , il y a 24 999 915 nombres premiers de la forme 30k + 1 en 0,4 secondes... tu vois que le programme de mon algorithme, python de Yoshi, retranscrit en C++, n'est pas comparable.

et pour cette même limite $n$ il nous indique aussi qu'il y a 23 407 452 nombres premiers de la forme 30k + 1 entre 4 222 234 460 et 8 444 468 920 en 0,4 secondes ...

Tu peux vérifier que le programme en question se trouve sur le forum programmation  à la page 15 : http://www.bibmath.net/forums/viewtopic … 10154&p=15

Mais ta réponse est intéressante, pourrais tu me retranscrire en C++ et en utilisant les slices comme ce la a été fait dans le programme en question . le programme python que @Yoshi m'a fait :

Si besoins je peux mettre les deux programmes en C++ pour les fusionner en C++ , comme il me l'a fait en Python ci dessous, ce qui ferait gagner du temps pour la fusion en C++ .


from time import time
from os import system

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):
    n1,n = int(n**0.5), int((2*n)**0.5)  #(si on fusionne les deux cribles il faudra rentrer, int((2n)**0.5) pour Goldbach.
    prime_E,prime_EG=[2,3],[]
    sieve_list = [True for _ in range(n+1)] # c'est plus propre comme ça)
    for each_number in candidate_range(n):
        if sieve_list[each_number]:
            if each_number>n1:
                prime_EG.append(each_number)
            else:
                prime_E.append(each_number)
            for multiple in range(each_number*each_number, n, each_number):
                sieve_list[multiple] = False
    #print(prime_E,prime_EG)            
    return prime_E[3:],prime_EG


def Criblage_EG(Premiers,Premiers_suite, n, fam):
    start_crible = time()
    # On génère un tableau de n//30 cases rempli de 1
    lencrible = ((n//30)+1)
    crible=[1 for _ in range(lencrible)] # c'est plus propre comme ça
    GM = [7,11,13,17,19,23,29,31]
    # On calcule les produits :
    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
    Premiers+=Premiers_suite
    del Premiers_suite # suppression du tableau devenu inutile
    nbpremiers = len(Premiers)
    n2 = 2*n
    for premier in Premiers:
        reste = n2 % premier
        if reste % 2 == 0:
            reste += premier
        pi2 = 2*premier
       # tant que reste % 30 != fam on fait reste += pi2
        while reste % 30 != fam:
            reste += pi2
        # Ensuite on divise reste par 30 pour obtenir l'index
        reste //= 30
        # On crible directement avec l'index
        for index in range(reste, lencrible, premier):
            crible[index] = 0
    total = sum(crible)
    #print(nbpremiers)
    #print("crible:", crible)
    print(f"Nombres non congru 2n[pi] {1} à {n} famille {fam} premiers de {n} à {n2}: {total} ----- {int((time()-start_crible)*100)/100}")

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

def main():
    # On demande N a l'utilisateur
    n = demander_n()
    # On récupère les premiers de 7 à √n et de √n à √2nN
    Premiers_E,Suite_E = eratostene(n)
    # On crible
    fam = 7 # ou 11, 13, 17, 19, 23, 29, 31 au choix
    Criblage_EG(Premiers_E,Suite_E, n, fam)
   
main()
system("pause")
 

yoshi
27-09-2020 09:56:15

Bonjour,

Avec la commande pfgw64 -od -qp(200000000) ( programme pfgw64 installé sur mes PC ) pfgw programme développé par primeform group.

Je ne parle pas de programme professionnel : comparons ce qui est comparable.
J'ai utilisé le langage Python ; dans ce langage, j'ai contribué à optimiser le programme utilisé par LEG.
Python est un langage interprété et haut niveau, pas compilé, donc lent.
Python est un langage libre et gratuit.
Nous ne sommes pas de programmeurs de métier.
En ce sens, le petit bout de script que j'utilise "jouait dans la même cour" que ta macro en VB : il ne peut se comparer avec ce que tu cites.

Je ne vais pas comparer les performances du SCENIC 135 ch de mon voisin avec celles d'une Ferrari !!!
Sachons raison garder ...
Si je récris le script en C et que je le compile j'irai 20 à 30 fois plus vite avec la même machine, sans pouvoir arriver à la cheville de ton pfgw64...
Le script Python en question :

from time import time

def candidate_range(n):
    cur = 5
    incr = 2
    while cur < n+1:
        yield cur
        cur += incr
        incr ^= 6  

def ERA(n):  
    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
    return [2,3,5]+prime_list[3:]

debut=time()
P=ERA(16*10**7)
print(len(P))
print(P[-1])
print(time()-debut)

Tout est possible si d'autres que vous ont travaillé pour mettre au point des outils qui n'existaient pas avant eux et que nous utilisons .

(...) nous utilisons.(...)
Nous ? Que voilà un pluriel bien... singulier (puisque le pluriel de majesté n'est plus en usage depuis longtemps.
Es-tu ici le VIP d'une S informatique ?

@+

yoshi
26-09-2020 18:46:31

Bonsoir,

Le crible utilisé par LEGécrit en Python sur ma machine qui n'est pas une bête de course mais 16 Go RAM :
- le millionième premier est 15 485 863
- temps de calcul 6,2 s  (un vrai TGV)
- je tape assez large avec $16 \times 10^6$
je sors à 1000000 de premiers

Si je ne le bride pas, avec n = 16000000
- j'obtiens 1 031 130 premiers
- le 1 031 130e est 15 999 989
- temps : 5,2 s

@+

yoshi
26-09-2020 15:11:11

Cher ami,

On te dirait fâché... ?
C'est l'expression "horizon limité" qui te chagrine ?
Alors, laisse-moi t'expliquer :
avec le langage Python, je peux manipuler des nombres entiers de 30 000 chiffres sans souci...
Est-ce que tu peux le faire, toi ?
Sans ce langage, moi, je ne peux pas...
Donc, Python me permet des calculs plus imposants qu'à la main ou qu'avec n'importe quelle calculatrice...
Mon horizon est donc limité à la main ou avec une calculatrice par rapport à l'emploi du langage Python...
C'est plus clair ?

Si tu as pris l'expression comme une insulte ou visant à te faire passer pour quelqu'un à l'intelligence limitée, tu t'es trompé complètement.

Par contre, je suis un peu déçu de ne pas avoir vu de commentaire (pas seulement le mien) à propos des réponses à ta discussion sur les sommes de carrés : là aussi quelque chose t'aurait vexé ?

Quant à ma méthode elle diffère totalement et procède avec une nouvelle logique qui n'a pas besoin de boucler et reboucler

Si tu tiens à protéger ta découverte, alors écris-la sur une feuille de papier que tu dates, signes et que tu fais authentifier par un huissier.
Tu la déposes ensuite dans un coffre  à la banque.
Enfin, cela fait, reviens s'il te plaît et explique-nous ton algorithme afin qu'on puisse voir en quoi il pose un problème pour pouvoir y remédier.

A te lire.

@+

Omhaf
26-09-2020 14:28:00

Dernière chose à mentionner avant de me taire
tout le monde sait confectionner un algorithme
Boucle allant de 1 a X
vérifier dans une autre boucle allant de  2 à racine de X
vérifier si la division donne un reste nul ou non (modulo)
afficher si reste différent de  0 (c'est un nombre premier)

Quant à ma méthode elle diffère totalement et procède avec une nouvelle logique qui n'a pas besoin de boucler et reboucler
Pas Grave

Omhaf
26-09-2020 09:14:40

Mon horizon est limité oui c'est vrai
Désolé d'avoir perturbé

LEG
26-09-2020 09:12:23

ok , il t"en rajoute 33 .

Bonjour @Yoshi, je te laisse la main ....

J'attends ton idée de reprogrammation de notre algorithme ....déjà pour Ératosthène ou Goldbach et/ou: pour la fusion des deux ... le crible_EG2_mod30 c'est celui ci qu'il faudrait optimiser, afin de vérifier assez loin le nombre de représentation R(n) de 2n en somme de deux nombres premiers p+q pour une limite n fixée.
avec n= 15k + i , soit :  2n =30k + 2i.
@+

yoshi
26-09-2020 09:03:20

Re,

@Omhaf. Et les réponses concernant ta somme de carrés ne t'intéressent plus ?
Sauf erreur, tu fais probablement des calculs via une calculatrice, pas avec un langage de programmation, donc ton horizon est vraiment trop limité... Mais montre-nous ce que tu as imaginé..
Sache cependant que personne, même parmi les plus grands mathématiciens actuels n'a été capable de construire à coup sûr un nombre premier, ni de montrer que la conjecture de Syracuse était vraie...

@LEG
Quant à toi, d'ici quelques jours, je vais reprendre ton programme et le repenser en fonction de l'extension mathématique numpy de Python.
J'avais bricolé avec , l'an dernier et il n'y avait pas de changement. Mais c'était du bricolage, je vais essayer aussi le threading : parallélisation des calculs pour utiliser plusieurs des cœurs du processeur de nos bécanes : tout ce qu'on a pu écrire n'en utilise qu'un seul sur 5, 6 et parfois 8...

@+

Omhaf
26-09-2020 08:59:45

Bonjour LEG
Je crois que tu m'as mal compris,
relis mon poste stp
en plus des 168 nombres premiers inférieurs à 1000 j'ai 33 nombres en plus et ce qui les caractérisent tous est qu'ils sont des produits de 2 nombres premiers

LEG
26-09-2020 08:31:30

Bonjour
Ben sur le forum de programmation ce n'est pas les algorithmes (cribles) générant des nombres premiers qui manquent , le crible d'Ératosthène ou une de ses variante...

Si pour une limite n =1000 , ton algorithme te donne 33 nombres premiers c'est qu'il a un sérieux problème...Et en combien de temps ?

Qu'est ce que cela donne pour n = 600 000 000 000 ? En combien de temps ?
par exemple pour le mien , il me donne 2 875 943 853 nombres premiers de la forme 30k + 7 en 59 secondes

Commence par expliquer ton algorithme ...Si tu veux une réponse §

Pied de page des forums