Nombres premiers

Lachkar M · 07-10-2008 15:01:16

Salut

comme je l'ai signalé en haut pour trouver les multiples des nombres impairs on procede :

colonne 1

multiple de 11 (M11)

position de 11 est P= 2
le suivant sur la même colonne sera à P= 2 + ( 2x11) = 24 c'est N= 121
le suivant P= 24 + (4x11) = 68 c'est N= 341
P= 68+(2x11) = 90 c'est N=451
P= 90+(4x11) =134 c'est N= 671

donc la multiplication par 11 sera en alterance entre 2 fois et 4 fois pour eviter les multiples de 3 et de 2.

les multiples de 7 dans la colonne 1 commence à la ligne 4 c'est N=21

comme 21 est déjà éliminer avec les 3, donc celui qui reste c'est 91=7x13

91 se trouve à la position 18 donc
le suivant est à P= 18 + (2x7 ) = 32 c'est N= 161
P= 32 +(4x7) = 60 c'est N= 301

idem pour les autre colonnes

colonne 2

M11 143 P= 28

le suivant P= 28 + ( 2x11) = 50 et N= 253
P=50 + ( 4x11) =94 et N= 473

on applique les formules

N = ( P + K ) x 5

Colonne 1 K = 0.2
Colonne 2 K= 0.6
Colonne 4 K= 1.4
Colonne 5 K= 1.8

salut

yoshi · 07-10-2008 16:13:49

Salut,

J'ai fini par trouver comment éliminer les multiples de nombres premiers dans chaque colonne sans savoir quels sont ces nombres.
Calcul et affichage pour 3000 lignes : 30 s...
Reste le cas des puissances... Je ne désespère pas, même si c'est le plus "gros morceau" !

+

Lachkar M · 07-10-2008 16:45:28

Salut

Je vous félicite pour la bonne nouvelle
ce que je n'arrive pas à concevoir c'est les puissances ?

un truque je ne sais pas s'il peut être utile vous savez que le carré d'un nombre impair on peut l'écrire sous cette forme

N x ( N+2) +1 = le carré de la moyenne de N + (N+2)

(2x4) +1 = 9 =3*3

(12x14) +1 = 169 = 13*13

salut

yoshi · 07-10-2008 17:34:11

Re,

Bien d'accord !
Mais je cherche une astuce avec très peu (ou pas de calculs si possible)
Voici les 40 lignes comprenant des nombres premiers, certaines de leurs puissances et leurs multiples ne figurant dans la colonne racine :

    0     3     5     7     0

   11    13     0    17    19

    0    23     0     0    29

   31     0     0    37     0

   41    43     0    47    49

    0    53     0     0    59

   61     0     0    67     0

   71    73     0     0    79

    0    83     0     0    89

   91     0     0    97     0

  101   103     0   107   109

    0   113     0     0   119

    0     0     0   127     0

  131   133     0   137   139

    0     0     0     0   149

  151     0     0   157     0

  161   163     0   167   169

    0   173     0     0   179

  181     0     0     0     0

  191   193     0   197   199

    0   203     0     0     0

  211     0     0     0     0

  221   223     0   227   229

    0   233     0     0   239

  241     0     0   247     0

  251     0     0   257   259

    0   263     0     0   269

  271     0     0   277     0

  281   283     0     0   289

    0   293     0     0   299

  301     0     0   307     0

  311   313     0   317     0

    0   323     0     0   329

  331     0     0   337     0

    0   343     0   347   349

    0   353     0     0   359

  361     0     0   367     0

  371   373     0   377   379

    0   383     0     0   389

  391     0     0   397     0

  401     0     0     0   409

Les puissances incriminées
7² = 49, 7^3 = 343... etc... les multiples de 7 autres : 49, 91, 119, 133, 161, 203, 259, 301, 329, 343, 371
Puissances et multiples de 11 : néant jusqu'à la ligne 40...
13² = 169...etc . Les autres multiples : 221, 247, 299, 377
17²=289...etc. Les autre multiples : 323, 391
19²=361

Je voudrais rendre accessible cette méthode à n'importe qui, non muni d'une calculette, qui sache compter de 2 en 2 et enlever 3, rien de plus...

@+

Lachkar M · 08-10-2008 11:14:59

