la suite des nombres premiers est-elle logique ou aléatoire ?

[andretou]

Bonjour à tous
En principe, dans une suite "logique" contenant une infinité de termes, on peut déterminer (voire deviner) chaque terme en fonction du ou des termes qui précèdent, comme par exemple avec :
- les suites arithmétiques et/ou géométriques,
- la suite de Fibonacci,
- la suite de Syracuse,
- la suite de Conway,
- la suite des décimales d'un nombre rationnel,
- etc...

Or, ce n'est pas le cas avec la suite des nombres premiers, dans laquelle il n'est pas possible (en tous cas à ce jour) de déterminer le n-ième terme à l'aide des termes qui précèdent (idem avec la suite des décimales du nombre , comme avec la suite des décimales de tout nombre irrationnel).

Selon vous, puisqu'il n'est pas possible de déterminer le n-ième terme à partir des termes qui précèdent, peut-on affirmer que la suite des nombres premiers est aléatoire, qu'elle n'obéit à aucune logique apparente ?
Dans le cas contraire, si l'on déclare que la suite des nombres premiers n'est PAS ALEATOIRE, comment alors justifier que l'on ne puisse pas déterminer le n-ième terme à partir des termes précédents, et à partir d'eux seulement ?

Merci pour vos réponses et vos commentaires
-----

[anthony_unac]

Bonsoir,

Il existe au moins un algorithme qui permette de trouver le nième nombre premier à partir des précédents et il existe également des résultats permettant d'affirmer qu'un nombre premier donné se situe dans un intervalle donné.
Il existe également des relations plus ou moins sophistiquées (qui reposent sur le théorème de Wilson) donnant tous les nombres premiers mais qui sont inutilisables dans la pratique.
Bref, déterminer un "grand" nombre premier reste encore aujourd'hui extrêmement compliqué et les nombres premiers records sont souvent de la forme car ils possèdent des propriétés particulières mais pour le reste ...

[andretou]

Il existe au moins un algorithme qui permette de trouver le nième nombre premier à partir des précédents

Merci !
Aurais-tu éventuellement un lien vers cet algorithme ?

[anthony_unac]

bonjour,
voici un lien avec une petite animation pour bien comprendre le mécanisme
http://therese.eveilleau.pagesperso-.../crible_an.htm

[A voir en vidéo sur Futura]

[Médiat]

Bonjour,

Une formule très simple qui donne tous les premiers :

[andretou]

Je ne comprends pas comment fonctionne cette formule étrange qui n'a pas de comparateur. Comment passe-t-on d'une fraction à la suivante ? Il manque des premiers (3, 5...) et apparemment elle utilise abondamment d'autres nombres que les premiers (78, 85, 51, 38, 33, etc...).

[Médiat]

C'est du FRACTRAN : http://www.olympiad.org.uk/papers/20...l/fractran.pdf

[Deedee81]

Salut,

Ah tiens, sympa ça. Je ne connaissais pas.

Voir aussi :
https://fr.wikipedia.org/wiki/FRACTRAN

Et en particulier
https://fr.wikipedia.org/wiki/FRACTR...mbres_premiers

[andretou]

bonjour,
voici un lien avec une petite animation pour bien comprendre le mécanisme
http://therese.eveilleau.pagesperso-.../crible_an.htm

Apparemment ce lien renvoie vers le crible d'Eratosthène, qui permet de dresser la liste des premiers par élimination des nombres non-premiers (principe sur lequel repose aussi le théorème de Wilson).
Mais pourrais-tu stp me communiquer le lien vers cet algorithme que tu as mentionné et qui permettrait de trouver le n-ième nombre premier à partir des seuls nombres premiers précédents ?

[Deedee81]

Mais pourrais-tu stp me communiquer le lien vers cet algorithme que tu as mentionné et qui permettrait de trouver le n-ième nombre premier à partir des seuls nombres premiers précédents ?

L'algorithme le plus simple est aussi l'algorithme proche du crible d'Eratosthène.

Suppose que tu as tous les nombres premiers jusque N. A partir de là, tu incrémentes (par 2 pour être plus efficace). Tu vérifie s'il est divisible par les nombres premiers compris entre 2 et N inclus (mais plus petit ou égal à la racine carrée du nombre considéré). S'il n'y en a pas, ok, tu as trouvé, sinon tu incrémente de 2 et tu recommences.

[andretou]

L'algorithme le plus simple est aussi l'algorithme proche du crible d'Eratosthène.

