Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#126 19-08-2009 00:37:33
- Jolatomme
- Invité
Re : Nombres premiers
Bonjour a tous,
Je voudrais apporter une petite précision à Barbichu sur #87. Desole, ca remonte un peu loin ...
On peut changer la ligne
par
puisque les multiples avant le carre sont eliminés. On gagne un peu de temps mais ce n'est pas énorme.
Si on veut aller plus loin, il faut enlever les tests. Et c'est possible en utilisant un peu mieux le type liste de pyhton.
N, nombre = Nend, 2
liste, liste[1] = range(N+1), 0
while nombre**2 <= N:
liste[nombre**2 :: nombre] = [0]*len( liste[nombre**2 :: nombre] )
nombre += 1
return filter(None, liste)
Ce qui devrait faire gagner quelques petites secondes ... et en plus on respecte ici l'esprit du crible ...
A bientot si ce post est encore actif ...
#127 19-08-2009 15:22:18
- nerosson
- Membre actif
- Inscription : 21-03-2009
- Messages : 1 658
Re : Nombres premiers
Salut à tous,
je m'excuse de faire irruption au milieu de cette docte assemblée. Je me fais l'effet d'un clochard entré par erreur dans la salle des délibérations de l'Académie française.
J'ai tout de même cru comprendre qu'on discutait de techniques permettant de répertorier à l'infini les nombres premiers. Je hais les nombres premiers : dans ce monde d'une infinie rigueur que sont les mathématiques (j'en ai tout de même fait un peu, mais il y a longtemps), ils m'apparaissent comme une bande de voyous foutant le bordel dans le défilé du 14 juillet. Si quelqu'un pouvait les enchaîner, ça me ferait plaisir.
Alors, je voudrais juste poser à cette noble académie une question simple :
Quelqu'un peut-il me dire AVEC CERTITUDE si le nombre formé par les 1.924 premières DECIMALES du nombre "pi" est un nombre premier ?
Vous trouverez sans peine ce nombre sur le net, et, pour éviter tout malentendu je précise qu'il se termine par "0471".
Merci d'avance.
Dernière modification par nerosson (19-08-2009 15:25:11)
Hors ligne
#128 19-08-2009 15:36:59
- freddy
- Membre chevronné
- Lieu : Paris
- Inscription : 27-03-2009
- Messages : 7 457
Re : Nombres premiers
'lut,
ce dont je suis sûr avec CERTITUDE est que 1.924 ne l'est pas tout comme 471 !
Par contre je sais qu'en 1924 naquit un homme très singulier qui embêtait déjà ses petits camarades d'école avec des histoires d'aiguilles de montre superposables à certaines heures fixes de la journée ... et de la nuit !
Bb
Hors ligne
#129 19-08-2009 15:56:35
- Jolatomme
- Invité
Re : Nombres premiers
Bonjour,
false
Donc visiblement non premier. Faut-il le factoriser ou cette reponse est suffisante ?
A bientot ...
#130 19-08-2009 17:10:39
- nerosson
- Membre actif
- Inscription : 21-03-2009
- Messages : 1 658
Re : Nombres premiers
Salut, sarcastique Freddy,
Pour 1924 et 471, je savais qu'ils n'étaient pas premiers. Là, c'est encore à ma portée. Mais tu n'as pas répondu à ma question. J'ai tout de même pris soin de prendre un nombre qui ne finissait pas par 0, 2,4,5, 6 ou 8. Quant aux caractères de divisibilité par 3, 7 ou 9, ceux que je connais ne sont pas faciles à mettre en oeuvre avec un nombre de 1.924 chiffres.
Quand à mes aiguilles de montre, je n'embêtais pas mes "petits" camarades (celui là avait une tête de plus que moi), je les aidais. J'aidais même le surveillant d'étude (ça ne veut pas dire que j'étais fayot).
Salut, Jolatomme,
Si tu le dis, je te crois(j'espère que tu as fait un copier-coller pour mettre le nombre). Mais, l'explication, s'il y en a une, elle m'échappe. Je sais seulement qu'il existe une méthode qui permet d'avoir la QUASI-certitude qu'un nombre est premier. Sauf erreur, c'est à la base du système RSA. Si tu m'explique, il y a 99 chances sur cent que je n'y comprendrai rien. Essaye si tu veux, en essayant de te mettre à la portée d'un cancre qui est plus capable de repasser sa chemise que de repasser son bac. Quant à factoriser, je serai incapable de vérifier (la calculette de mon ordinateur exploserait), mais j'aimerais bien quand même, surtout pour savoir si ce sont de grands facteurs premiers ou si ce sont des petits rabougris.
Merci d'avance
P.S. Freddy va encore dire "On le changera pas : qu'est-ce qu'il est bavard !"
Hors ligne
#131 19-08-2009 21:18:46
- Jolatomme
- Invité
Re : Nombres premiers
Bonjour,
Pas de copier/coller, c'est le meilleur moyen de se tromper.
Plutôt : floor((2*arcsin(1)-3)*10^1924)
Ensuite on effectue un test de primalité.
On combine un test de pseudo primalité avec un test de Lucas.
Un petit peu de bibliographie si besoin :
Knuth ``The art of computer programming'', Vol 2, 2nd edition, Section 4.5.4, Algorithm P for a reference
H. Riesel, ``Prime numbers and computer methods for factorization''.
A ce jour pas de contre exemple connu et il a été conjecturé qu'un contre exemple pourrait exister mais devrait comporter plusieurs centaines de chiffres.
Aurait-on affaire a une exception ?? Pour le savoir, il faut trouver un facteur premier et commencer la factorisation.
Et on obtient finalement : (541)*(811)*(98384441)*reliquat ... c'est raté pour l'exception ...
Reliquat que je n'ai pas testé. Sur mon P120 et ma TI92 c'est trop long...
Sont-ce de grands ou petits facteurs, à mon avis les suivants sont grands ... même si grand ne veut rien dire ...
Mais ce qui est sûr c'est que : floor((2*arcsin(1)-3)*10^1924) n'est pas premier puisque ses plus petits
facteurs sont 541 et 811.
Inutile de préciser que 541 et 811 sont premiers.
A bientôt ...
#132 20-08-2009 07:33:00
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : Nombres premiers
Bonjour,
Tiens...
D'après ton post précédent, il me semblait que tu avais utilisé Maple : en effet, isprime() est une mnémonique de ce langage, non ?
Cela dit, tes références sont intéressantes, pour moi, parce que je doute fortement que l'ami Nerosson qui hait l'Informatique, puisse les priser...
@+
Hors ligne
#133 20-08-2009 08:46:10
- Jolatomme
- Invité
Re : Nombres premiers
Bonjour,
Effectivement isprime() est une mnémonique de maple.
Tout comme isprime() est aussi une mnémonique de :
- Matlab
http://www.mathworks.com/access/helpdes … prime.html
- Xcas
- MuPAD
- et tant d'autres ...
- mais pas encore dans sympy... enfin je crois, il faudra verifier.
Mais moi j'aime bien aussi pour les petits nombres...
'''return True if the number is prime, false otherwise'''
if aNumber < 2: return False
if aNumber == 2: return True
if (( aNumber / 2 ) * 2 == aNumber) :
return False
else:
klist = primes(int(math.sqrt(aNumber+1)))
for k in klist[1:]:
if (( aNumber / k ) * k == aNumber ): return False
return True
... encore une autre pour le sport ... Meme si on sait qu'il y a moyen de faire beaucoup mieux.
Une autre référence : Numerical Recipes in C (utile avant de commencer Knuth qui n'est pas seulement connu pour latex). http://www.nrbook.com/a/bookcpdf.php
Au fait, j'ai encore améliorer la génération du crible d'Ératosthène (CF #126) en pyhton bien sûr.
Je n'ai pas implementé celui de Lachkar mais je gagne du temps par rapport au code précédent.
Faut-il que je continue à poster ici, ou existe-t-il un topic dédié à ce crible ?
A bientôt ...
#134 20-08-2009 08:49:53
- Jolatomme
- Invité
Re : Nombres premiers
RE-Bonjour,
Désolé, Mon clavier QWERTY me joue des tours ...
Il faut lire sur le message précédent : J'ai encore amélioré ...
A bientôt ...
#135 20-08-2009 14:01:31
- nerosson
- Membre actif
- Inscription : 21-03-2009
- Messages : 1 658
Re : Nombres premiers
Salut à tous,
Qu'est-ce qu'ils sont savants, tous ce gens ! Je me sens petit, petit, petit. Que suis-je venu faire dans cette convention d'agrégés de maths. Je n'ai même pas la consolation de me dire que je me coucherai moins bête ce soir....
Une satisfaction pourtant : je suis content de savoir que le plus petit facteur premier de mon nombre est 541. Si on m'avait annoncé 13, 17, ou 19, je me serais senti mortifié, je ne sais pas pourquoi....
Mais le jour où je serai vraiment content, c'est quand on annoncera que la loi de formation des nombres premiers a été découverte et que ces cochons-là ont été enfin soumis à la rigueur mathématique. Et imaginez que cette loi-là, je la comprenne...Je rêve....
Merci, Jolatomme. Si tu trouve cette sacrée loi, tu gagneras le prix je-ne-sais-quoi, (qui remplace le Nobel) et en plus je t'offrirai une bouteille de champagne. Mais dépêche-toi....
P.S. Ami Yoshi, je ne hais pas l'informatique : on ne peut pas haïr ce qu'on ne connait pas !
Dernière modification par nerosson (20-08-2009 14:14:55)
Hors ligne
#136 07-10-2009 12:10:12
- shearer
- Invité
Re : Nombres premiers
S'il est vrai que je souffre de ce que vous dites, je préfère les mots que vous utilisez. Pour mon entourage je suis un fou, un débile.
C'est malheureux, car ceux-là, qu'ils le veulent ou non, doivent se soigner. Les seules occupations que la société peut leurs proposer sont des travaux manuels (même s'ils sont diplômés), ils n'ont (presque) pas droit au respect, ils sont les escalves modernes.
Je voudrais que vous preniez conscience de ça avec l'exemple suivant: le zéro
Le zéro existe mais il ne représente rien, alors il n'existe pas.
C'est simple comme ça, si je parle de choses qui n'existent pas, même des trouvailles, je suis mis à l'écart de la société.
C'est Docteur Machin en psychoconnerie qui va être reçu à l'académie française. Sa notion de démocratie est que si vous n'êtes pas d'accord, il faut avaler sa pilule.
Ma vision est poètique, trouver des fonds pour construire une ville sur Mars ne serviront qu'à faire l'aller-retour.
Si vous aimez les vers, voici mon blog:
blog.isuisse.com/shearer
#137 05-02-2010 12:39:30
- shearer
- Invité
Re : Nombres premiers
A partir de mon plan, je construis une grille horizontale et une autre verticale. Elles me permettent de voir en transparence les nombres affichés comme des points dans l’espace. Ensuite je vais chercher avec ces réglettes quadrillées croisées selon les axes X, Y, une valeur de mon plan. D’autres apparaissent autour. A partir de là, je peux affirmer que les nombres premiers sont cubiques à 2-3 valeurs près, qu’il y a deux règles…
#138 08-02-2010 23:50:01
- shearer
- Invité
Re : Nombres premiers
je dois avoir suffisament d'espace pour trouver quelque chose de cohérant.
#139 12-05-2010 11:18:27
- shearer
- Invité
Re : Nombres premiers
allo Houston, j'ai un problème de communication.
Si je vous ai vexé en disant FINI, je m'en excuse car c'est contraire aux définitions.
Aurai-je dû utiliser IRRATIONNEL?
Comme ça ne colle pas avec 5, cela veux vouloir dire que je dois encore mettre les pieds dans le plat.
Quel est le terme exact?
Y a-t-il encore trace de vie sur ce forum?
#140 12-05-2010 16:52:09
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : Nombres premiers
Allo la lune,
Ici Houston...
Si je vous ai vexé en disant FINI, je m'en excuse car c'est contraire aux définitions.
Aurai-je dû utiliser IRRATIONNEL?
Pourquoi serions-nous vexés par une erreur (éventuelle) d'appellation ? Curieuse idée !
Bon, où ça ?
@+
Hors ligne
#141 21-06-2010 13:21:38
- Lakar
- Invité
Re : Nombres premiers
Bonjour
Je viens vous demandez une aide, j’ai un tableau de 2 colonnes ou figure des nombres premiers et des nombres composés.
Sachant que la position des nombres composés sur le tableau est facile à déterminer,
Je voudrais savoir s’il vous plait, si l’algorithme sera-t-il facile ou difficile pour séparer les nombres premiers et les nombres composés ?
salut
#142 26-06-2010 10:44:05
- lakar
- Invité
Re : Nombres premiers
Bonjour,
pour plus d'informations sur le tableau contenant des nombres impairs ( premiers et composés)
En appliquant la formule d'EULER, je peux connaitre les nombres composés à l'avance ( ou avec plus de précision connaitre les X qui donnent les nombres composés dans la formule) sans faire aucun calcul de division.
Donc en connaissant ces X, on peut déterminer les autres X qui donnent les nombres premiers.
Est il possible de programmer cet algorithme;
exemple X= 323 donne N= 10892992571 ( 104047*104693)
X=946769 N= 896372486171 (197*4550114143)
Salut
#143 26-06-2010 11:10:27
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : Nombres premiers
Bonjour,
Peut-on voir ce fameux tableau ? Comment est-il construit ?
@+
Hors ligne
#144 26-06-2010 14:49:21
- lakar
- Invité
Re : Nombres premiers
bonjour,
le tableau est constitué à partir de la formule dEuler N = x2 + x + 41
x N
0 41
1 43
2 47
3 53
4 61
5 71
6 83
7 97
8 113
9 131
10 151
11 173
12 197
13 223
14 251
15 281
16 313
17 347
18 383
19 421
20 461
21 503
22 547
23 593
24 641
25 691
26 743
27 797
28 853
29 911
30 971
31 1033
32 1097
33 1163
34 1231
35 1301
36 1373
37 1447
38 1523
39 1601
40 1681 41/41
41 1763 41/43
Ainsi de suite.
A partir de ce tableau on déterminera tous les X donnant les nombres impairs composés , sans faire appel à des calculs trop pénibles et trop long.
Salut
#145 26-06-2010 15:55:36
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : Nombres premiers
RE,
ok...
Sachant que la position des nombres composés sur le tableau est facile à déterminer...
Après la réponse, je te dirai, si je peux programmer ça en Python : si ta méthode de détermination de la position des nombres composés est aussi simple que tu le dis, alors, sa programmation ne devrait pas être trop compliquée.
Avec Python, je peux travailler avec des nombres de très grande longueur : je ne suis pas limité à 17 ou 18 chiffres, 100 chiffres ne seraient pas un problème...
Reste à savoir si la méthode que tu évoques est infaillible...
@+
Hors ligne
#146 26-06-2010 17:22:10
- lakar
- Invité
Re : Nombres premiers
bonjour,
Pour l'instant, je continue à vérifier quelques points et le plus important, je continue ma recherche sur le côté positions des X donnant les nombres premiers, j'ai encore quelques trous.
Salut
#147 29-06-2010 19:21:51
- lakar
- Invité
Re : Nombres premiers
bonjour,
Pour l'instant, je continue à vérifier quelques points et le plus important, je continue ma recherche sur le côté positions des X donnant les nombres premiers, j'ai encore quelques trous.
Salut
Bonjour
pour information, ci-dessous un exemple d'une liste des x donnant les nombres premiers qui ne se trouvent pas dans le tableau qui donne les nombres composés.
42 83 124 165
43 125 166
85 167
45 86 168
46 128 169
47 129
48 88 171
50 90 131 174
51 132 175
52 92 133 176
53 93 134 177
54 94 135
55 95 179
137 180
57 97 181
58 98 139 182
59 99 183
60 100 141
61 101 142 206
62
63 103 144 247
64 145
105 146 288
66 106
67 107 148
68 108 149
69 150
70 110 151
71 111 152
72 112 153
73 113 154
74 114
75 115 156
116 157
77 158
78 118
79 119 160
80 120
90
92
93
94
95
97
98
99
100
101
103
105
106
107
108
110
111
112
113
114
115
116
117
118
119
120
Salut
#148 07-07-2010 14:26:37
- lakar
- Invité
Re : Nombres premiers
Bonjour,
je m'adresse à vous, pour vous demander : y a-t-il une limite pour faire l'extraction d'une racine carrée d'un nombre .
y a-t-il une limite dans le nombre de chiffre d'un nombre.
Merci
Lakar
#149 07-07-2010 14:49:08
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : Nombres premiers
Salut,
Une limite en programmation, oui : la RAM de la machine et le temps qu'on est disposé à attendre. Sinon, mathématiquement, non !
Il y a 20 ans, j'ai écrit un programme de calcul de la racine carrée de 5 avec 120 chiffres après la virgule : il fallait deux heures avec une machine cadencée à 4,7 Hz et dont je ne savais exploiter que 64 Ko de RAM (sur 128 ko) : ma machine actuelle est plusieurs millions de fois plus rapide et plus de 200 millions de fois plus de RAM.
Quelle racine carrée veux-tu calculer et avec combien de chiffres après la virgule ?
@+
Hors ligne
#150 07-07-2010 15:33:15
- lakar
- Invité
Re : Nombres premiers
RE,
ok...
Sachant que la position des nombres composés sur le tableau est facile à déterminer...
Après la réponse, je te dirai, si je peux programmer ça en Python : si ta méthode de détermination de la position des nombres composés est aussi simple que tu le dis, alors, sa programmation ne devrait pas être trop compliquée.
Avec Python, je peux travailler avec des nombres de très grande longueur : je ne suis pas limité à 17 ou 18 chiffres, 100 chiffres ne seraient pas un problème...
Reste à savoir si la méthode que tu évoques est infaillible...@+
Bonjour,
Je vous donne un aperçu sur la méthode qui me permet de déterminer tous les X donnant les nombres composés quand on applique la Formule d'Euler.
Une fois ces x sont trouvés , il suffit de chercher les X qui ne figurent pas dans les tableaux, Ces X donneront les nombres premiers en appliquant toujours la formule d?Euler
Liste des x donnant les nombres composés selon la formule d’Euler N = x2 + x +41.
1ER tableau de 40 et les carrés de i
A i X=A+i 40+i2 2*x - i 3* 4* 5*
41 -1 40 40+0 81 122 163 204
41 +0 41 40+1 82 123 164 205
43 +1 44 40+4 87 130 173 216
47 +2 49 40+9 96 143 190 237
53 +3 56 40+16 109 162 215 268
61 +4 65 40+25 126 187 248 309
Exemple X=237
2372 + 237 + 41 = 56447 = 47 * 1201
2eme cas de 41 et les i
*1 *2 *3 *4 *5 *6
41 -1 40 81 122 163 204 245
43 -2 41 84 127 170 213 256
47 -3 44 91 138 185 232 279
53 -4 49 102 155 208 261 314
61 -5 56 117 178 239 300 361
71 -6 65 136 207 278 349 420
83 -7 76 159 242 325 408 491
97 -8 89 186 283 380 477 574
Exemple X=477
4772 + 477 + 41 = 228047 = 97 * 2351
Salut