énumération des premiers

[akntn]

Bonjour,

Existe-t-il aujourd'hui un algo simple (manipulable par des écoliers) capable d'énumérer tous les premiers :

1) Sans barrer les multiples
2) sans faire de divisions

Merci.
-----

[inviteaf1870ed]

message annulé

[phys4]

Bonjour akntn,

C'est une question très intéressante, recherchée par de nombreux mathématiciens depuis des siècles.
Si tu trouves une solution simple, surtout fais en un bel article.
Au plaisir.

[akntn]

Bonjour,

Je tiens cette solution. Elle produit ce que j 'appelle une "raison première" pour tous les entiers, elle ne produit pas seulement les premiers (c'est à dire qu'il y a une raison première pour 1, pour 2, pour 3, etc.). Mais qui peut s'intéresser à cela dans un monde de performances technologiques et mathématiques ? Ce qui intéresse les mathématiciens auj, ce sont les très très grands nombres premiers. Or, ma méthode, bien que pouvant énumérer simplement TOUS les premiers, ne permet pas d'obtenir les très grands nombres premiers, qui ne peuvent être atteints directement (de façon discontinue).
Au fond, c'est comme les entiers : on ne peut les énumérer à l'infini, il y en a trop.
Qu'en pensez-vous ?

[A voir en vidéo sur Futura]

[inviteaf1870ed]

Tu es un ami de WizartS ? Vous semblez travailler sur des sujets voisins

[erik]

Qu'en pensez-vous ?

J'en pense que tu dits avoir une "méthode", sans rien dire de cette méthode.
A part ça qu'est ce que tu veux qu'on en pense .

[akntn]

Bonjour,

Je comprends que le fait d'annoncer qu'on détient la solution d'un problème sans la dévoiler puisse agacer.
Cependant, n'étant ni Poincaré, ni Cantor, ni Einstein, je ne serai pas imprudent au point de divulguer un algo de construction des premiers, tel quel, sur un forum, aussi renommé soit-il : je ne serais pas pris au sérieux !
Aussi, voici mon algo sous forme d'énigme.

ALGO DE AKNTN

A0A0AB1B1BC2C2CD3D3DE4E4EF5F5F ...

A, B, C, D, E, F... : à l'infini.

Cet algo donne une raison première pour A, B, C, D, E, F... Je rappelle qu'il ne peut énumérer les premiers de façon discontinue, car, pour connaître A, il faut connaître B, C, D, E, F..., pour connaître B, il faut connaître C, D, E, F...

Bon déchiffrage !

[invite4ef352d8]

Pour lister les nombres premier inférieur à n entier fixé, il n'y à a priori rien de plus efficace (algorithmiquement parlant) que le crible d'Erathostène et ces raffinements (crible d'atkin etc...).

apres ci ce genre de choses t'amuse, il ya des formule (qui s'écrive uniquement avec des symbole usuelle, signe sigma et partie entière) qui donne le n-iemme nombre premier en fonction de n... mais elle n'ont que peu d'interet : en pratique tu fera beaucoup plus de calcule en utilisant ces formules quand testant tous les nombres premier à la main...

[invite4ef352d8]

akntn : si je peux de donner un conseil, demande toi si ta methode est vraiment plus efficace que ce qui existe déja en la matière. si ce n'est pas le cas, ca ne sert à rien de faire autant de secret autour...

[akntn]

Bonjour Ksilver,

Excuse-moi, mais je pense que tu n'as pas bien capté le problème de cette discussion. Reporte-toi à mon premier message.

[Médiat]

Cependant, n'étant ni Poincaré, ni Cantor, ni Einstein, je ne serai pas imprudent au point de divulguer un algo de construction des premiers, tel quel, sur un forum, aussi renommé soit-il : je ne serais pas pris au sérieux !

Cela me rappelle quelque chose ... mais quoi ? Ah oui :

http://forums.futura-sciences.com/ma...ml#post2309016

