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

#51 21-03-2019 10:24:45

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

Re : Nombres premiers nouvelles approches : formule probabiliste

Et dans R, avec P, du polynôme d'Euler par exemple , ça marche...? car cela va assez vite pour les construire, et les tester.

3010811
3353351
3714341
4093781
4491671
4908011
5342801
6267731
7266461
7793501
8338991
9485321
------------------
3033073
3376843
3739063
4936423
5372443
5826913
7829293

Dernière modification par LEG (21-03-2019 10:26:36)

Hors ligne

#52 21-03-2019 10:34:09

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

Re : Nombres premiers nouvelles approches : formule probabiliste

Re,

@LEG
Oui, j'ai un zéro de trop...

if p%premiers == 0 : c'est pas plus rapide ...?

premiers est la liste issue d'Eratosthène...
Comment veux-tu diviser un nombre par une liste ?

Maintenant je vais me pencher sur l'optimisation...

@+


Arx Tarpeia Capitoli proxima...

En ligne

#53 21-03-2019 12:02:21

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

Re : Nombres premiers nouvelles approches : formule probabiliste

De la même façon que tu as appelé les premiers d'É dans notre crible pour calculer les restes:  j=2n%pi ; où  là ce serra:  [premiers %p==0]


for i,pi in enumerate(Primes_init):      
       j = nn%pi

qui devient...................

p= nombres    ("que tu dois tester:  par ex:  20979421, 20979461, 20979587 que tu mets ensuite dans R..") les pi sont tes premiers d'Ératosthène < racine de p

for i,pi in enumerate(premiers):      
       if p%pi == 0   #etc ...la suite de ton programme

concernant la 2ème question avec la liste des nombres premiers que j'ai mis ,(" puisque  au départ il était parti sur le polynôme d'Euler") est ce que tu as autant de résultat ?
ce serait facile d'en mettre une centaine , et de tester  avec p > 30 000 000 dans un premier temps . On peut lister une famille afin de voir le résultat.

si tu veux essayer ou BAKKAOUI HASSANE:

cela va éviter pas mal d'opération de plus ils corresponde au critère du polynôme d'Euler si oui :
je te les met sur le forum
@+ bon courage

Dernière modification par LEG (21-03-2019 12:06:45)

Hors ligne

#54 21-03-2019 12:15:07

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

Re : Nombres premiers nouvelles approches : formule probabiliste

Re,


Optimisation peu concluante sur la poignée de s de fonctionnement, mais j'ai écrit qq ch de plus propre...
J'ai changé le test de primalité à base de divisions : avec la nouvelle mouture, les résultats étaient incohérents.

Donc les tests, qu'ils soient probabilistes via Miller-Rabin ou avec des divisions me sonnent les mêmes quantités qu'hier...
Et il n'y a pas de doublons.
Hier, j'ai posté les 20 derniers...

Voilà les 20 précédents :
20895671, 20895757, 20936453, 20936497, 20936581, 20936789, 20936791, 20937041, 20937083, 20937127,
20937253, 20937463, 20937503, 20937589, 20978411, 20978623, 20978791, 20978917, 20978999, 20979001

et les 40 premiers :
41, 43, 83, 127, 167, 211, 251, 293, 337, 379, 419, 421, 461, 463, 503, 547, 587, 631, 673, 757, 797, 839,
881, 883, 967, 1009, 1049, 1051, 1091, 1093, 1217, 1259, 1301, 1303, 1427, 1429, 1471, 1511, 1553, 1597

Nouveaux tests :
p=2n+1+2*q : 307
p=2n -1+2*q :   0
p=2n+1-2*q  :   0
p=2n- 1-2*q  :   0

p=2n+1+2*k*q : 376
p=2n -1+2*k*q :  10
p=2n+1-2*k*q  :   0
p=2n- 1-2*k*q  :   0

@+


Arx Tarpeia Capitoli proxima...

En ligne

#55 21-03-2019 14:52:37