Suppose que tu as tous les nombres premiers jusque N. A partir de là, tu incrémentes (par 2 pour être plus efficace). Tu vérifie s'il est divisible par les nombres premiers compris entre 2 et N inclus (mais plus petit ou égal à la racine carrée du nombre considéré). S'il n'y en a pas, ok, tu as trouvé, sinon tu incrémente de 2 et tu recommences.

ok. Mais, sauf erreur de ma part, tous les algorithmes connus (d'Eratosthène à Wilson, en passant par Conway, en effet remarquable) procèdent en testant la primalité de chaque entier, et en éliminant ceux pour lesquels un diviseur a été trouvé.
Apparemment il n'existe pas de formule permettant de calculer le n-ième premier uniquement à partir des premiers précédents, et à partir de ceux-ci seulement, comme dans une suite "logique".
C'est pourquoi je me demande si on doit mettre sur le même plan la suite des nombres premiers, et les autres suites "logiques"...

[Médiat]

La Formule de Minác et Willans est de la forme f(n) = ... et donne le n-ième nombre premier

[Deedee81]

Salut,

Apparemment il n'existe pas de formule permettant de calculer le n-ième premier uniquement à partir des premiers précédents, et à partir de ceux-ci seulement, comme dans une suite "logique".
C'est pourquoi je me demande si on doit mettre sur le même plan la suite des nombres premiers, et les autres suites "logiques"...

Une formule avec une boucle qui donne le nième en passant pas les composés précédents, est aussi une formule donnant le nième. Il y a toujours des calculs intermédiaires (à moins d'avoir une seule addition ).
Et il existe des formules plus directes, voir le message de Médiat ci-dessus, elles sont juste de performances épouvantablement mauvaises.

Mais peu importe les performances : ça existe.

Et donc, ça répond à la question : ce n'est pas aléatoire (au sens où tu l'as utilisé). Contrairement au décimales du nombre de Chaitin ou aux solutions de l'épouvantable équation Diophantienne (plusieurs pages !!!!) qu'il avait trouvé et dont les solutions sont équivalentes à un tirage à pile ou face.

[andretou]

La Formule de Minác et Willans est de la forme f(n) = ... et donne le n-ième nombre premier

Oui, en effet, elle donne le n-ième nombre premier, mais cependant pas à l'aide des premiers précédents (ce qui à mes yeux est une différence essentielle avec les suites "logiques").

[andretou]

Une formule avec une boucle qui donne le nième en passant pas les composés précédents, est aussi une formule donnant le nième. Il y a toujours des calculs intermédiaires (à moins d'avoir une seule addition ).
Et il existe des formules plus directes, voir le message de Médiat ci-dessus, elles sont juste de performances épouvantablement mauvaises.

Mais peu importe les performances : ça existe.

D'accord, mais quelle que soit la formule, les termes précédents ne sont pas nécessaires pour calculer le n-ième premier !

Et donc, ça répond à la question : ce n'est pas aléatoire (au sens où tu l'as utilisé). Contrairement au décimales du nombre de Chaitin ou aux solutions de l'épouvantable équation Diophantienne (plusieurs pages !!!!) qu'il avait trouvé et dont les solutions sont équivalentes à un tirage à pile ou face.

D'accord, la suite des nombres premiers n'est pas aléatoire. Pour autant, est-elle vraiment "logique" ? Selon toi, peut-on considérer que la logique dont elle procède est du même niveau que celle des suites "logiques" conventionnelles ?

[gg0]

Sérieusement, Andretou,

tu compliques ce qui est simple ! La suite 2,4,6,8 que je complètes par 10 utilise directement la formule 2n où n est le numéro du terme. C'est pour deviner une réponse possible qu'on a besoin des termes précédents. Pour la suite 2, 3, 5, 7, 11, 13, c'est bien en regardant ces termes que je vais avoir envie de rajouter 17, si j'ai pensé que ce sont des nombres premiers.
Pour savoir quel est le nombre premier suivant, il faut bien utiliser ceux qu'on a déjà !

Ou alors il va falloir définir ce que tu appelles une "suite logique", et lui donner un autre nom.

Cordialement.

[Deedee81]

Salut,

Ou alors il va falloir définir ce que tu appelles une "suite logique", et lui donner un autre nom.

Je suis d'accord car affirmer qu'une suite serait "illogique" serait, hein, hum

La seule chose intéressante soulevée jusqu'ici est que calculer la suite des nombres premiers est plus compliqué que calculer une suite arithmétique. Bon, ça nous mène où tout ça ???? Nul part

[Médiat]

Bonjour,

Et je rappelle que toute suite finie est "logique" dans le sens ou il existe une formule (comme le f(n) = 2n pour les nombres pairs) explicitant cette suite (et, encore plus fort, cette formule est la même pour toutes les suites, seuls deux paramètres permettent de déterminer de quelle suite il s'agit).

[Deedee81]

Salut,

et, encore plus fort, cette formule est la même pour toutes les suites, seuls deux paramètres permettent de déterminer de quelle suite il s'agit).

Là tu m'intrigues. Une explication ? Un cht'tit indice sur la manière de trouver une telle formule ?

[Médiat]

Salut,

Mèzalor, tu ne connais par cœur l'ensemble de mon œuvre

http://forums.futura-sciences.com/sc...-9-3-13-a.html

[Deedee81]

Mèzalor, tu ne connais par cœur l'ensemble de mon œuvre

Si mais j'avais déjà fait trois fois le tour de mon bocal
Non, je plaisante, je ne l'avais pas lu.

http://forums.futura-sciences.com/sc...-9-3-13-a.html

Vachement intéressant. Une toute petite formule et hop....

Merci,

[andretou]

Sérieusement, Andretou,

tu compliques ce qui est simple ! La suite 2,4,6,8 que je complètes par 10 utilise directement la formule 2n où n est le numéro du terme. C'est pour deviner une réponse possible qu'on a besoin des termes précédents. Pour la suite 2, 3, 5, 7, 11, 13, c'est bien en regardant ces termes que je vais avoir envie de rajouter 17, si j'ai pensé que ce sont des nombres premiers.
Pour savoir quel est le nombre premier suivant, il faut bien utiliser ceux qu'on a déjà !

Ou alors il va falloir définir ce que tu appelles une "suite logique", et lui donner un autre nom.

Cordialement.

Bonjour gg0 !
Dans ton exemple 2,4,6,8... les termes suivants de cette suite peuvent en effet se déduire (et se déduisent aisément) des termes précédents.
Je veux simplement dire que dans le cas de la suite des nombres premiers, il est rigoureusement impossible (en tous cas jusqu'à présent) de déduire les termes suivants uniquement à partir de 2,3,5,7,11,13..., ce qui confère à cette suite un caractère apparemment aléatoire (par définition, une suite aléatoire est une suite dont on ne peut prédire le terme suivant).
Comme tu l'as indiqué, on est ici obligé de constater qu'il s'agit de la suite des nombres premiers, puis, à partir de là, on emploie un algorithme qui va déterminer les termes suivants.
C'est pourquoi je me demande si on ne devrait pas faire une différence entre :
- d'une part les suites "logiques" dont il est possible de déduire le n-ième terme à partir des seuls termes précédents,
- et d'autre part les suites "semi-logiques" (ça fait classe, non !? ) pour lesquelles c'est impossible (l'impossibilité ne pouvant alors être levée qu'en disposant d'informations supplémentaires non contenues dans la suite elle-même, comme dans le cas de la suite des nombres premiers ou des décimales des nombres irrationnels)...
Mais bon, effectivement, une fois qu'on a dit ça, on n'est pas plus avancé !

ps : merci Médiat pour tes remarques et pour les informations partagées.

[gg0]

" il est rigoureusement impossible (en tous cas jusqu'à présent) de déduire les termes suivants uniquement à partir de 2,3,5,7,11,13." ??? Voyons donc, il suffit de tester les entiers suivant 13 pour savoir s'ils sont non divisibles par ceux-ci : pas 14, pas 15, pas 16, et on tombe sur 17, non divisible par les précédents, de même que 7 est le premier entier suivant 7 non divisible par 2, 3 ou 5.
Il vaut mieux ne pas affirmer des impossibilités aussi vagues. Tu as une idée à laquelle tu tiens, mais comme elle est floue, non mathématisée, tu t'exposes à réfutation systématique. tant que tu ne définis pas totalement ce qu'est une "suite logique" comme tu dis, tu te feras réfuter. Et si tu arrives à définir très précisément ce qu'est une suite logique, tu risques d'être déçu parce qu'il ne restera presque rien !

Cordialement.

NB : Pour le fun, connais-tu la suite logique n, x, s, e, q, x ? Peux-tu la compléter (autrement qu'en numérisant et utilisant la règle de Médiat, seulement par intuition ?

[andretou]

NB : Pour le fun, connais-tu la suite logique n, x, s, e, q, x ? Peux-tu la compléter (autrement qu'en numérisant et utilisant la règle de Médiat, seulement par intuition ?

Je ne la connais pas !
On doit la compléter par un seul terme, ou s'agit-il d'une suite infinie ?

ps : je note au passage que tu as employé le terme "suite logique", il faudra que tu m'en dises plus sur les suites "non logiques"...

[Médiat]

s'agit-il d'une suite infinie ?

Oui, mais elle a tendance à se répéter.

[andretou]

Pour le fun, connais-tu la suite logique n, x, s, e, q, x ? Peux-tu la compléter (autrement qu'en numérisant et utilisant la règle de Médiat, seulement par intuition ?

Est-ce que ça marche aussi avec les majuscules N, X, S, E, Q, X ?

[Deedee81]

Salut,

Dans ton exemple 2,4,6,8... les termes suivants de cette suite peuvent en effet se déduire (et se déduisent aisément) des termes précédents.
Je veux simplement dire que dans le cas de la suite des nombres premiers, il est rigoureusement impossible (en tous cas jusqu'à présent) de déduire les termes suivants uniquement à partir de 2,3,5,7,11,13..., ce qui
[...]

Dis-moi si je t'ai bien compris.

Tu veux dire qu'à partir de "2,3,5,7,11,13" et sans connaitre d'autres règles mathématiques sur les nombres premiers alors il est impossible d'en déduire que le suivant est 17.

C'est ça ?

Mais dans ce cas, ce que tu dis juste avant est faux.
A partir de "2,4,6,8" il t'est impossible de savoir la suite sans des règles définissant (par exemple) une suite arithmétique.
La suite ça pourrait être 2,4,6,8,23 ou 2,4,6,8,9898568 ou tout ce qu'on veut

La déduction de "10" comme suite de ces nombres n'est en rien logique, c'est seulement basé sur des préjugés. D'ailleurs pour moi, la suite la plus simple est 2,4,6,8,0,0,0,0,0,0,0,.... Et certainement pas 2,4,6,8,10. Qui a dit que ça devait être comme ça, hein ?

Au mieux tu pourrais définir une notion de complexité algorithmique, à la Kolmogorov. Alors la suite arithmétique est une des plus simples.

[gg0]

Est-ce que ça marche aussi avec les majuscules N, X, S, E, Q, X ?

A priori, non.
La suite est t, t, f, x ... et on l'utilise souvent

[andretou]

Salut,



Dis-moi si je t'ai bien compris.

Tu veux dire qu'à partir de "2,3,5,7,11,13" et sans connaitre d'autres règles mathématiques sur les nombres premiers alors il est impossible d'en déduire que le suivant est 17.

C'est ça ?

Oui. Plus précisément, à partir des n premiers termes de cette suite, il est impossible de déduire le n+1ème, et cela quel que soit n (sauf à supposer d'emblée la primalité des termes de la suite, ce que choisit de faire gg0).

Mais dans ce cas, ce que tu dis juste avant est faux.
A partir de "2,4,6,8" il t'est impossible de savoir la suite sans des règles définissant (par exemple) une suite arithmétique.
La suite ça pourrait être 2,4,6,8,23 ou 2,4,6,8,9898568 ou tout ce qu'on veut

La déduction de "10" comme suite de ces nombres n'est en rien logique, c'est seulement basé sur des préjugés. D'ailleurs pour moi, la suite la plus simple est 2,4,6,8,0,0,0,0,0,0,0,.... Et certainement pas 2,4,6,8,10. Qui a dit que ça devait être comme ça, hein ?

Au mieux tu pourrais définir une notion de complexité algorithmique, à la Kolmogorov. Alors la suite arithmétique est une des plus simples.

Si la suite est finie, alors en effet, il existe une infinité de combinaisons possibles, toutes aussi logiques les unes que les autres.
Dans l'hypothèse des suites infinies, plus n est grand, plus les possibilités pour le n+1eme terme se réduisent et tendent vers une valeur autorisée unique.

[gg0]

Mais alors, Andetou, tes suites logiques n'existent pas ! Quelle que soit la suite finie, il est impossible de prévoir le terme suivant uniquement à l'aide des termes de la suite, puisque le terme suivant peut être n'importe quel nombre !!
Cette fois-ci, tu parles dans le vide !!

Sans compter que ce passage est faux (c'est une opinion qui ne repose sur rien et est contredite par ce que j'ai dit ci-dessus) :

Dans l'hypothèse des suites infinies, plus n est grand, plus les possibilités pour le n+1eme terme se réduisent et tendent vers une valeur autorisée unique.