[akntn]

Médiat, rien à voir. Je n'affirme rien, mon algo est sans intérêt du point de vue de la performance technologique (je l'ai dit). Pour trouver des premiers en masse, il vaut mieux passer par le test de Miller-Rabin. Seulement, cet algo propose une solution à la question posée au début :

Existe-t-il un algo produisant tous les premiers sans :

1) Barrer tous les multiples
2) Faire des divisions

En connais-tu un ?

[Médiat]

Je comprends que le fait d'annoncer qu'on détient la solution d'un problème sans la dévoiler puisse agacer.

Médiat, rien à voir.

Je vois que tu prétends en avoir un, mais que tu ne veux pas le révéler, donc le rapport est évident, il faut être aveugle pour ne pas le voir.

[akntn]

Je ne peux le révéler directement. Mets-toi à ma place. Cette solution est tellement enfantine qu'elle serait immédiatement tournée en dérision (à moins d'être un mathématicien reconnu).
J'en ai donné suffisamment sur le forum pour qu'elle puisse être déchiffrée, moyennant quelques échanges neuronaux.

Cordialement, akntn

[Médiat]

Je ne peux le révéler directement. Mets-toi à ma place. Cette solution est tellement enfantine qu'elle serait immédiatement tournée en dérision (à moins d'être un mathématicien reconnu).

J'ignorais que la validité d'un résultat mathématique dépendait de celui qui l'énonce ; au pire cela à un impact sur les vérifications que l'on a envie de mener.

[invite88ef51f0]

Bonjour,
Que les choses soient claires : soit vous avez quelque chose à dire et vous le dites, soit vous ne voulez rien dire et alors vos messages sont inutiles. Les comportements paranoïaques du type "j'ai une super méthode, mais si je le dis vous allez me le piquer" n'ont aucun intérêt.
Afin de ne pas traîner plusieurs pages à brasser du vent je vous demanderai donc de ne poster que si vous avez quelque chose à dire.

Pour la modération, Coincoin.

[WizartS]

Médiat, rien à voir. Je n'affirme rien, mon algo est sans intérêt du point de vue de la performance technologique (je l'ai dit). Pour trouver des premiers en masse, il vaut mieux passer par le test de Miller-Rabin. Seulement, cet algo propose une solution à la question posée au début :

Existe-t-il un algo produisant tous les premiers sans :

1) Barrer tous les multiples
2) Faire des divisions

Dommage, ça aurait pû être intéressant! Je pense même que n'importe quel travail est intéressant pourvu qu'il soit cohérent.

D'un point de vue logique, je ne comprends pas pourquoi tu te manifestes avec la ferme intention de ne rien dévoiler (au passage pour Médiat, ce qui n'était pas mon cas, c'était simplement une question de temps mal estimé de ma part, je reconnais).

En effet, nous avons ici quelqu'un qui prétend détenir la solution. Cette personne vient nous le dire ouvertement. Mais ce que cette personne dit aussi, c'est qu'elle ne nous dira rien.

Si effectivement, nous ne pouvons rien apprendre d'une telle personne, c'est que ces messages sont manifestement vides de sens. Et donc la discussion n'a plus d'intérêt à partir du moment où nous en prenons conscience. Et donc mon message fini lui aussi par devenir inutile...

Dommage : akntn, tu vois, tu trouverais ici même une audience qui s'intéresse à ton propos, si seulement tu nous proposais ta solution.

(- PS : avant de poster mes travaux mathématiques, comprenant entre autre ma formule de factorisation d'un nombre entier >=2, j'ai protéger par enveloppe soleau pour me garantir les droits d'auteur. Exemple ma discussion est ici :
http://forums.futura-sciences.com/ma...entier-11.html

- PS 2 : Les mathématiques pures sont tout aussi intéressantes que les mathématiques appliquées)

[Médiat]

(au passage pour Médiat, ce qui n'était pas mon cas, c'était simplement une question de temps mal estimé de ma part, je reconnais).