BAKKAOUI HASSANE
Membre
Inscription : 21-02-2019
Messages : 62

Re : Nombres premiers nouvelles approches : formule probabiliste

Bonjour
Salut Yoshi

Quel soulagement ! Enfin une petite réussite.
Ces résultats vont nous servir dans l’étude de q.
Il faut quand sache le pourcentage de q=0 % autres q.
Et comment évolue q=0 % n.
Vérifier dans ce test que tout les n ont au moins un nombre premier (ça doit être le cas)
Faire le même test avec k=91 et k=171, prendre des k arbitrairement différents de  m(m+1)/2 et vérifier s’ils donneront les mêmes résultats, notre objectif est quand on veut chercher un nombre honorablement grand on choisira la meilleure forme de k qui donnerait un « q » petit.

Cas particuliers
[tex]p=\frac{m(m+1)}{2}\times n(n+1) \pm1 \pm m(m+1)\times q[/tex]

Travailler avec cette formule et prendre le cas suivant m=n/2
Produit-elle plus de nombres premiers
Ma liste est long c’est pourquoi on a besoin des contributeurs à ce projet qui est trouver le nombre premier record.

Dernière modification par BAKKAOUI HASSANE (21-03-2019 15:48:04)

Hors ligne

#56 21-03-2019 15:25:34

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

Re : Nombres premiers nouvelles approches : formule probabiliste

Salut B.H
1) pour qu'elle raison tu choisis des K qui sont des multiples 91=7*13, 171 multiple de 3..tu as l'air de vouloir faire des tests à l'arrache...! test s que tu te garde bien de faire...Alors explique cette raison de A à Z...!point par point détail par détail ...

2) @ Yoshi a mis la liste des 40 premiers et tu ne dit rien.
or on voit nettement que c'est nombres premiers sorte d'un polynôme , par exemple:2*41+1 = 83; 2*83 +1 =167 ; 2*127-3 =251; 2*167 +3= 337....
................................................................
et les 40 premiers :
41, 43, 83, 127, 167, 211, 251, 293, 337, 379, 419, 421, 461, 463, 503, 547, 587, 631, 673, 757, 797, 839,
.....................................................................

il n'y a qu'a séparer les polynôme et travailler sur un seul..., puis sur un autre ; afin d'étudier le comportement dans l'ordre des choses et pas n'importe comment...

j'ai indiqué une liste de nombres premiers issue du polynôme d'Euler ...Marche t'il, ...?
comment tu les mets dans ta  formule avec les trois premiers de chaque liste que j'ai mise , en détaillant les différentes valeurs que tu vas utiliser...c'est un minimum que tu dois faire ...par politesse...! si tu ne veux pas dit le carrément ..!

Car si je comprend bien , tu ne t'emmerde pas : travailler avec x, si ça ne marche pas essayer ma formule, avec y;  qui est longue ....patin couffi patin couffa

imprime donc les tests que tu as fait, comme vient de le faire @Yoshi...! et les valeurs que tu as utilisé dans l'ordre de la logique...

à+

Hors ligne

#57 21-03-2019 18:19:30

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

Re : Nombres premiers nouvelles approches : formule probabiliste

Salut,

@LEG

j'ai indiqué une liste de nombres premiers issue du polynôme d'Euler ...Marche t'il, ...?

Qu'est-ce que ru entends par  : Marche-t-il ?

@Bakkoui Hassane
[tex]q=0 % n[/tex].
??? Quelle évolution ? si je cherche le reste de la division de 0 par n'importe quel nombre n >0 le reste sera toujours 0...
Nan ? C'est pas ce que tu veux ? Bon alors, explique-toi...

Il y a déjà quelques posts tu disais que mon niveau de compréhension de la langue laissait à désirer...
Pourtant, je te signale que là non plus tu n'es pas clair :

Vérifier dans ce test que tout les n ont au moins un nombre premier (ça doit être le cas)

