Forum de mathématiques - Bibm@th.net

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Répartition des nombres premiers et multiple de 5

Bonjour,

c'est grâce aux multiples que nous pouvons déterminer qui est ou qui n'est pas premiers sur cette fameuse ligne
pour trouver les nombres premiers il ne reste plus qu'a faire des multiplications

1.Ces multiples de nombres premiers nous sont connus à condition qu'on connaisse ces fameux nombres premiers.
  Je t'ai fourni une liste de 20 nombres : as-tu pu me dire quels sont ces multiples ?
2. Tu veux faire des multiplications ? Soit, pourquoi pas ? Ça marchera à condition que je connaisse lesdits nombres premiers.
    Reprenons le nombre 50845737958021583.
    Avec ta méthode, qu'est-ce que j'aurais dû faire ?
    Etablir la liste des multiples de 7, jusqu'à dépasser ce nombre. Aller au suivant...
    Etablir la liste des multiples de 11, jusqu'à dépasser ce nombre. Aller au suivant...
    Etablir la liste des multiples de 13, jusqu'à dépasser ce nombre. Aller au suivant...
    ................
    Enfin, établir la liste des multiples de 431 et constater que l'un d'entre eux est égal à 50845737958021583 et conclure que ce nombre n'est pas premier...
Si oui, alors, le coût en temps et en nombre de tests est prohibitif...
Moi, qu'ai-je fait ?
Avec la liste des nombres premiers inférieurs ou égaux à [tex]\sqrt{50845737958021583}[/tex], je n'ai fait qu'un test chaque fois : j'ai cherché le reste, avec à chaque fois le même test : le reste est-il 0 ? Oui, on s'arrête, non on continue...

rien ne nous interdit de faire la table de multiplication des nombres premiers supérieur à 3 entre eux

C'est bien ce que je disais, alors...
Prenons les nombres premiers inférieurs à 65536 ([tex]2^{16}[/tex]) : j'en dénombre 170 ( à partir de 5).
Le nombre de multiples de ces nombres premiers (en ne les comptant pas eux-même) est supérieur à 42.000.000 !
Pourquoi 65536 ? C'est grosso modo la racine carrée de 4294967291.
Ce nombre étant premier, je vais devoir, avec ta méthode, effectuer d'abord plus de 42000000 de multiplications (en supposant que je connaisse la liste des premiers < 65536) pour avoir la liste des multiples, puis effectuer plus de  42000000 de comparaisons pour conclure ? Avec un nombre aussi "ridiculement petit" ?
J'ai testé mon programme : je découvre la primalité de 4294967291 en 11/100e de s...

Je testerai la vitesse de ta méthode si tu me confirmes que j'ai bien compris...

@+

plg

Invité

Re : Répartition des nombres premiers et multiple de 5

Bonjour il paraît évident yoshi, que sa méthode serra beaucoup plus lente, mais surtout elle va prendre beaucoup de mémoire, c'est bien pour cela d'ailleurs que l'on fait fait des variante au crible Eratosthène...

¤@tibo
quel crible tu veux écrire en python.. est ce pour cribler une famille de premiers par exemple les premiers 30k+7....?
ou pour les 8 familles 30k+1 et 30k+P avec p appartenant à [7;29]..?

car dans la première méthode :30k +7, il faut faire attention à une instruction...:
comment déterminer si un complémentaire P + k30 est premier:

a) si le couple p et (p'+ k30) arrive dans une cellule (" sur un entier de cette famille 30k+7")  deux possibilités; soit la cellule est marqué d'un 0 donc cet entier a été déjà factorisé par un premier (p'+k30) dans ce cas le complémentaire p+k30 n'est pas premier, il est éliminé.. et la base p repartira avec son nouveau complémentaire p +((k+1)30) (autrement dit le complémentaire augmente de 30). soit le couple p et son complémentaire arrive sur l'entier ou cellule marqué d'un 1, et: c'est au tour de ce couple de base de partir: la base p divise le complémentaire p+k30, si le reste = 0 ce complémentaire est un multiple de p sinon il est définitivement premier, il part en premier, marque d'un 0 tous ses multiples  jusqu'à la limite x du crible fixée et sort du crible, puis la bas p compte son nombres de cellules soit p cellules,et se positionne en attente avec son nouveau complémentaire augmenté de 30.....etc pour les 8 bases P [7;31] puisque 1 ne peut être une base P.

pour en revenir aux moutons de madgel

quel est le cycle périodique des entiers congrus à 1 ou P modulo 30...tel que p est défini..

en partant de 1, tu as: 6,4,2,4,2,4,6,2 soit la somme des entiers de ce cycle te donne 30, il n'y a pas de mystère  et cela n'indiquera pas pour autant :
dire qui est multiple de qui, si tu ne connais pas les nombres premiers qui le factorisent, pas plus que ta ligne 1+4+2 que le crible modulo 30 ou modulo 6
pour un entier  tiré au hasard , et supérieur au limite d'un crible...Eratosthène ou une de ses variante.

plg

Invité

Re : Répartition des nombres premiers et multiple de 5

Prenons les nombres premiers inférieurs à 65536 ( 2¹6 ) : j'en dénombre 170 ( à partir de 5).

170 premiers..? inférieur à 65536
la je ne suis pas....joshi..?

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Répartition des nombres premiers et multiple de 5

Re,

Désolé, oubli de ma part : j'étais d'abord parti sur 1000...
Je te redonne la bonne valeur : 6540 (sans 2 et 3).
Tu aurais dû te douter de ça : à partir de 170 nombres premiers, je ne peux pas avoir plus de 42000000 de multiples...

@+

madgel

Invité

Re : Répartition des nombres premiers et multiple de 5

Bonjour

mon idée c'était de faire travailler 3 ordinateur de concert
et chaque ordinateur n’exécutant qu'un programme
un ordinateur qui établi la liste1 des nombres produit par 1+4+2
le deuxième ne ferait que reprendre la liste 1 pour les multiplier entre eux
et le 3 ème ne ferait que soustraire les éléments de la liste 2 de la liste1
donc avec ma méthode , je ne test pas, je fais simplement deux listes
une qui contient les nombres premiers et leurs multiples
et la deuxième qui ne contient que les multiples
pour terminer je fais une soustraction
liste1 - liste2= listes des nombres premiers
je pense qu'on pourrait aller loin en une journée de travail
c'est le système de la chaîne, je pense que un programme ne faisant qu'une opération
est plus rapide qu'un programme qui fait plusieurs opérations à la suite
en faisant travailler 3 ordinateur simultanément, le temps de travail est divisé par 3
pourtant
j'ai une vague impression, qu'il manque 1 détail, quelque chose d'important,dans toute ces trouvailles,
il y a surement un détail, une observation majeure, qui nous échappe encore, et qui nous permettrais de savoir
si un nombre est ou n'est pas premiers du premiers coup d’œil
sans avoir à établir de liste, de test ou de crible
à+

plg

Invité

Re : Répartition des nombres premiers et multiple de 5

@yoshi
j'ai bien compris qu'il y avait une erreur, mais je cherchais comment tu décomptes les multiples de 65536²
j'ai donc supposé que tu faisais une estimation de premiers :4294967291 / ln4294967291= X puis, tu déduits X de 4294967291, ce qui te donne en gros le nombre de multiples....soit au minimum 4101332040 et en gros 42000000000.

de toutes les façons la méthode est ridicule, car même en utilisant le crible Eratosthène en mode factorisation , pour connaître les multiples de P premier qu'il y en est un ou plusieurs il faut aller au bout du crible pour les connaître, mais il n'y a aucune prédiction , à la rigueur des probabilités...
et je peux te garantir que son crible il est loin d'égaliser en vitesse le tien pour un nombre fixé, ou l'algorithme modulo 30 ou modulo 6 pour connaître tous les multiples de p pour une limite fixée...

à moins d'être un autiste savant par comme Daniel Tammet, qui pour lui , les nombres premiers se distinguent des multiples, par une image différente....mais avec une limite.

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Répartition des nombres premiers et multiple de 5

Re,

le deuxième ne ferait que reprendre la liste 1 pour les multiplier entre eux

??? Bin voyons, yaka !
Si je prends 3 ordinateurs identiques au mien, avec le même logiciel, si je veux tester la primalité du nombre 4294967291, je dénombre 6540 nombres premiers, de 5 à la racine carrée 65536...
Tu as une idée du nombre de multiples que ça représente ?
Voilà :
5447178944291084972779663832122989203892618883168412774182737439302060465221002874466331356457211094275810539875411414852377789394158874261526194362143711989469137433894279358515184066603239685775918397552366412583983166014798906086067053931174074323009641892590148892461181436283263617637624440084871979780586352592543221344605056837902730406434204019523170110477017073127797840211785923935382654513009913478635088656850193730952838820424300566999517511642303574179269546403839822985208334957293886982154147170340694137805067870147769032744293082345254425280951636744304877294155100341082714479840506031047374596640475917878315087327793217783398099911906192525972941869770012042526661577073310162243807265448603863187647824324866155732057206553981404823826651149827044067429374379216260830511145877877707191749257294548805496241419219802141386542210906546869987076522105051397187485428779695599557509030226263029155888667694111329965023440925736211884310260377062124118192216418460445182781041245963697098543744312379051282125619972409394254075070744643243395554996398013982684685745080403600018984184580527609738211534827907693880111794532438761805818295723770438973243233715742027684666672864063118784999161534502329619443316500935106107688538837345833932634378472435376124142260026895879758982979578381737557662653270084955891232184928256215002385986498124022764812751759985051301558073571963077587411557823261823475290054649848708824938497269484722130916709713602664710397210658550694525571884590552730944319358191502069778525807270418274102522394742607633821743699629117657118171777307695812068829293660145520674015324329554944580338162150141243576041351675099704241776380461448609995643023270800583292114913939573780009552996577848968352389383527804669884549238109826778168418458754300082963559563188397753498969004768454367848195159930030213201108226471876630248060933901000811190122684096677334060540011934182759965303871625068036327218921389270955761153867775

(Exemple avec [2,3,5,7,11] :
2,3,5,7,11                                       --> 1 nombre
6,10,14,22,15,21,33,35,55,77             --> produits de 2 nombres
30,42,66,70,110,154,105,165,231,385  --> produits de 3 nombres
210,330,462,770,1155                       --> produits de 4 nombres
2310                                              --> produit de 5 nombres
Soit 31 multiples [tex]2^5-1[/tex])

Et la mémoire nécessaire ?  De 5 à 65535 2 octets par nombre, de 65536 à 167772156 3 octets, de 655536 à 4294967295 4 octets.... Je n'ose pas y penser !

En plus, tu vas gérer une 2e liste, sans compter la mémoire utilisée par le système, la mémoire pour les calculs...
Mon ordinateur est alors engorgé et ne peut tourner.
Alors qu'avec un crible d'Eratosthène, je tourne, je recherche les nombres premiers de 5 à ma racine carrée et je teste 20 très grands nombres le tout en 5 min 5 s (avec un programme mal foutu, en prime)...

Non, ta méthode est bien trop gourmande en ressources...

@+

@plg.
Je m'étais planté ailleurs encore...
Parce que le nombre de multiples différents des premiers de 1 à n, je pense, est le même que le nombre de parties d'un ensemble à n éléments -1 (l'ensemble vide), d'où le nombre de multiples ahurissant ci-dessus [tex]2^{6540}-1[/tex]...
Hmmm, ça me paraît beaucoup trop...

Dernière modification par yoshi (18-10-2013 18:06:08)

plg

Invité

Re : Répartition des nombres premiers et multiple de 5

tout a fait yoshi...il va saturer....très très vite ..

au moins tu comprends pourquoi avec mon algorithme j'ai de grande limite , car je n'ai que des 1 ou 0; mais plus la limite du crible est haute, et bien comme tous le monde la mémoire sature... car je ne peux pas construire un tableau ou une ligne virtuelle de 1 aussi grande que je le voudrai.
de plus il me faut aussi les numéroter ensuite de 1  à 450 000 000 000 ou stocker les nombres premiers  de 7 à 450 000 000 000 ce qui limite la mémoire d'une manière ou d'une autre....!

même le dernier algorithme que j'ai trouvé ,il est basé sur la conjecture de Goldbach, il utilise quand même une variante d'Eratosthène, mais avec le même principe et même méthode.
la différence réside dans le fait que l'on peut aller assez loin, mais limité par le nombres de premiers que l'on va stocker au fur et à mesure de 7 à X en principe, tous les premiers < 500 000 000 000.

c'est à peu près la même méthode qu'Eratosthène modulo 30, c'est à dire que l'on travail avec une base de donnée de 8 premiers [7;31] comme les algorithmes précédent,
et on utilise la congruence de 30k modulo p_i
les modulo p_i sont les premiers inférieurs à la racine carrée de 30k et on recommence à chaque fois donc le crible avance par pas de 30.
donc on teste uniquement les 8 premiers P appartenant à [7;31] et on stock les complémentaires q premiers :
tel que 30k - P = q premier.

il est évident que pour 500 000 000 000  il y a racine carré de 500 000 000 000 de modulo p_i
donc autant de reste R de 500 000 000 000 par p_i,j qui vont vérifier les 8 premiers de base [7;31]
cela fait quand même beaucoup de division ou alors d'addition méthode Eratosthène...mais on doit quand même vérifier la congruence de tous les modulo p_i par rapport à 30k = environ 500 mds....

autre avantage c'est que l'on a pas besoins de connaître tous les nombres premiers < 30k/2,
de plus les modulo p_i, sont puisé au fur et à mesure dans la base de donnée première, qui est stocké au fur et à mesure du crible et de la décomposition de 30k

donc le principe est : on vérifie si P est congru à 30k modulo p_i; avec P appartenant à [7;31]et on part de 30k = 60 ou 90 et ou 120,150..
mais il faut dans ce cas stocker la base de donnée première des premiers compris entre 7 et 150. ce qui se fait facilement dans ce genre de programme.
puis on lance le crible 180;210.....30k etc

les p_i,j < sqrt de 180 :7,11,13, le reste R de 180 par 7 = 5 ; par 11 = 4 ; et par 13 = 11

les premier P congrus à 180 modulo p_i sont :

5 +(2*7) = 19 ; 19+14 = c; c+14  > 31 fin du test pour 7
(11 +4) +22 = 37 > 31 fin
(13 +11) donne déjà P = 11, puis 11+2*13 = 37 > 31fin

on a donc 11 et 19 congrus à 180[p_i,j]

on relève les p' = 180 -7, 180-13,180-17, 180-23, 180-29, et 180-31, que l'on rajoute à la base de donnée p' 150,180: soit :
173; 167;163; 157; 151, et 149. qui sont bien les premiers suivants, appartenant à [149;180]...etc

**************************************
(7).    (11).    (13). (17).    (19). (23) .(29).    (31).
37.....41....43.....47.............53....59....61
67.....71....73.............79.....83....89.......
97.....101..103...107..109.. 113.............
127...131...........137..139......... 149 ..151
157..........163...167...........173.
*****************************************
on passe à 30k = 210 et on réitère.

plg

Invité

Re : Répartition des nombres premiers et multiple de 5

Je m'étais planté ailleurs encore..

yoshi je ne suis pas sur que tu te sois planté pour le nombre de multiple < 65536², car tu es d'accord que lon déduit de 65536² ,pi(x) où pi(x) est le nombre de premiers inférieur à 65536² donc cela fait bien en gros 42000000000.
car on ne peut pas compter deux foix ou n fois les mutiples de 7, puis de 7et 11 ou de 7,11 et 13 par exemple ces trois multiple sont ne comptent pour moi que pour un... non ?
exemple :
10000 /7 = X , nombre de multiples de 7
10000/ 11 = Y , nombre de multiple de 11 et qui contiennent aussi des multiple de 7; c'est à dire que Y/7 = Z vient en déduction des multiple de 11 soit Y - z . etc pour 13,17.....P

en reprenant ton nombre : 4294967291 on a : 4294967291/ 3,75 = entiers non multiple de 2,3 et 5  soit 1145324610 entier
4294967291-1145324610 - 3  = 3149642678 multiples de 2,3 et 5

nombre de premiers >5 et < 4294967310 = 203 280 218

1145324610 - 203280218 = 942 044 392

nombre de multiples de p < 4 294 967 310:

3 149 642 678 + 942 044 392 = 4 091 687 070 multiples

mais il est clair que le nombre d'opération méthode madgel est nettement supérieur, car il va multiplier des doublons à profusion...

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Répartition des nombres premiers et multiple de 5

Bonjour,

Je vais me limiter aux multiples "simples" (je ne compte pas les combinaisons) des nombres premiers inférieurs à 65536 et supérieurs à 5, à savoir les multiples de 5 non multiples de 3 nu de 2, puisque j'ai 6540 nombres premiers de 5 à 65536 ...
Exemple :
je reprends [2,3,5,7,11], j'appelle multiples simples
2*3, 2*5, 2*7, 2*11
3*5, 3*7, 3*11
5*7, 5*11
7*11
soit un total de 4*5/2 =10 ..

Pour les 6540 premiers de 5 à 65536
* j'ai 6539 multiples de 5 (ni de 2 et 3 puisque ceux-ci ne figurent pas dans ma liste)
* j'ai 6538 multiples de 7 non multiples de 5 (ni de 2 et 3 puisque ceux-ci ne figurent pas dans ma liste)
* J'enlève le 5 et le 7 : j'ai 6537 multiples de 11 non multiples de 5 ni de 7
Soit un total de 21.382.530 multiples pour les nombres premiers inférieurs à 65536 !
Pourquoi tester 21 000 000 de multiples d'ailleurs, il nous faut nous limiter à ceux inférieurs à 65536, soit 9465 ce qui oblige pour établir cette liste à quand même faire 21000000 de tests pour éliminer ceux qui sont supérieurs à 65536...

Ceci fait, posons-nous la question : comment établir  la liste des 6540 ombres premiers ? Parce qu'il m'est nécessaire de les avoir...
En dressant la liste des nombres impairs non multiples de 3, puis en éliminant les multiples au fur et à mesure ? C'est bien long tout ça...
Impensable...

@plg
Au départ je remplis une liste ne comprenant que des 0 pour les nombres de 2 à 65536
puis je teste si
* le temoin est à 0 : je le passe à 1 (il est premier) je stocke au fur et à mesure tous les nombres dont les témoins sont à 1, en ajoutant 2 à leur indice.
* je passe ses multiples à -1 (= déjà traité) en commençant par le carré du nb premier trouvé...

C'est très mal foutu, parce que je teste au fur et à mesure plusieurs fois les mêmes témoins : c'est là-dessus qu'il faut que je travaille...

@+

madgel

Invité

Re : Répartition des nombres premiers et multiple de 5

bonjour
il est possible d'éviter une partie des doublons, en ne multipliant les nombres premier supérieur à 3, que par eux même et les nombres premiers, qui leurs sont supérieurs, cela évite qu'ils se re multiplie avec les nombres premiers qui les précèdent.
mais il y aura toujours des doublons, ceux qui sont le produit de plusieurs nombres différents
genre 1001 qui est le produit de :91 x 11; 7 x 143 ; 13 x 77 il y en a peut-être d'autre
a +

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Répartition des nombres premiers et multiple de 5

Salut,

A ce stade, il convient d'être clair.
Qu'est-ce que pour toi la liste des multiples de [2,3,5,7,11]
Réponse 1 :

2,3,5,7,11
2*3, 2*5, 2*7, 2*11
3*5, 3*7, 3*11
5*7, 5*11
7*11

Là en partant de n nombres, j'ai [tex]\frac{n(n-1)}{2}[/tex] multiples. Soit avec n = 5 --> 10 multiples.
Pour 40 nombres, 780 multiples.

Réponse 2 :

2,3,5,7,11
2*3, 2*5, 2*7,2*11,
3*5,3*7,3*11
5*7, 5*11
7*11
2*3*5, 2*3*7,2*3*11
2*3*7,2*3*11
2*3*11
2*5*7,2*5*11,
2*7*11
3*5*7,3*7*11
5*7*11
2*3*5*7,2*3*5*11
2*3*7*11
2*5*7*11
3*5*7*11
2*3*5*7*11

Là en partant de n nombres, j'ai [tex]2^n-1[/tex] multiples. Soit avec n = 5 --> 31 multiples.
Pour 40 nombres, 10.995.116.277.755 multiples
Il n'y a aucun doublon dans les deux cas...
Ce n'est pas du tout la même échelle !!!

@+

plg

Invité

Re : Répartition des nombres premiers et multiple de 5

Ce n'est pas du tout la même échelle !!!

et malheureusement pour lui, il est bien obligé d'en tenir compte et où: la limite se situe bien a:  [2*3*5*7*11] les multiples de p, comme les nombres premiers doivent tous être pris en compte..!
lorsque l'on compte tous les multiples inférieur à une borne, il n'est pas question d'en oublier. donc 2*3 est un multiple < [2*3*5*7*11], 2*3*5 en est un autre, de même que 3*5...etc soit au total la réponse 2, ou bien cela n'a plus aucun sens dans sa théorie, qui commence à fumer....

ou alors effectivement on peut déclarer que l'on compte uniquement tous  les multiples de 2 premiers ce qui n'est pas très cohérent...., et qui de toute les façons, laisserait en route les multiples de 3 premiers, de 4 premiers de n premiers...on peut faire une entorse en disant que ce ne sont pas de bons multiples....

un entier naturel se décompose de façon unique en facteurs premiers point barre ...Mr madgel.

Au départ je remplis une liste ne comprenant que des 0 pour les nombres de 2 à 65536

ensuite tu les test pour savoir si ils sont premiers..? ou pour savoir de qui ils sont multiples
si tu fais un tableau de 8 colonnes tu peux donc tester uniquement les premiers > 5 en écrivant tes nombres en progression arithmétique de raison 30.
ce qui te fais tester que 65536/3,5 = 18724 nombres soit 18724 zéro , ensuite je ne comprends pas pourquoi tu repasses par les témoins qu tu as déjà testés ou alors on parle pas de la même chose...

car si il s'agit d'identifier de qui ils sont multiples:

je dirai peu importe lorsque tu les tests au lieu de marquer 1, tu marques le facteur p qui serra de toutes évidence le plus petit..en commençant par 7, puis tu testes ce qui reste avec 11, ..13...17....P_n.

comme le crible en mode factorisation mais en plus rapide car la tu n'auras que le plus petit facteur p qui décompose ce multiple...ce qui va très vite.
exemple 7007 , tu passe le témoin à 7 c'est tout peu importe qu'il soit aussi factorisé par 11, et par 13. ce nombre serra multiple de 7 mais tu ne le retestera plus car il a déjà un témoin = p = 7...
enfin si on parle de la même chose.....

sinon met moi un exemple:

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Répartition des nombres premiers et multiple de 5

Ave,

Je réfléchis...
Bon, ma problématique est simple, pour éliminer les multiples de 5 (par ex), j'ai adopté un pas de 5 depuis 5²...
Mais ce faisant, je me retrouve mettre à -1 les témoins de 30 40 45 qui le sont déjà puisque respectivement déjà multiples de 2 et 3, de 2, de 3...

Je cherche donc pour un nombre premier n donné, si je ne peux pas trouver l'écart ou les écarts qui le sépare de ses multiples qui ne sont pas multiples des nombres premiers inférieurs à n...
Ça m'a tout l'air d'être contre-productif, sauf, si je trouve une formule définissant cet écart en fonction de ce nombre premier n...
En partant de n² (n premier), écarts entre les multiples de n non multiples des premiers précédents...

(5²) 25 --->
10 20 10 20 10 20 10 20 10 20

(7²) 49 ---> écarts dans l'ordre
[28, 14, 28, 14, 28, 42, 14, 42, 28, 14, 28,

(11²) 121 ---> écarts dans l'ordre
22, 44, 22, 44, 66, 22, 66, 44, 22, 44, 66, 66, 22, 66, 44, 22, 66, 44, 66, 88, 44, 22, 44, 22, 44, 88, 66, 44, 66, 22, 44, 66, 22, 66, 66, 44, 22, 44, 66, 22, 66, 44, 22, 44, 22, 110

(13²) 169 ---> Tous les écarts différents sont
[26, 52, 78, 104, 130, 156, 182]

(17²) 289 ---> Tous les écarts différents sont
[34, 68, 102, 136, 170, 204, 238]

(19²) 361 ---> Tous les écarts différents sont
[38, 76, 114, 152, 190, 228, 266]

A partir de 7 ça se gâte pas de périodicité apparente...

@+

Dernière modification par yoshi (20-10-2013 11:13:31)

plg

Invité

Re : Répartition des nombres premiers et multiple de 5

A partir de 13 ça se gâte...

ce qui est normal, et tu ne pourra pas avoir une formule qui te donne un écart type entre les multiples d'un nombre premier  donné, non multiples des autres premiers, sauf si ces nombres premiers < P dont tu cherches l'écart, laisse un témoin donc tu sautera ce multiple en question,  et ton écart sautera aussi.....son idée est absurde.

c'est bien pour ça que le crible Eratosthène serra plus efficace , l'écart types d'un premier est P entre chaque nombre multiple de P, donc lorsque vient le tour de P > à 5,7,11,13,17,19...pn < P ; tu es bien d'accord que tous les multiples de P, qui ne sont pas déjà marqué par pn < P sont les multiples de :

a_) de p à la puissance n

b_) des facteur pi > P et qui ne sont pas multiple de [5..pn.]