Bonjour,

Maintenant je vois ce que vous voulez dire par les puissances.
Comme je vous l'ai dit je suis pas fort pour la programmation seulement quelques notions de bases, je vous suggère ce qui suit

Prenons le cas du nombre 7 qui se trouve à la ligne 0 et colonne 4
sa formule N7= ( P + 1.4 ) x 5 , avec P=0 donc N=7
pour trouver les autres multiples dans l'ensembe du tableau, il suffit
d'appliquer cette formule

[ ( Pi + 1 ) x 1.4 ] x 5

i = 0 (( 0 + 1 ) 1.4 ) 5 = 7 L0 & C4
i = 1 (( 1 + 1 ) 1.4 ) 5 = 14 L1 & C5

i = 2 (( 2 + 1 ) 1.4 ) 5 = 21 L4 & C1
i = 6 (( 6 + 1 ) 1.4 ) 5 = 49 L8 & C5
i = 8 (( 8 + 1 ) 1.4 ) 5 = 63 L12 & C2
i = 12 13 x 1.4 x 5 = 91

pour connaitre la position de la ligne on le trouvepar le calcule de la multiplication de

( Pi + 1 ) x 1.4

i = 12 on a 13 x 1.4 = 18.2 ce qui veut dire ligne 18 & colonne de K= 0.2 c'est bien la colonne 1

Idem pour les autres nombres

13 se trouve à la ligne 2 et colonne 2 et 13 = ( 2 + 0.6 ) x 5

[ ( Pi + 1 ) 2.6 ]x5

i = 2 (( 2 + 1 ) 2.6 )x5= 39

i = 8 9x 2.6 x5 = 117

idem pour les autres

Salut

yoshi · 08-10-2008 11:42:31

Salut,

Bonne nouvelle ! J'ai trouvé une méthode simple et j'ai optimisé mon code...
Pour le tri de 15000 nombres sur tes 3000 premières lignes, j'ai un temps, affichage compris, de 25 s (50 s pour 5000 lignes et 25000 nombres)...

       2     5

    0     3     7     0

   11    13    17    19

    0    23     0    29

   31     0    37     0

   41    43    47     0

    0    53     0    59

   61     0    67     0

   71    73     0    79

    0    83     0    89

    0     0    97     0

  101   103   107   109

    0   113     0     0

    0     0   127     0

  131     0   137   139

    0     0     0   149

  151     0   157     0

    0   163   167     0

    0   173     0   179

  181     0     0     0

  191   193   197   199

    0     0     0     0

  211     0     0     0

    0   223   227   229

    0   233     0   239

  241     0     0     0

  251     0   257     0

    0   263     0   269

  271     0   277     0

  281   283     0     0

    0   293     0     0

    0     0   307     0

  311   313   317     0

    0     0     0     0

  331     0   337     0

    0     0   347   349

    0   353     0   359

    0     0   367     0

    0   373     0   379

    0   383     0   389

    0     0   397     0

  401     0     0   409

J'ai testé tous les résidus possibles multiples de 7,11,13,17,19,23,29,31,37,41,43,47 : il n'y en a plus...
Ce n'est pas une preuve suffisante, mathématiquement parlant, mais mon algorithme se comporte avec ces tests ainsi que je l'attendais.
J'ai donc la certitude à 99,9 % d'être dans le vrai.
S'il y a des amateurs, pour chercher la faille, à vot' bon coeur... ;-)

@+

Lachkar M · 08-10-2008 12:06:34

Bonjour Yoshi

Je vous félicite pour votre travail et pour la bonne nouvelle

Ce que je voulais savoir est que vous pouvez faire la comparaison en temps avec le Crible d'Eratosthene dans les mêmes conditions?

Encore une fois BRAVO !!!

Lachkar

yoshi · 08-10-2008 13:04:53

Re,

C'est prévu. J'y réfléchis déjà.

Nouveau test : 10000 lignes, 50000 nombres --> 2 min 19 s. Ca reste raisonnable !
Les 3 derniers nombres 49991, 49993, 49999 sont bien premiers : testés avec http://www.brennen.net/primes/FactorApplet.html

@+

Lachkar M · 08-10-2008 15:59:29

Salut