Su tu écris : ce test, le "ce" signifie : celui dont on parlé, qui est connu...
Donc, le test précédent ?
Celui à venir ? Et dans ce cas, il faut le préciser...

Veux-tu bien présenter cela de façon rigoureuse avec une hiérarchisation des tâches, s'il te plaît ?
Comme cela par exemple :
1.  a)
     b)
    ...
2. a)
    b)
   ...

tous les n ont au moins un nombre premier

n c'est n, rien d'autre, il ne possède rien : pourquoi ce verbe avoir ?
Ça veut dire quoi ?

Je veux bien t'aider, mais je t'ai déjà demandé d'être précis dans ce que tu veux : je n'ai pas l'envie de chercher 10 min, pour savoir ce que tu as voulu dire...
A prendre ou à laisser !

Si tu soumettais ton travail, tel quel, à l'examen de la communauté mathématique mondiale, je vais te dire ce qu'il se passerait : il partirait dans la minute à la poubelle, tellement c'est formulé "à la va comme je te pousse"...
Et ne pas me dire que tu n'as pas fini, que tu en es à la phase de mise au point : ce n'est pas de cela que je parle...

Tiens, à méditer :
Ce qui se conçoit bien s'énonce clairement
Et les mots pour le dire arrivent aisément.

Et cette abréviation, ctd, que tu emploies régulièrement,  elle remplace quoi ?
@+


Arx Tarpeia Capitoli proxima...

En ligne

#58 21-03-2019 21:07:23

BAKKAOUI HASSANE
Membre
Inscription : 21-02-2019
Messages : 62

Re : Nombres premiers nouvelles approches : formule probabiliste

Bonjour
LEG
- pourquoi je choisi k =91, 171, ..j’ai dit au début que mes travaux repose exclusivement sur des observations numériques.
Parce que j’ai remarqué qu’elle marche mieux. Les k de la forme m(m+1)/2 et qui sont divisibles par 3 , vous avez vu juste les multiples par 3.
Exemple si k=(10*11)/2=55
55 ne marche pas bien
L’idée viens de ça :
Les nombres premiers s’écrivent tous sous la forme :
p= m(m+1).p1.p2...pi +/-1
p=[m(m+1)/2] *   2•p1.p2...pi +/-1
p=k.                  *.   (n+1)+/-1-2kq.
Si k=m.(m+1)/2
- Pourquoi les tests : c’est pour faire des listes qui serviront à l’étude du comportement de q, et essayer de comprendre pourquoi la formule marche avec certains k et pas d’autres .
- je garde bien de les faire : croyez moi pas pour feignantise , la seule et unique raison c’est que je ne suis pas programmeur, alors que ce travail repose exclusivement sur la programmation. Donc soit je laisse mes travaux au fin fond de mes tiroirs, là où il était pendant 3 ans, où je travail en collaboration avec quelqu’un comme Yoshy
- C’est nombre sort d’un polynôme : c’est l’idée maîtresse de mon travail
- Concernant vos listes c’est vrai ça devrait être intéressant de les tester j’en ai fait quelques une avec différentes n pris au hasard, on ne peut pas conclure sur une dizaine de test, polynôme d’Euler ça peut être une piste de la démonstration, mais ce n’est pas ma procuration pour le moment,sujet à suivre ...


Bonjour
Yoshy
Désolé si je ne suis pas très souvent clair
q=0
21*6*7-1=881
21*6*7+1=883
Dans les deux cas on q=0
On a besoin de savoir combien de nombres premiers produit par la formule ont q=0
Et mesurer leur évolution quand n augmente
n de 0 à 100 combien de nombres premiers produits par la formule ont un q=0
Le test que vous avez fait avant hier avec k=21
C’était surtout pour vous convaincre pour () de la validité mes propos.
Maintenant si on veut rentrer dans le vif du sujet ma demande sera légèrement différente on a besoin dans votre liste R que vous avez créé les coordonnées de chaque nombre premier produit par la formule ctd:
Son k on le connaît =21
Son -n- correspondant
Et q avec le signe + ou -
Et le + ou - de 1
Exemple 881=[6,21,0,-1]
Car on faire des tracés pour chaque k lui correspond une fonction polynomiale pour voir visiblement comment évolue q % à n
On s’explique davantage dans autres postes