C'est exactement le sens du post que j'ai mis en référence : dire que tu ne faisais pas partie de cette bande-là, puisque tu annonçais ta volonté de poster tes résultats.

[invite8915d466]

Bonjour,

Je tiens cette solution. Elle produit ce que j 'appelle une "raison première" pour tous les entiers, elle ne produit pas seulement les premiers (c'est à dire qu'il y a une raison première pour 1, pour 2, pour 3, etc.). ...
Au fond, c'est comme les entiers : on ne peut les énumérer à l'infini, il y en a trop.
Qu'en pensez-vous ?

euh, sauf erreur, pour produire tous les premiers dans l'ordre, mais pas seulement les premiers, le plus simple justement, c'est d'énumérer tous les entiers dans l'ordre non ? .

[akntn]

Bon. Voici mon algo :

Il s'agit de construire l'ensemble des diviseurs primals de N (un diviseur "primal" est un entier d divisant un et un seul n tel que n/d donne toujours un premier si n est supérieur à d^3).
En fait cela revient à construire tous les cycles n selon deux principes :

1) La hiérarchie
2) Le déplacement

La résultante est la "raison première" pour tout entier.

Soit la suite N des entiers.
On place d'abord les "1". On s'arrête au carré de 2 (4).

1 2 3 4
1 1 1 2

On place ensuite les "2" jusqu'au carré suivant (9). On complète avec les "1".

1 2 3 4 5 6 7 8 9
1 1 1 2 1 2 1 2 3

On place ensuite les "3" jusqu'au carré suivant (16). On complète avec les "2" et les "1".

1/1
2/1
3/1
4/2
5/1
6/2
7/1
8/2
9/3
10/2
11/1
12/3
13/1
14/2
15/3
16/4

Par exemple, on voit que "2" ne peut pas se placer en "12" puisque cette place est prise par "3". Il se place donc en "14".

On place ensuite les "4" jusqu'au carré suivant (25). On complète avec les "3", les "2" et les "1".

1/1
1/2
1/3
2/4
1/5
2/6
1/7
2/8
3/9
2/10
1/11
3/12
2/14
3/15
4/16
1/17
3/18
1/19
4/20
3/21
2/22
1/23
4/24
5/25

Etc. jusqu'à "l'infini". Comme je l'ai dit, impossible d'obtenir de très grands nombres premiers car TOUS les cycles sont nécessaires, du plus GRAND au plus PETIT.
Ce qui est "remarquable" ici, c'est de constater que tous les diviseurs se placent en fonction des écarts premiers multipliés par n. Jusqu'à n < d ^ 3, tous les diviseurs sont "triviaux". Ils deviennent "non triviaux" au-delà de d^3, c'est à dire qu'ils donnent toujours un premier.
Somme toute, une affaire de "saute-mouton" jusqu'à l'infini. J'avais prévenu : c'est enfantin.

[Médiat]

Existe-t-il aujourd'hui un algo simple (manipulable par des écoliers) capable d'énumérer tous les premiers :

1) Sans barrer les multiples
2) sans faire de divisions

On place ensuite les "3" jusqu'au carré suivant (16). On complète avec les "2" et les "1".

Autrement dit ton algorithme consiste à faire des divisions ou à barrer les multiples (en écrivant un diviseur), il ne respecte donc pas les deux contraintes que tu as, toi-même, donnée.

[WizartS]

C'est exactement le sens du post que j'ai mis en référence : dire que tu ne faisais pas partie de cette bande-là, puisque tu annonçais ta volonté de poster tes résultats.

Y'a aucun malentendu là-dessus, merci!

En tout cas, merci à akntn de nous avoir fais confiance en nous postant sa méthode! Lorsqu'on affirme quelquechose, il devient nécessaire de le montrer.

[leg]