je vois que ça avance bien , mais il reste la comaraison entre les deux cribles

Salut

yoshi · 09-10-2008 07:32:19

Bonjour,

Mauvaise nouvelle et c'est tellement incroyable que je veux tout vérifier.

Eratosthène vainqueur par 4 à 0. AUtrement dit 22 s contre 1 min 28 s, pour 50000 nombres...

@+

Lachkar M · 09-10-2008 09:12:02

Bonjour

Si vous dite mauvaise nouvelle , c'est vraiment une ICROYABLE !
Il doit y avoir un hic quelque part

Bon courrage

Salut

Barbichu · 09-10-2008 11:17:13

Salut Yoshi,
et avec ce programme là pour eratosthène ? ça te donne quoi ?
(sachant que, sur ma machine la plus lente, il s'exécute instantanément sur l'entrée 50000 et mets 3s sur 500000)

def eratosthene(n):

    nombres = []

    premiers = []

    for i in range(2,n+1):

        nombres.append(True)

    for i in range(2,n+1):

        if nombres[i-2]:

            premiers.append(i)

            for j in range(2*i,n+1,i):

                nombres[j-2] = False

    return premiers

++

yoshi · 09-10-2008 11:24:18

RE,

9 s pour 50 000 000 de nombres....
Mais c'est pas réglo : il faut travailler comme on travaille à la main, sur une grille pré-remplie...
Je vais chercher à comprendre ce que fait ta fct exactement...

@+

Barbichu · 09-10-2008 11:35:51

Re,
Je travaille exactement comme à la main : le numéro de la cellule est le nombre (à 2 près), le contenu est le fait que ce soit barré ou non.
(True si non barré, False si barré (donc si non premier)). Et je n'ai pas besoin de regarder le nombre pour barrer : je raye une case sur i (pour i premier).
++

yoshi · 09-10-2008 14:06:55

Salut,

D'accord ! Mais ce que j'ai voulu dire c'est que tu ne stockes pas de nombres, que les booleens True,False.
Pour afficher tes nombres, il faut que j'affiche les indices de ta liste.
Cela dit, j'ai bien l'impression que travailler avec une liste de nombres qui se suivent à la queue leu leu, est plus simple et plus appropriée que de gérer un pseudo tableau avec un tuple, solution que j'ai employée.
Je vais réfléchir à modifier ma méthode de gestion du crible de Lachkar en fonction de ton idée : il sera moins lourd et moins gourmand en ressources de gérer et stocker True et False que nombres...
Je pense maintenant que, au moins informatiquement parlant, la méthode de Lachkar ne pourra lutter en vitesse contre le crible d'Eratosthène...

@+