Dernière modification par BAKKAOUI HASSANE (03-03-2020 16:54:01)

Hors ligne

#59 21-03-2019 22:20:23

BAKKAOUI HASSANE
Membre
Inscription : 21-02-2019
Messages : 62

Re : Nombres premiers nouvelles approches : formule probabiliste

Re,
Une simple vérification quand vous aurez le temps
k = 3010811
n varie de 180300 à 181300
q de 0 à 3
D’où la formule
p=3010811*n(n+1)+/-1 +/-2*3010811*q
peut être on aura ici la surprise du siècle !!
Salut Yoshy c’est urgent de faire ça

Dernière modification par BAKKAOUI HASSANE (22-03-2019 09:11:21)

Hors ligne

#60 22-03-2019 09:48:43

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

Re : Nombres premiers nouvelles approches : formule probabiliste

RE,

from random import randint
from time import time

def Affiche_temps(tps):
    mn,sec=divmod(tps,60)
    h,mn=divmod(mn, 60)
    print ("Durée :", h,"h",mn,"min",sec,"s")

def _millerRabin(a, n):
    """Ne pas appeler directement (fonction utilitaire). Appeler millerRabin(n, k)"""
    # trouver s et d pour transformer n-1 en (2**s)*d
    d = n - 1
    s = 0
    while d % 2 == 0:
        d >>= 1
        s += 1
 
    # calculer l'exponentiation modulaire (a**d)%n
    apow = pow(a,d,n) # =(a**d)%n
 
    # si (a**d) % n ==1 => n est probablement 1er
    if apow == 1:
        return True
 
    for r in range(s):
        # si a**(d*(2**r)) % n == (n-1) => n est probablement 1er
        if pow(a,d,n) == n-1:
            return True
        d *= 2
 
    return False
 
# ========================
def millerRabin(n, k):
    """Test de primalité probabiliste de Miller-Rabin"""
      # éliminer le cas des multiples de 30 qui ne peuvent pas être 1ers!  
    if  n%30  not in [1,7,11,13,17,19,23,29]:
        return False
 
    # recommencer le test k fois: seul les nb ayant réussi k fois seront True
    for repete in range(k):
        # trouver un nombre au hasard entre 1 et n-1 (bornes inclues)
        a = randint(1, n-1)
        # si le test echoue une seule fois => n est composé
        if not _millerRabin(a, n):
            return False
    # n a réussi les k tests => il est probablement 1er
    return True

debut=time()    
k=30110811
P1234=[0,0,0,0]
R,S=[],[(1,2),(-1,2),(1,-2),(-1,-2)]

for n in range(180300, 181301):
    for q in range(4):
        for i in range(4):
            s1,s2=S[i]
            p=k*n*(n+1)+s1+s2*k*q
            if p>1 and not (p in R):
                if millerRabin(p,50):
                    P1234[i]+=1
                    R.append(p)
                   
for i in range(4):
    s1,s2=S[i]
    print("p=kn(n+1)"+"+"*(s1>0)+str(s1)+"+"*(s2>0)+str(s2)+"kq --->",P1234[i])
print()
Affiche_temps(int(time()-debut))

Résultats :

p=kn(n+1)+1+2kq ---> 263
p=kn(n+1)-1+2kq ---> 279
p=kn(n+1)+1-2kq ---> 240
p=kn(n+1)-1-2kq ---> 184

Durée : 0 h 0 min 2 s

@+


Arx Tarpeia Capitoli proxima...

En ligne

#61 22-03-2019 09:57:59

BAKKAOUI HASSANE
Membre
Inscription : 21-02-2019
Messages : 62

Re : Nombres premiers nouvelles approches : formule probabiliste