Alors je te laisse imaginer les écarts entre ces multiples, qui sont tout aussi aléatoire que la répartition des nombres premiers. Aléatoire voulant dire impossible à déterminer sauf avec un crible est une limite x fixée...! retour case départ et tu encaisse 10000 je rigole....

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Répartition des nombres premiers et multiple de 5

Salut,

Je viens de refaire les tests avant d'avoir vu ton post...
C'est dès le nombre 7 que ça se gâte...
Au pire, à partir de 5, pour tout nombre premier n, depuis n², je testerai de 2n en en 2n (qui est l'écart minimum), au lieu de n en n comme maintenant... Et je parle bien du crible d'Eratosthène, la méthode de notre ami n'est valable que pour des petits nombres, sinon, la consommation de ressources est prohibitive.
Quand on le fait à la main, on voit les multiples rayés, et on passe... La machine, elle ne le peut encore pas ! ^_^
Une solution serait de retirer de la liste tous les multiples de n premier en cours, sans laisser de trous, mais après ce doit être assez "sportif"... Je vais y réfléchir.

@+
[EDIT]
Mise en place du pas de 2*n : gain 55 s. 4 min 10 s au lieu de 5 min 05 s pour mes 20 nombres tests

Dernière modification par yoshi (20-10-2013 13:23:52)

plg

Invité

Re : Répartition des nombres premiers et multiple de 5

je crois bien que cela va être sportif...
mais effectivement en supprimant les multiples déjà marqués, cela éclairci...mais ce n'est pas gagné.
de plus je pense et je reste convaincu que les multiple de 5 ne te serve à rient..si ce n'est à encombrer les calculs
donc travailler modulo 30 serait il me semble plus simple et économique.
7 . 11. 13. 17. 19. 23. 29. 31
37.41. 43. 47. 49. 53 .59 . 61.
..etc
bonne soirée

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Répartition des nombres premiers et multiple de 5

Salut,

Oui, mais je tiens à rester sur un crible d'Eratosthène pur...
Et je cherche maintenant à minimiser les tests.
A côté des inconvénients, mon système présente des avantages...
Soit un ensemble de témoins :
[1,1,-1,1,-1,1,-1,-1,-1,1]
En ajoutant 2 à l'indice du témoin à 1, j'obtiens le nombre premier correspondant :
0+2 -->, 1+2--> 3, 3+2 --> 5, 5+2  --> 7, 9+2 --> 11
Mais si mes témoins représentent les états des nombres 7 11 13 17 19 23 37 41 43 47 49 53 67 71 73 77 79 83 97 101, je n'ai pas d'idée pour l'instant de lien entre l'indice du témoin et le nombre qu'il représente...
Ces nombres sont les 6n+1 et les 6n+5 pour n de 1 à 16 si le chiffre des unités de n n'est pas 0, 4, 5, ou 9.

@+

[EDIT]
Une idée m'est venue qui devrait marcher : je teste demain sur une liste plus étoffée...

plg

Invité

Re : Répartition des nombres premiers et multiple de 5

si tes [1,1,-1,1,-1,1,-1,-1,-1,1] sont les témoins de tes nombres premiers, est ce que les 1 et les -1 représente deux familles distinctes de premiers tel que
les 1 = P de la forme 6n+1
les -1 = P de la forme 6n+5.

car si c'est le cas et que tu rajoutes 2, et toujours 2 à cet indice, rient ne peut te dire si l'indice de ton témoin est premiers ou pas ...
même en séparant les témoins en deux familles .

d'autant que tu impliques tous les entiers impairs à la suite:
0+2 -->, 1+2--> 3, 3+2 --> 5, 5+2  --> 7, 9+2 --> 11

alors que modulo 6 on devrait avoir:

1,5,7,11,13,17,19,23,25,29,31,35....etc c'est à dire n-1+ 6 et n +6;...  donc en déterminant si n est de la forme 6n+1 ou -1 on repart
exemple
101 = n-1 +6 et donc (n-1+2)= 103 +6.
soit:
101,103,107,109,113,115....etc

moi lorsque je crible modulo 6, je sépare mes deux famille et j'utilise un témoin qui est 1, et qui se change en 0, lorsque le 1 en question n'est pas premier mais c'est du pure Eratosthène...!

exemple famille 6n+1:
voila mes témoins au départ du crible ou le premier 1vaut 7:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1
puis
1 1 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1 0 1 0 1 1

........5².......7²... (5.11),(5.17)   (7.13)

les 0 sont les multiples de5, puis il y aura ce de 11, 17......p+6...etc. Tous les 5 nombres tous les 11 nombres tous les 17 nombres tous les P nombres...

et idem pour 7 et ses complémentaires
7+6 :13,19 (+6+6) 31, 37....etc

seule les deux bases 5 et 7, ne marque pas leur multiples du premier coup..mais leurs complémentaires P premiers, comme 11,17 ...p_n+6 ; et ou 13,19 ...p_n+6 ; eux : marquent jusqu'à la fin du crible leur témoins et sortent du programme...

et lorsque la base 5 fait apparaître sont dernier complémentaire (k6 + 5) inférieur ou égale à la racine carrée de la borne fixée, 5, continu jusqu'au bout, s'en s'arrêter; et marque tous ses témoins tous les 5 nombres  puis sort du crible.
Fin du crible pour 5 et ses complémentaires; Eratosthène...!

et pareil pour la base 7.sort du crible et fin du crible .

les témoin 1 sont les nombres premiers, les 0 les multiples de P_i,j.....il n'existe pas de lien entre l'indice et les témoins....

moi je n'ai qu'un test à faire sur l'une ou l'autre base 5 ou 7.

c'est à dire: lorsque 5 arrive sur son nombre (et tous les 5 nombre, par pas de 5 donc) soit ce nombre 1, est déjà changé en 0 donc je n'ai pas à tester ce complémentaire car il n'est pas premiers.

si par contre ce cinquième nombres est 1, cela indique qu'il n'a pas été factorisé, par un premier > 7.
Donc dernier teste pour savoir si le complémentaire de 5,  qui est = à 6k +5 est premier; et bien tu le divises par sa base 5.

Si le reste de (6k +5) par  5 est 0 , le complémentaire est supprimé et la base 5 va se positionner 5 nombres plus loin avec son nouveau complémentaire (6k+5)+6, soit (6(k+1)+5) etc..

Si le reste de (6k+5) par 5 n'est pas 0, ce complémentaire est premiers, il part marquer tous ses témoins par un 0, tous les (6k+5) nombres , puis sort du crible...Eratosthène.

Et il en est de même pour la base 7.

à toi....

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Répartition des nombres premiers et multiple de 5

Re,

car si c'est le cas et que tu rajoutes 2, et toujours 2 à cet indice, rient ne peut te dire si l'indice de ton témoin est premiers ou pas ...

Si, si ça marche...
Sur et certain !
Au départ je n'ai que des zéros pour les nombres consécutifs de 2 à n, et les indices +2 donnent tous ces nombres de 2 à n...
Le premier est à zéro, il correspond à 2 qui est premier puisque j'ai choisi de commencer par un premier, le nombre 2...
Je passe ensuite l'indice n° 3 à -1 c'est le nombre 4, puis je fais de même pour 6, 8, 10, 12, 14, 16.... dont je passe les témoins à -1 (nombres barrés).
Je reprends ensuite au suivant de 2, c à d 3, témoin à 0 --> passage à 1, il est premier...
Je traite alors les multiples à partir de 9 (parce que 3*2 a été traité avec 2) : 9, 15,  21, 27,... (12, 18, 24 aussi déjà traités avec 2)
J'ai donc barré 4, 6, 8, 9, 10, 12, 14, 16, 18, 20, 22, 24...
Reste 2, 3, 5, 7, 11, 13, 17, 19, 25... après, c'est encore trop loin
Le témoins de ces nombres sont à 0 à partir de 5.
Donc 5 premier. 5*2, 5*3, 5*4 ne sont pas à considérer, je démarre à 5² puis je vais de 10 en 10 :
Les témoins de 25, 35, 45, 55, 65 passent à -1...
Tu peux constater qu'entre 7 et 49 tous les multiples de 2, 3 et 5 sans exceptions sont traités..
Ce qui permet de dire que 7 dont le témoin est à zéro est premier, je passe le témoin à 1 et je démarre le traitement des multiples à 49, tous les multiples inférieurs son traités...
Si 7 n'était pas premier, il aurait été traité comme multiple de premier inférieur à 7 et son témoin passé à -1...
Tu n'en as peut-être pas eu l'impression, mais je ne suis pas un débutant en programmation : j'ai commencé avec le Basic de l'Amstrad CPC 6128, il doit y avoir 40 ans...
Donc, si je publie un programme, je te certifie qu'il fonctionne et qu'il est cohérent mathématiquement parlant...
Une seule fois, je me suis planté voir ici mais après explication de cette histoire de "descente infinie de Fermat", j'ai rectifié le tir...

Mais il va falloir que je me penche sérieusement sur tes propositions et voir ce que je peux en tirer.
Pour l'instant j'ai d'autres fers au feu !

@+

plg

Invité

Re : Répartition des nombres premiers et multiple de 5

je pense que tu as aussi compris,  que l'on peut accélérer l'algorithme en changeant les deux base 5 et 7 par,  par exemple 41 et 43 selon le même principe mais avec une modification sur la position de départ de ses deux bases.

cela sous entend que les premiers P : 5 <P < à 41 , et 7 < P <43; ont marqué tous leur témoins depuis leur position de départ...

donc toujours pareil pour la famille 6k+1 :
5*5, 5*11 position du départ de 11, 5*17 position du départ de 17, 5*23...idem pour 23; 5*29..., (5-35 non) et 5*41 positionnement de la base 41qui va se projeter directement sur sa position 41² . et de la , son premier complémentaire 41 nombres plus loin, serra 41+6 = 47 = 6k+5.

et on fait la même chose pour 7 et 43....

le crible avance par pas de 42 soit: 41 et 43 pas au lieu de 6 pas = (5+7)/2...

pour 7 on positionne 7*7 , puis 7*13, position de départ de 13...jusqu'au bout ; 7*19 idem pour 19....; 7-25 , 7*31 idem pour 31.... 7*37... et 7*43
position de la base 43; 7 marque jusqu'au bouts ses témoins..

la base 43 va se positionner sur sa position 43² :

c'est à dire: 43² = 1849; 1849 -7 =1842; et 1842 / 6 = 307ème témoin en partant de 7, donc du premier 1  pour n = 0 .

le premier complémentaire de 43, serait 49=7² donc 43 nombres plus loin et ce témoin est un 0, car il a été marqué par 7. La base 43 va se positionner 43 nombre plus loin avec 55, à nouveau un 0, elle repart se positionner 43 nombres plus loin avec 61....qui par obligation est un 1. puisque le complémentaire 61 est un nombre premier.....une foi la base 41 passée, cela serra à nouveau le départ de 61 jusqu'au bout; et de 43 , 43 nombres plus loin avec son complémentaire augmenté de 6 : 67...etc 

voila un programme assez simple à faire...en principe, car  n'y connaissant rient en programmation....

@+

plg

Invité

Re : Répartition des nombres premiers et multiple de 5

rassure toi yoshi en programmation je ne met absolument pas tes capacité en doute ni même la certitude, que cela fonctionne:

mais  uniquement il me semble "la longueur des tests" et d'écrire tous les entiers impairs..qui mangent des octets.....
au lieu de les écrire modulo 6 ce qui  t'enlèvera des multiples inutiles dont tu n'as pas besoins..pour avancer  lorsque tu es à 7
donc 7² = 49, je suppose que tu avance par pas de 14 pour barrer les impairs ,
et ensuite idem pour 11 et 121 par pas de 22....etc

ce qui revient presque au même que l'algorithme modulo 6 ci dessus, sauf que l'on représente les impairs par une liste de 1 à X fixé, limite du crible.
à la fin on relève les 1 que l'on transforme en premiers soit le (nième 1) * 6 +7 = P.
ce qui oblige à numéroter ou pas, les 1;
ou du moins, compter sa position. Si par exemple il est à la position 1501: 1501*6 + 7 = 9 013 = P..

plg

Invité

Re : Répartition des nombres premiers et multiple de 5

j'ai un ami prof d'informatique à l'iut, qui doit faire le programme en utilisant la conjecture de Goldbach :

la décomposition de 30k, et vérifier les 8 premiers [7;31] afin de tester si il sont congrus à 30k modulo P^i,j; pour P_i,j inférieur à la racine carrée de 30k.
Et pareil, on travaille avec les P_i,j > 5 . Puisque 30k est congru à 0 modulo 2; 3; ou 5. aucun nombre premiers > 5 est donc congrus à 0 modulo 2 ; 3 ou 5...

lorsqu'il serra fait, je te dirai quelle limite on obtient.. et si tu le veux je l'enverrai...

c'est une équipe qui a déjà travaillée sur cette conjecture, et sur la programmation de la décomposition d'un entier 2n en somme de deux premiers (p+q)
ils ont été surpris de l'algorithme et de n'utiliser que ces 8 premiers pour cribler la totalité des entiers premiers , c'est une variante à Eratosthène...
mais c'est la même méthode et principe....

@+

Géomètre

Invité

Re : Répartition des nombres premiers et multiple de 5

Re
la commodité, comme la probabilité, ne sont pas des  rigueurs mathématique
les mathématique demande de la précision
pas du peut-être , du à peu près, ou je change une véracité mathématique, pour rendre juste,une affirmation fausse
juste par commodité
Vous qui aimez les preuves irréfutables devez être d'accord avec cette définition.

les probabilités pas une branche des mathématiques ???? Tu aurais fait des maths au lycée tu saurais que les probas font partie des mathématiques, au même titre que la topologie, l'algèbre ou l'analyse.

Mais tu ne voudrais pas au moins apprendre le vocabulaire des mathématiques ? Car tout ce que tu racontes est incompréhensible : "coordonnées géographiques d'un nombre" ? Sans compter que tu ne comprend pas lorsque les gens te répondent. Plutôt que de t'obstiner à croire que tu as découvert une "théorie" (encore un mot que tu emploies mal) Ne voudrais tu pas investir ton temps à apprendre les maths ? Tout le temps que tu as passé sur ton site à produire des graphiques et des illustrations qui n'ont de sens que pour toi aurait pu être employé à ouvrir un livre de maths et à faire des exercices.

Ta passion est émouvante mais la motivation ne peut pas compenser le manque de compétence. Aussi, soit moins dogmatique, le dogmatisme est l'ennemi fondamental des mathématiques. Commence peut être par apprendre ce qu'est une suite, comment formaliser tout ça. Parce que "la ligne 1+4+2" ça ne veut rien dire. Et que tu le veuilles ou non tu te réfères à la suite 6k-1/+1. Le fait que tu ne le comprennes pas, malgré le fait qu'on te l'ait expliqué une douzaine de fois prouve que tu as encore de grandes lacunes en mathématiques. Tu peux les compenser, nous avons tous été ignorants un jour, mais pour commencer il faut que tu admettes que tu puisses ne pas toujours avoir raison.

"j'ai pas l'habitude avec les lettre de l'alphabet". Au mois, tu aura eu le mérite de me faire rire.

Félicitations à Yoshi pour s'être montré aussi patient et pédagogique, en vain.

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Répartition des nombres premiers et multiple de 5

Salut à tous,

Ce qui suit s' adresse à tous, mais plus spécialement à Yoshi et Géomètre.

Moi, au moins, j'ai un mérite, c'est de savoir que je ne comprends rien à vos mathématiques. Non pas que je n'en ai pas fait un peu : j'ai terminé en Math.Elem. ( et croyez-moi ou pas, brillamment). Mais c'était en 1943, à une époque où on ne distribuait pas le bac et les mentions comme des petits pains, histoire d'avoir une statistique qui dame le pion à la région voisine.

Or, il y a une chose que vous autres, les matheux du XXI e siècle, refusez de comprendre et d'admettre, c'est que les maths d'aujourd'hui ont évolué dans certains concepts et dans leur expression de telle sorte qu'un matheux de la première moitié du XX e siècle ne peut plus vous suivre.

Je sais : vous allez penser : il est convaincu que les choses ont changé, mais en réalité, c'est lui qui a changé : il sucre les fraises et ses neurones sont racornis.

Tout ce préambule pour vous faire saisir que je ne pouvais pas suivre cette discussion sur un sujet qui pourtant me passionne depuis des années et des années : les nombres premiers.

Je hais les nombres premiers (je me répète, mais rassurez-vous : j'en suis conscient), parce qu'ils sont une offense à tout ce qui fait l'immense prestige des maths : la logique dans sa pureté la plus absolue. On n'arrive pas à leur imposer une règle, à les enfermer dans une loi, pas même dans une conjecture. Ce sont les anarchistes des mathématiques. Et pourtant, il doit y en avoir une, de loi, on la cherche depuis des siècles, et peut-être (je n'ose pas dire sans doute) qu'elle est très simple (après tout, la formule qui fait la gloire d' Einstein tient dans cinq caractères).

Alors, ce que je voudrais que vous me disiez, sans blabla et surtout sans formules ésotériques :

Est-ce que cette interminable discussion a fait faire un pas, même petit, dans la bonne direction ?