Ps Connais-tu un tuto clair expliquant, pourquoi et quand créer des classes en Python (et accessoirement ce qu'elles peuvent gérer ou pas) : le bouquin de Swinnen dont on fait tant de cas est plein de non-dits...
Tu peux répondre par mél...

Lachkar M · 09-10-2008 16:48:10

Bonsoir

Je suis vraiment trés déçu ,moi qui avait pensé avoir trouver un crible trés facile, j'espèce que vous aller trouver la solution.

Autre chose,
Mon idée à moi c’était de dresser des colonnes ou sont inscrits 5 différents types de terminaisons des nombres.
Pour chaque colonne la terminaison est

Colonne 1 ; 11 , 21 , 31 ,41….
Colonne 2 ; 13 , 23 , 33 , 43…..
Colonne 3 15, 25 est à éliminer
Colonne 4 ; 17 , 27 , 37 , 47 …….
Colonne 5 ; 19 , 29 , 39 , 49….

La raison pour passer d’un nombre à l’autre est de 10
Je pensais qu’on pouvait faire une programmation facile colonne par colonne.

Si nous dressons la colonne 1 sous cette forme en 8 colonnes et n lignes
Nous pouvons éliminer facilement les multiples de 3 (21 51 ) en diagonale de gauche vers la droite et les multiples de 7 (21 231 ) de droite vers la gauches.

1 11 21 31 41 51 61 71
81 91 101 111 121 131 141 151
161 171 181 191 201 211 221 231
241 251 261 271 281 291 301 311
321 331 341 351 361 371 381 391
401 411 421 431 441 451 461 471
481 491 501 511 521 531 541 551
561 571 581 591 601 611 621 631
641 651 661 671 681 691 701 711
721 731 741 751 761 771 781 791
801 811 821 831 841 851 861 871
881 891 901 911 921 931 941 951

Salut

Lachkar

Lachkar M · 16-10-2008 12:44:15

Bonjour Yoshi,

je vois que vous avait laissé tomber vos recherches , en ce qui concerne le crible de Lachkar, est ce que vous êtes certains que ce crible ne peut pas concurrencier celui d'Eratosthene.
Je crois qu'avec un peu de perseverence ,il y a certainement une solution et un défi à ce crible.

salut

yoshi · 16-10-2008 16:52:01

Bonsoir,

Non, je n'ai pas vraiment abandonné, j'attends qu'une "idée me trouve"...
M. Lachkar, dans un programme informatique, ce qui ralentit le traitement des informations, ce sont les tests : ces instructions qui commencent par : if...
Si vous regardez bien le petit programme de détermination des nombres premiers de Barbichu (#87 ) par la méthode du crible d'Eratosthène, il n'en contient qu'un seul : 9 s pour le test des 5000000 premiers nombres...
Très très difficile de faire mieux ! Il faudrait pour ainsi dire n'en utiliser aucun ! Mission impossible.

Cela dit, l'informatique, pour une fois, ne rend pas justice à votre crible : je suis persuadé qu'avec un papier et un crayon, il est au moins aussi rapide que celui d'Eratosthène...

@+

Lachkar M · 28-10-2008 15:29:02

Bonjour

Dans mes écrits j'ai touvé une relation à moi que j'avais établit entre la somme des diviseurs d'un nombre impair et le nombre en question.
Nous savons que un nombre pair est parfait si la somme de ses diviseurs lui est égale.Alors que pour un nombre impair il n'en existe pas.
Ma relation à moi est la suivante

Comment on peut appeler un nombre impair si
la somme de ses diviseurs est égale au tiers de ce nombre plus 4

Salut

yoshi · 28-10-2008 20:49:08

Bonsoir,

J'ignore s'ils portent un nom...
Pour les noms nommés aux nombres : abondants, déficient, parfaits, etc...
Voir notamment http://fr.wikipedia.org/wiki/Nombre_abondant
ou encore :
http://villemin.gerard.free.fr/Wwwgvmm/ … ixNbPf.htm
Il me semble ce genre de classification a commencé avec Pythagore (à vérifier).

@+

Lachkar m · 30-10-2008 17:19:25

Bonjour Yoshi

Merci pour les renseignements, j'ai dèjà regardé sur ces sites,mais j'ai rien trouvé en ce qui concèrne mon idée qui est relatve à la relation entre un nombre impair la somme de ses diviseurs.

Salut

Lachkar M · 13-11-2008 15:40:14

Bonjour

Je reviens à cette histoire des nombres premiers et cette fois-ci avec mes carrés "" imagiques""

dressons un tableau de (n,n) ou on inscrit
sur la première ligne de n colonnes les chiffres 2 - 3 - 4 - 5 - ...
sur la deuxième ligne les carrés des nombres de la 1ère ligne
sur la 3ème ligne le cube de la première ligne
et ainsi de suite pour les autres lignes.

prenons par exemple un carré de 3x3 dont son centre est le carré de 3 qui est neuf d'ou on a

2 3 4
4 9 16
8 27 64

si on fait la sommation du nombre de centre 9 avec les nombres des coins on obtient des nombres premiers

9+2=11
9+4=13
9+8=17
9+64=73

prenons le carré ayant pour centre le carré du nombre 5 qui est 25
4 5 6
16 25 36
64 125 216

25+4=29
25+6=31
25+64=89
25+216=241

j'ai d'autres carrés "imagiques" et je laisse à ceux qui s'interessent de chercher d'autres combinaisons

pour le mot "imagique" je ne sait pas d'abord est ce que une telle forme existe+t+elle ou non

Salut

Lachkar M.

Golgup · 13-11-2008 17:40:29

Salut,

C'est quand même fou! les coïncidences!

Il ya de cela 4 jours, je remarquais que n^2 + n-1 donnait souvent des nombres premiers, celle ci est directement liée avec tes tableaux! Mais il ya plein de contre exemples..

A+

Dernière modification par Golgup (13-11-2008 17:44:39)

Lachkar M · 14-11-2008 16:07:47

Bonjour

C'est vrai qu'il y a plein de contre exemple, c'est pour cela qu'il faut dénicher les cas qui peuvent aboutir à des nombres premiers.ceci dit.
Maintenant j'ai autre chose à dévoiler
Nous savons qu'un nombre pair parfait est celui dont la somme de ses diviseurs lui y est égale, par contre les nombres impairs ne répondre pas à cette relation.
Moi je propose la relation ci-dessous qui relait la Somme des diviseurs de ce Nombre et le Nombre impair
soit les relations

N = 45 K – 6 = 3( 4^2 - 1 ) K - 6

N
et S = ------ + 4
3
pour tous K impair

on peut dire que un nombre est parfait impair si

N = S + 2( N/3 - 2 )

pour tout nombre se terminant par 9

39 = 17 + 2( 39/3 -2 ) =17 + 22 = 39

759 n'est pas parfait car :

393 + 2 ( 759/3 -2 ) = 393 + 502 =895

pour les autres terminaisons il y a un petit changemant dans la formule.

---------------------------------------------------------------------
K N Diviseurs S
1 39 1;3,13 17
3 129 1; 3,43 47
5 219 1; 3,73 77
7 309 1; 3,103 107
9 399 1; 3,133 137
11 489 1; 3,163 167
13 579 1; 3,193 197
15 669 1; 3,223 227

17 759 1,3,11,23,33,69 393

On peut dire que SI la somme de diviseurs d’un nombre impair est égale au tiers de ce nombre plus 4, et si on divise ce nombre N uniquement par 3, alors le nombre trouvé sera premier.

Salut

Lachkar M

Gloubi · 03-12-2008 17:42:47

ouah, vous êtes un peu des savants fous, ici. Futurs Euler, Fermat, Mersenne, je vous salue !

je n'irai pas aussi loin, je me demandais juste s'il y avait un moyen de faire un tableau du crible d'eratosthene (pas celui de lachkar, même s'il a l'air très bien, mais c'est pas vraiment dans le vif de mon sujet) avec LaTeX (sans écrire puis barrer les nombres à la main). écrire une commande qui me calcule tout ca tranquillement.

(sinon j'insèrerai une image mais c'est pas très classe)

merci pour votre aide !

Forum de mathématiques - Bibm@th.net

#76 07-10-2008 15:01:16

Re : Nombres premiers

#77 07-10-2008 16:13:49

Re : Nombres premiers

#78 07-10-2008 16:45:28

Re : Nombres premiers

#79 07-10-2008 17:34:11

Re : Nombres premiers

#80 08-10-2008 11:14:59

Re : Nombres premiers

#81 08-10-2008 11:42:31

Re : Nombres premiers

#82 08-10-2008 12:06:34

Re : Nombres premiers

#83 08-10-2008 13:04:53

Re : Nombres premiers

#84 08-10-2008 15:59:29

Re : Nombres premiers

#85 09-10-2008 07:32:19

Re : Nombres premiers

#86 09-10-2008 09:12:02

Re : Nombres premiers

#87 09-10-2008 11:17:13

Re : Nombres premiers

#88 09-10-2008 11:24:18

Re : Nombres premiers

#89 09-10-2008 11:35:51

Re : Nombres premiers

#90 09-10-2008 14:06:55

Re : Nombres premiers

#91 09-10-2008 16:48:10

Re : Nombres premiers

#92 16-10-2008 12:44:15

Re : Nombres premiers

#93 16-10-2008 16:52:01

Re : Nombres premiers

#94 28-10-2008 15:29:02

Re : Nombres premiers

#95 28-10-2008 20:49:08

Re : Nombres premiers

#96 30-10-2008 17:19:25

Re : Nombres premiers

#97 13-11-2008 15:40:14

Re : Nombres premiers

#98 13-11-2008 17:40:29

Re : Nombres premiers

#99 14-11-2008 16:07:47

Re : Nombres premiers

#100 03-12-2008 17:42:47

Re : Nombres premiers

Pied de page des forums