Bonjour
Ce qu’on a ic c’est extraordinaire

Hors ligne

#62 22-03-2019 10:07:01

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

Re : Nombres premiers nouvelles approches : formule probabiliste

Re,

Tant mieux pour toi...
Mais n'espère pas arriver un jour à 30000 chiffres, tu serais déçu...
Pour réaliser des tests probabilistes sûrs à 99,99 % il faudrait passer des mois avec nos machines....

@+


Arx Tarpeia Capitoli proxima...

En ligne

#63 22-03-2019 10:57:13

BAKKAOUI HASSANE
Membre
Inscription : 21-02-2019
Messages : 62

Re : Nombres premiers nouvelles approches : formule probabiliste

Bonjour
Vous vous êtes trompé sur la valeur de k
k=3010811
C’est bizarre votre numéro à quand même donner de bonne résultats !!
Vous avez mis 30110811

Hors ligne

#64 22-03-2019 11:12:59

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

Re : Nombres premiers nouvelles approches : formule probabiliste

RE,

Avec k =3010811 :

p=kn(n+1)+1+2kq ---> 271
p=kn(n+1)-1+2kq ---> 151
p=kn(n+1)+1-2kq ---> 164
p=kn(n+1)-1-2kq ---> 214

Durée : 0 h 0 min 2 s

@+


Arx Tarpeia Capitoli proxima...

En ligne

#65 22-03-2019 11:40:23

BAKKAOUI HASSANE
Membre
Inscription : 21-02-2019
Messages : 62

Re : Nombres premiers nouvelles approches : formule probabiliste

Bonjour
Fausse alerte, les résultats sont presque pareils sinon moins, désolé ce n’est pas là surprise du siècle le numéro que je vous ai proposé est celui de la liste de LEG les nombres premiers d’Euler

Hors ligne

#66 22-03-2019 13:36:07

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

Re : Nombres premiers nouvelles approches : formule probabiliste

Salut ok B.H

Au moins tu as une réponse avec k = 3010811 , du polynôme d'euler qui ne donne pas plus de résultat.... pour un K..
si les autres ne donne pas mieux alors que ceux calculer par le programme de Yoshi , donnent plus de résultats, on saura que le polynôme Euler n'apporte rien de plus...
@+

Hors ligne

#67 22-03-2019 14:16:13

BAKKAOUI HASSANE
Membre
Inscription : 21-02-2019
Messages : 62

Re : Nombres premiers nouvelles approches : formule probabiliste

Bonjour LEG
bien sûr ce que je me suis dit, mais ce n’est pas encore fini avec les nombres premiers issus des polynômes d’Euler.

Question techniques quel est le nombre de chiffres maximale quand peut manipulés aisément avec nos machines ?
Voilà ma stratégie on produit des nombres premiers avec le maximum de chiffres que nos ordinateurs nous permet et pourquoi pas aller ensuite dans un labo . l’université de saclay par exemple leur demandant si on puisse faire une expérience avec notre formule
Est-ce possible ?
Nb ctd==c’est à dire

Dernière modification par BAKKAOUI HASSANE (22-03-2019 14:19:22)

Hors ligne

#68 22-03-2019 15:48:02

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

Re : Nombres premiers nouvelles approches : formule probabiliste

tout dépend de ta mémoire Ram, mais surtout du logiciel qui va manipuler tes grands nombres par ce qu'une calculatrice ne va pas loin..donc supposons que tu veuilles établir le Produit de tous les facteur p [7 ; Pn] avec Pn de l'ordre de 1000 000 ton dernier facteur p . Ce produit X est forcément congrus à 1 ou P [30] , avec P premier appartenant [7;29] il te suffit d'ajouter 30, ou de retirer 30. 6 fois de suite que tu testes à chaque fois .
cela va te donner 12 entiers PSP = possible premier .
c'est le principe de la croix d'Ératosthène , si le produit n'est pas égal à 7 modulo 30, il suffit de le multiplier par un des 7 facteurs P[7;29] . Pour qu'il le devienne
ex: si X se termine par 3 , il faut multiplier X par 19 ou 29 , pour qu'il devienne congru à 7 ou à 17[30].