bonjour
en cherchant un peu sur le forum AKNTN,
tu aurais trouvé l'algorithme P[30] qui me semble l'égèrement plus rapide et plus simple que ta méthode ... et qui à l'avantage d'extraire les premiers par Famille ce qui donne une idée sur leur réparatition et ce en ne connaissant que les 8 premiers >5 et <=31 . mais surtout sans s'encombrer de tous tes nombres pair, multiple de 3 ou 5, qui sont tellement nombreux; et comme le dit MEDIAT,tu divises N par N, et tu ne va pas aller bien loin avant de saturer ta mémoire......

[phys4]

Bonjour,

Désolé d’enlever l’antériorité que croyait avoir « aktnt ». La réduction de temps de calcul par l’utilisation de boucles sur un multiple est programmée depuis longtemps.
L’on peut soit utiliser une boucle sur les dizaines, dans laquelle sont utilisés seulement les nombres finissant par 1, 3, 7, 9 ce qui divise le temps d’algo par 2.5
J’ai également utilisé la boucle sur 30 qui permet de gagner un rapport 3.75
Ces algos sont triviaux et bien connus.
La question était la recherche des premiers et non la réduction du temps de calcul, ce qui n’est pas la même chose.

[leg]

la recherche ("du nombre") de tous les premier et la réduction du temps de calcul va de paire il me semble et il aurait pu commencer par ça:
Il aurait été plus simple de s’inspirer du crible d’Eratosthène, en travaillent modulo 9 exemple :
9 colonnes et n lignes (« n tend vers l’infini ») la première ligne se numérote à partir de la deuxième.

0 = 1 . 2. 3. 4. 5. 6. 7. 8. 9
1 = 1. 0. 1. 0. 1. 1. 1. 0. 1
2= 0. 1. 1. 1. 0. 1. 1. 1. 1
n+1. 1. 0. 1. 0. 1. 1. 1. 1. 1
" . 0. 0. 0. 0. 0. 0. 0. 0. 0
" . 0. 0. 0. 0. 0. 0. 0. 0. 0
" . 0. 0. 0. 0. 0. 0. 0. 0. 0
" . 0. 0. 0. 0. 0. 0. 0. 0. 0
" . 0. 0. 0. 0. 0. 0. 0. 0. 0
" . 0. 0. 0. 0. 0. 0. 0. 0. 0
" . 0. 0. 0. 0. 0. 0. 0. 0. 0
…etc…etc

Puis tu remplaces les 0 par 1 tous les P.0 (P = premier); ce qui donne déjà pour tous les 2n, un 1. et toutes les lignes colonne 3, 6 et 9 , puis tous les 5 zéros…etc 5…11..etc.. P
Tu n’as donc pas besoins de diviser le prochain zéro puisqu’il est premier d’office, sinon ce serait un 1, il aurait été factorisé par un Premier < P est marqué d’un 1.
Pour connaître la valeur de 0 = P, tu connais la suite .. (n * k9) + X. (« X de 2 à 9 ») .

il n'y-à pas de division, pas de croix et même pas de chiffres > 9 ;
et tu peux faire la même chose P[30], comme ça tu supprimes tous les 2n, m3 et m5 il te reste 26.66% des entiers naturels congrus P[30] , pour P de 7 à 31. donc 8 colonnes .

[akntn]

Bonjour,

Le but du jeu n'est pas de trouver des premiers, mais d'observer comment ils se forment. Moi-même, pour en trouver facilement jusqu'à 100 chiffres de long, j'utilise le test de Miller-Rabin, bien plus efficace que le crible d'Eratosthène (limité à 12 chiffres).
Désolé, je ne "barre" pas les multiples. Pour moi, il n'y a pas, d'un côté, les "multiples", et de l'autre, les "premiers". Il y a seulement les entiers rangés en fonction de la raison première : P x 1, P x 2, P x 3, P x 4 ... C'est cela qui est "différent" dans cet algo. TOUS les
nombres sont ici nécessaires. Il n'y a pas de déchets (les multiples). Mais peut-être n'est ce pas évident à première vue.

