Inscription / Connexion Nouveau Sujet
Idee : Inversion du crible d`Eratosthene
Bonjour,
Quand on utilise en general le crible d`Eratosthene on commence par eliminer les multiples de 2 ensuite de 3, de 5, de 7 etc...
Mon idee est d`inverser cet ordre, on commence par eliminer les multiples de 7, ensuite sur les nombres restants les multiples de 5, toujours les nombres restants on elimine les multiples de 3 et il nous reste a la fin que les multiples de 2.
L`avantage est que tous les nombres composes de 4 a 120 ne sont cites qu`une fois chacun.
On obtient la repartition suivante.
Composes multiples de 7 : 14,21,28,35,42,49,56,63,70,77,84,91,98,105,112,119
Composes multiples de 5 : 10,15,20,25,30,40,45,50,55,60,65,75,80,85,90,95,100,110,115,120
Comopses multiples de 3 : 9,12,18,24,27,33,36,39,48,51,54,57,66,69,72,78,81,87,93,96,99,102,108,111,114,117
Composes multiples de 2 : 4,8,16,22,26,32,34,38,44,46,52,58,62,64,68,74,76,82,86,88,92,94,104,106,116,118
L`algorithme prend certes plus de temps que le classique crible d`Eratosthene mais la n`est pas l`objectif recherche.
Le but est d`avoir une distribution entre multiples des nombres premiers aussi "egalitaire" que possible.
Dans mon exemple, j`ai choisi les 4 premiers nombres premiers 2,3,5,7. Comme tous les nombres de 2 a 120 (11^2-1) sont forcement premiers ou divisibles par l`un de 4 premiers nombres premiers (2,3,5,7) on obtient une liste de tous les nombres composes de 2 a 120. Je ne tiens compte du nombre 1 pour des raisons evidentes.
Je ne sais pas ce que cela donnerait comme repartition des nombres composes si le meme algorithme est applique aux 10.000 nombres premiers (de 2 a 104729) sur une liste de nombres composes allant de 4 a 10971096048 (104743^2-1). Le nombre 104743 est le nombre premier qui suit 104729.
Si la repartition tend a devenir egalitaire quand n devient grand on obtiendrait un resultat tres interessant.
je ne suis pas programmeur mais sur un tableur je peux avoir une distribution des nombres composes pour les 1000 premiers nombres premiers (de 2 a 7919).
Ce serait fastidieux et ce n`est pas suffisant pour se faire une idee plus precise.
Viendrait alors une fois les resultats obtenus la tentative de preuve (obtention de formules approchees ou explicites).
Merci pour tout commentaire.
Ps : j`ai commence a travailler sur les 25 premiers nombres premiers et je commence a avoir des doutes sur le fait que la repartition devienne egalitaire quand n va vers l`infini.
Bonjour,
Il y a quelques années jamo un animateur de l'île nous avait donné
la liste des premiers <1000 000.
Amateur de tableur j'ai utilisé les 250 colonnes pour créer des suivants.
Pour les besoins d'une autre énigme je suis arrivé à 2605 613 par exemple,
par tranche successive je peux continuer...mais il existe des sites de test.
A noter que la rareté fait l'objet de recherches multiples dont Mersenne,
Hadamard, La Vallée-Poussin, Riemann et autres Weierstrass.
Salut,
Merci pour le commentaire.
Le but ici n`est pas de compter les nombres premiers mais de calculer la distribution des nombres composes par nombre premier en suivant mon algorithme.
Finalement je pense avoir resolu le probleme : on peut obtenir une repartition egalitaire moyennant certaines astuces.
Je suis en train de tester.
salut
bof bof ...
si on recherche les premiers on considère uniquement les nombres de la forme non multiples de 5 .... ce qui élimine d'office les multiples de 2, de 3 ... et de 5 !!
Bonsoir,
Je pense qu`il y a un malentendu ici.
Je ne recherche pas les nombres premiers. Le but est de repartir les nombres composes parmi les premiers qui les divisent.
C`est un crible inverse qui vise un autre but.
Faut me relire de bout en bout, me poser des questions et la je suis disponible.
Je le repete car j`ai l`impression que le message ne pas pas.
Le but premier de l`algorithme ce sont les nombres composes et leur repartition et non les nombres premiers.
Bonjour,
J'ai utilisé mon tableur pour voir les composés jusqu'à 65000 et
on constate que le maximum de composition (avec un premier) est de 6.
le plus petit est 30030 qui est composable avec 2,3,5,7,11 et13 .
Cette remarque te sera peut-être utile.
Suite,
J'ai regardé ce qui se passe en observant les 1000 décomposables en débutant par 31
Il semble que la répartition soit équilibrée on élimine par exemple 899 qui serait
resté avec 29 .
Je reste à l'écoute
Merci pour les reponses mais j`ai la nette impression que j`ai mal formule mon probleme d`ou le malentendu.
Cela dit, je continue mon chemin car je viens de faire des decouvertes interessantes en travaillant sur les 10200 premiers entiers naturels et en utilisant les 25 premiers nombres premiers.
Meme si personne n`a compris ce que j`ai voulu faire, je pense avoir resolu un probleme de taille. je sais qu`en arithmetique les nombres premiers et les nombres composes peuvent reserver des surprises et que la tendance a la projection pour les nombres suivants peut faillir.
Sans entrer dans le detail, je peux annoncer les choses suivantes :
1. On peut mettre a la poubelle le crible d`Eratosthene. Il serait remplace par un algorithme plus simple.
2. En connaissant les nombres premiers de 2 a p on peut connaitre par simple calcul le nombre exact de nombres premiers compris entre p et p^2
3. Cela fonctionne de la facon suivante : a chacun des nombres premiers < p est associe une valeur calculee v(p). En faisant la somme des v(p) on obtient le nombre de nombres composes et indirectement le nombre de premiers.
4. Ce ne sont pas des approximations. On obtient la valeur exacte de la fonction de comptage des premiers pi(n).
Comme on n`a jamais rien sans rien. Un travail preliminaire est necessaire pour calculer v(p) mais une fois v(p) calcule la valeur est definitive.
A p=7 est associee la valeur v(7) qui reste eternellement inchangee
On aurait un algorithme ou on entre les nombres premiers 2,3,5,7,1,.....,p (le p desire), on somme les v(p) et par magie on obtient apres des calculs simples pi(p^2) qui represente le nombre EXACT de premiers < a p^2.
Des que j`aurai fini mon travail, je presenterai une illustration pour p=97 et p^2=9409. En pratique j`irai au dela (10200=(101^2)-1.
Je le fais sur Excel.
A bientot.
Bonjour,
>derny
Bonne observation:
J'ai respecté la méthode de Goudda .
Dès qu'un composé rencontre son premier premier diviseur il sort de la liste,
j'ai appliqué la formule pour les colonnes successives d'où ton observation,
mais j'aurais du l'appliquer à toute la ligne exemple 868.
J'ai donc rectifié.
J'ai un tableur qui donne le crible avec 1597 --->2 comme premier
et 2 à 72700 comme composé.
Je pense être à coté de la plaque mais nous attendons le travail de Goudda
qui a le mérite de cette démarche.
Merci.
Le tableau poste correspond exactement au profil recherche (1 diviseur par ligne).
Cretains nombres meme divisible par 3 premiers par exemple ne doivent figurer que sur une colonne en fonction de leur hierarchie. Si un nombre est divisible 31 (le plus grand premier il est d`emblee exclu de figurer sur les autres colonnes. 62 figurera dans la colonne 31.
Les puissances de nombres premiers (2^2,2^3,... ou 3^2,3^3....) je les ai elimines en mme temps que les nombres pairs cela reduit la dispersion. En fin de compte, j`ai fini par trouver une autre methode.
Suite
Cela m'a permis de trouver la bonne formule pour le choix unique du premier diviseur...
Bonne continuation.
Desole pour mon commentaire precedent j`avaais vu juste les premieres pas le reste.
Il faut un seul 1 par ligne sinon on ne retrouve pas la somme des nombres composes.
Un nombre compose ne figure qu`une SEULE fois associe a l`un de ses facteurs premiers.
Oui,
Une fois établi le tableau des divisions entières, notées 1 dans C3 par exemple ;
il suffit de faire un clone avec la formule:
=si(somme($C3.C3)>=1;"";D3)
Pour info voici la courbe des premiers diviseurs des composés (72361)
avec premiers de 2 à 269 .
Si cela peut servir...
Annuler
connectez vous