donc tu as :$X\equiv{7}[30]$tu fais tes 6 + 6 tests et en plus tu peux trouver deux couples de premiers jumeaux possible en faisant :
X + 4  test; +2 test; +4 test; +2 test ; + 4 test et + 6 test. ce qui te fais 6 nouveaux tests , au total 18 tests .

X ne peut être divisé que par un facteur P > Pn.

Ensuite tu peux réitérer avec le facteur P > Pn et consécutif ,

rebelotte il faut qu'il soit congrus à 7[30] si ce nouveau X , se term1ne par 9 , et bien X*13; ou X*23 = 7[30] , si il se termine par 7 et bien modulo 30 = 7 ok sinon c'est qu'il est = à17[30] et dans ce cas tu multiplies  par 11...

moi j'allais sur sur le site:  https://www.alpertron.com.ar/ECM.HTM avec des nombres de 200 chiffres:c X  = produit de 7 jusqu'à  Pn = 459  ou Pn < 1000. mais c'est trop petit .
Bon courage.

Dernière modification par LEG (22-03-2019 15:51:33)

Hors ligne

#69 22-03-2019 16:06:55

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

Re : Nombres premiers nouvelles approches : formule probabiliste

Re,

Alors l'abréviation standard cher ami, est c a d ou mieux i.e du latin id est...