Je reformule (pour ceux que la théorie intéresse) mon théorème :

Pour chaque entier n, il existe un et un seul diviseur d tel que n/d donne un premier si n est supérieur à d au cube.

D'où : l'ensemble des diviseurs "primals".

De rien, Wizarts.

[leg]

Bonjour,

Le but du jeu n'est pas de trouver des premiers, .

je pensais que le but du jeu c'était ta question:

Existe-t-il aujourd'hui un algo simple (manipulable par des écoliers) capable d'énumérer tous les premiers :

1) Sans barrer les multiples
2) sans faire de divisions.

Mais je vois que les toutes les règles ont changé

de plus je pense qu'il y a une certaine différence entre le test de Miller-Rabin pour savoir si un nombre est premier, et l'algorithme d'Eratosthène, qui n'a pas pour but de tester les nombres P , mais de les énumérer façon crible...Ce que tu fais d'ailleurs ....mais comme tu as besoin de tous les entiers pour faire fonctionner ton crible alors bon courage...

[invite5f67e63a]

Je reformule (pour ceux que la théorie intéresse) mon théorème :

Pour chaque entier n, il existe un et un seul diviseur d tel que n/d donne un premier si n est supérieur à d au cube.

Alors là j'ai rien compris à ce théorème....il faudrait le formuler de manière plus précise...est ce que c'est pour tout il n il existe un unique diviseur d de n, plus petit que n^{1/3}, tel n/d est premier.
Ca c'est juste faux....regarde 4....


D'un point de vue logique ton truc est douteux...tu te fixe un n puis tu dis qu'il existe un unique d tel que, et ensuite y a un "si"...

[WizartS]

Alors là j'ai rien compris à ce théorème....il faudrait le formuler de manière plus précise...est ce que c'est pour tout il n il existe un unique diviseur d de n, plus petit que n^{1/3}, tel n/d est premier.
Ca c'est juste faux....regarde 4....

D'un point de vue logique ton truc est douteux...tu te fixe un n puis tu dis qu'il existe un unique d tel que, et ensuite y a un "si"...

Il faudrait demander à Akntn qu'il détail sa démarche depuis le début jusqu'à la "fin" (qu'il s'est fixée). C'est-à-dire d'exposer le raisonnement entier, pas à pas, puis de nous donner les exceptions (si elles existent).

Mais je vois que les toutes les règles ont changé

Pour ma part, je pense qu'il ne faut pas se fixer de règles (ou de limites) qui pourraient barrer notre route vers la compréhension des nombres premiers en général.

[akntn]

Bonjour Leg,

Il me semble, en ce qui concerne "barrer les multiples" avoir répondu à ta question. Peux-tu faire un petit effort de compréhension ?
Pour ce qui est de "faire des divisions", je parlais de tests, non de placer des nombres dans une suite.
En ce sens donc, mon algo ne barre aucun multiple (puisqu'il ne différencie pas les "premiers" et les "multiples") et il n'oblige pas à tester chaque entier avec une calculette. Et un écolier peut l'utiliser sans problème.
Maintenant, je n'ai jamais dit qu'il était efficace pour trouver rapidement des NP. Son intérêt est surtout théorique, car il permet de construire rationnellement l'ensemble des diviseurs primals, qui est l'ensemble de tous les cycles rangés selon la raison première (les "1", les "2", les "3", les "4" ...). En d'autres termes, on peut dire que tous les entiers sont des "multiples" rangés selon la raison première, pas seulement les "premiers".
Ex :
Entiers multiples de 1 : 1,2,3,5,7,11,13,17,19,23,29...
Entiers multiples de 2 : 4,6,8,10,14,22,26,34,38,46,58. ..
Entiers multiples de 3 : 9,12,15,18,21,27,33,39,51,57,6 9,87...

Est-ce seulement trivial ? Ce serait dommage.