Bon, rectification 30000 c'est peu et là tu vas être déçu :
le plus grand nombre premier (découvert le 7 décembre 2018) est un  nombre de Mersenne qui comporte 24 862 048 chiffres lorsqu'il est écrit en base 10. 
Je peux manipuler des nombres de 50000 chiffres (j'ai fait l'essai avec un de mes programmes qui calcule le nombre d'or)...

Par contre, je ne sais pas combien de passages, je devrais faire avec le test de Miller-Rabin pour avoir une bonne probabilité, voire une certitude qu'un nombre est premier...
Et si je dois tester des centaines de nombres, cela risque d'être très très très long...

Es-tu capable de générer un nombre de 50000 chiffres ?

Le logiciel libre PARI gp a l'air intéressant, 100 fois plus rapide (écrit en C ou C++ et compilé) que Python (langage interprété)...

@+


Arx Tarpeia Capitoli proxima...

En ligne

#70 22-03-2019 20:33:11

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

Re : Nombres premiers nouvelles approches : formule probabiliste

yoshi a écrit :

Re,

Alors l'abréviation standard cher ami, est c a d ou mieux i.e du latin id est...

@+

té pou qui sa , té pou moi....? je rigole .

Bon bref : où est ce que je peux t'envoyer un message privé....? c'est important , c'est au sujet de notre travail en commun , sur le renseignement qu je t'ai indiqué dans la rubrique programmation. tu ne le regretteras pas ...au plus tu laisse courir...Mais il faut que tu vois ça....suite aux deux cribles.

Bonne soirée
@+

Hors ligne

#71 22-03-2019 21:06:55

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

Re : Nombres premiers nouvelles approches : formule probabiliste

RE,

le MP n'existe pas avec Flushbb, moteur de ce forumi.
Ecris à yoshik _at_ no-log.org
(Remplacer _at_ par @)

@+


Arx Tarpeia Capitoli proxima...

En ligne

#72 23-03-2019 00:19:05

BAKKAOUI HASSANE
Membre
Inscription : 21-02-2019
Messages : 62

Re : Nombres premiers nouvelles approches : formule probabiliste

Bonjour Yoshi

J’ai booster mon ordi avec  un disque dure ssd, j’ai ajouté de la ram, j’ai réinstaller python, j’ai refait le test k=21 avec votre script, j’ai vue les 15578 nombre premier créé par la formule, c’est fabuleux.
Comme je vous ai expliqué on a besoin des 4 variables [tex]n,k,\pm q, \pm1[/tex]pour chaque nombre premier produit, inscrit à côté.
Quand vous aurez le temps, vous avez votre travail aussi, il ne faut pas que j’abuse.
J’aimerais  que vous fassiez les changements sur votre script en figurant dans votre liste R, les 3 variables plus k..
C’est à moi maintenant de faire les autres tests avec des différents k.
Par contre j’aurais besoin aussi d’un script pour chercher un seul nombre premier et le programme s’arrête
On prenant exemple
n =2^3999
k =180300
q est la seule variable elle varie de 0 jusqu’à qu’ont trouve un nombre premier
En tenant compte des +/- de 1 et des +/- 2*kq
Un nombre de N=10000 chiffres si on de la chance on peut tomber sur un nombre premier à q=N/10 ce qui veut dire qu’on aura à faire 1000*4 de tests de primalité dont 80%  seront facilement à vérifier les nombres qui prendront du temps ceux qui sont multiples de deux ou trois grand nombre premier.
Très probable suffirait pour un début

Dernière modification par BAKKAOUI HASSANE (23-03-2019 06:11:35)

Hors ligne

#73 23-03-2019 16:54:52

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

Re : Nombres premiers nouvelles approches : formule probabiliste

Re,

Il y a de fortes chances que celui-là (2413 chiffres) soit premier  :
7832511608960961256244208751170810889816935858462785068413835889134551599212294731564127088377697509285493985874497567479274188172198208736013356021285086993029806470085465455831935231027369108556145071280435468004205565264395509755488620595552302084934749936533040070892006349285982900671373536550860142549788878603254253918665102372955759539525198125960648149058279128634087028053368419684046589421265647821936563453372756157108056622776693182334026979021626091358897490650669698164977753180470167447975865556884113712931565002283036562388943579481808877356617489568691431806732532276148249963548171465499759077240637902727945009422807277029668025772431981484963361641111825784695050539176832589739704902937298518874540662677282944572928944588368014559778576610204872159898980285071771945321239812712511254768792379878195982227062274114285922332155364385725082149541451826422088502859283055434472589798486954694512877575186722779245373263176474694412248134682060574035507788146358181738064807743897398711321433905764274280507284377898743279663675552381873414015354314283024172228749460054098093465151991673847263488927138701078956937111283083402897241865752487830827363883317524165911505624919999411092917792452290608266778912146783707233551241566694764135753135581576893755024723060428579830641640379406614209690334316653561449523819485463201802940871810599863948222806752625873178554767159977865156200948382208671164036767296454573784571778856706362898320480509433750398236696640576134555813956887063779141689969036545347370658531573600511174173617466982649035595219733190165983360782518074931801654702115813909246892130269090385098854462036252370832978651454996399687234509610447454856549149398616522763752752167196980422082077387116638933907154571949512548097177243894779869902262506215193948046543856048041346831728052009392775945072627856614783464436565725623003975099831023492178910858046444339126354034697947337941190661685266837625260811312663052513877272685032378600344294655631939890730536358646870903644097246989878320271963773767008847712262972058752136111700497086842946040975673479175823962248786171537830396101397025743336052891219055654746605415215328825551737728040640741870600964864442643941405080644562608079630560426485574242209070232324768834862896394084537550024271890287533661396670251384711482249018181297354426563241274689249860785434331191272006269147238648860320662201547410168327999

Avec
n =2^3999
k =180300
q=136 (je suis parti de q=0)
p=kn(n+1)-1-2kq

@+


Arx Tarpeia Capitoli proxima...

En ligne

#74 23-03-2019 20:26:07

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

Re : Nombres premiers nouvelles approches : formule probabiliste

Re,

Voilà ce que tu demandes : testé et retesté...

from random import randint
from time import time
from math import sqrt

def Affiche_temps(tps):
    mn,sec=divmod(tps,60)
    h,mn=divmod(mn, 60)
    print ("Durée :", h,"h",mn,"min",sec,"s")

def _millerRabin(a, n):
    """Ne pas appeler directement (fonction utilitaire). Appeler millerRabin(n, k)"""
    # trouver s et d pour transformer n-1 en (2**s)*d
    d = n - 1
    s = 0
    while d % 2 == 0:
        d >>= 1
        s += 1
 
    # calculer l'exponentiation modulaire (a**d)%n
    apow = pow(a,d,n) # =(a**d)%n
 
    # si (a**d) % n ==1 => n est probablement 1er
    if apow == 1:
        return True
 
    for r in range(s):
        # si a**(d*(2**r)) % n == (n-1) => n est probablement 1er
        if pow(a,d,n) == n-1:
            return True
        d *= 2
 
    return False
 
# ========================
def millerRabin(n, k):
    """Test de primalité probabiliste de Miller-Rabin"""

    # éliminer le cas des restes %30 improductifs
    if  n%30  not in [1,7,11,13,17,19,23,29]:
        return False
 
    # recommencer le test k fois: seul les nb ayant réussi k fois seront True
    for repete in range(k):
        # trouver un nombre au hasard entre 1 et n-1 (bornes inclues)
        a = randint(1, n-1)
        # si le test echoue une seule fois => n est composé
        if not _millerRabin(a, n):
            return False
    # n a réussi les k tests => il est probablement 1er
    return True

       
debut=time()    
P1234=[0,0,0,0]
R=[]
S=[(1,2),(-1,2),(1,-2),(-1,-2)]
ok=0

##################
n = 2**3999                   #  (1)                          
k = 180300                     #  (2)
#################

commun = k*n*(n+1)
for q in range(451,501): # (3)
    if ok:
        break
    kq=k*q
    for i in range(4):
        if ok:
            break
        s1,s2=S[i]
        p=commun+s1+s2*kq
        if p>1 and not (p in R):
            if millerRabin(p,200):   #4
                print ("p = kn(n+1)"+"+"*(s1>0)+str(s1)+"+"*(s2>0)+str(s2)+"kq =")
                print(p)              
                print ("q = ",q)
                ok=1
                break
if not ok:
    print("Limite maxi de q atteinte : pas de résultat. Remplacer les limites mini et maxi")

Affiche_temps(int(time()-debut))

Où tu peux modifier :
(1)  La valeur de n... Attention la puissance en Python c'est **
(2)  La valeur de k
(3)  Les limites inférieure et supérieure. Ton disque SSD ne t'avancera à rien. Tour se passe en mémoire vive (RAM)...
      Selon la vitesse du processeur et la quantité de RAM (et sa vitesse) il est préférable d'avoir un écart pas trop grand...
      Les tests avec 50 d'écart me prennent 17 min lorsqu'ils sont négatifs... et j'ai 16 Go de RAM et un windows 64 bits.
      Si ta machine est vieille, elle est probablement en 32 bits : la mémoire max est alors de 4Go, dont seulement 3,2 Go sont utilisables
(4)  Plus le nombre qui suit p est élevé, plus le test va prendre du temps mais plus il sera fiable...

Pour qu'une boucle fonctionne, il faut un écart minimum de 1 entre les 2 bornes.
for i in range(3,5):
    print (i)
va afficher :
3
4
Le test d'arrêt est 5 : lorsque i prend la valeur 5 le script sort de la boucle...
q=136 est la seule valeur qui a généré un premier entre 0 et 560 inclus...
Sa "certification" a pris 8 min 11s.

@+


Arx Tarpeia Capitoli proxima...

En ligne

#75 23-03-2019 22:32:06

BAKKAOUI HASSANE
Membre
Inscription : 21-02-2019
Messages : 62

Re : Nombres premiers nouvelles approches : formule probabiliste

Bonsoir
Salut Yoshy
Vous êtes géniale mec, merci infiniment de tous ce vous avez fait pour moi

Hors ligne

Pied de page des forums