Ai-je la preuve que les nombres premiers ne sont pas aléatoires ? et qu’un algorithme existe !

[daniel100]

Bonjour à tous,

En avant propos, je souhaiterais l’indulgence des modérateurs pour laisser cette question dans cette section, pour les raisons ci-dessous, merci !

Il y a 2 ans, j’avais contacté la section mathématique de FS avec les éléments ci-après ( ici la discussion), et je n’avais pas beaucoup eu d’échos, je m’adresse donc à vous ici.

J’ai trouvé beaucoup des corrélations, non pas avec les nombres premiers, mais avec ceux qu’ils ne le sont pas.

Voici les graphiques que j’obtiens :

nb-paint.jpg



Le principe est d’afficher un pixel (noir) représentant un nombre premier dans une matrice de X ( horizontal ) vers le bas. Puis j’examine si je peux tracer des lignes (ne coupant jamais un nombre premier noir) sous diverses « angles », ce sont les lignes rouges. Parfois j’ai laissé continuer le tracé des lignes rouges vers la gauche, ce qui permet de mieux visualiser toutes ces lignes.

Bien que je n’ai pas trouvé de corrélation concernant les nombre premiers, je peux tracer des lignes parfaitement homothétiques sous diverses angles, et cela, quelque soit la valeur en abscisse.

Je peux ainsi couvrir plus de 89% des nombres non premiers, cette réflexion a été faites il y a quelques années, et il restait encore à expérimenter d’autres angles à afficher afin d‘augmenter encore et encore ce pourcentage de 89%.


Mon interrogation est donc :

Est-ce la preuve que les nombres premiers ne sont pas aléatoires ?

Si oui, « non aléatoire » implique-t-il qu’il existe un algorithme (encore inconnu bien sûr).

Si on couvrait tous les nombres non premiers, cela serait-il la preuve d’un algorithme de nombres premiers existe ?

Ce qui est troublant, est que quelque soit le nombre en abscisse, je couvre plus de 85% les nombres non premiers.

Aussi bien, j’enfonce des portes ouvertes, je ne sais pas.

Un énorme merci, d’une part si la question peut, exceptionnellement, rester ici, et bien sûr pour vos réflexions.






PS1 : 2 – 3 – 5 sont des exceptions, je ne les ai pas affichés.

PS2 : dans mon programme, après l’affichage des lignes rouges, je vérifie que tous mes nombres premiers affichés sont toujours la (pas de lignes rouges passant sur un nombre premier noir). Mon programme est fiable.
-----

[daniel100]

L’image attachée semble avoir une largeur très réduite, si celle-ci pouvait avoir une grande largeur, cela aiderait à la question, merci.

[daniel100]

Au cas ou l’image serait trop petite,

ICI

Un lien avec l’image en taille réelle,

[JPL]

Désolé mais il était impensable de laisser ce sujet dans le forum Astronomie !

[A voir en vidéo sur Futura]

[Tryss]

Ça ressemble bigrement au résultat d'un banal crible d'Eratosthène, en effet les lignes correspondent (d'une certaine façon) à des multiples.

La question légitime est alors : en quoi est-ce différent?


Parce que par exemple, pour une grille de 100 de large, tu va voir apparaitre :
- des lignes verticales, qui correspondent aux multiples de 2 et 5 : si n est divisible par 2 ou 5 alors n+100 aussi (donc celui juste en dessous)
- des lignes en biais à 26° (descendre de 1 avancer de 2), qui correspondent aux multiples de 2, 3 et 17 : si n est divisible par 2,3 ou 17, n+102 est divisible par 2,3 ou 17
-des lignes en biais de 45° (descendre de 1, reculer de 1) quii correspondent aux multiples de 3 et 11 : si n est divisible par ou 11, n+99 est aussi divisible par 3 ou 11
Et ainsi de suite...

[invite73192618]

Est-ce la preuve que les nombres premiers ne sont pas aléatoires ?

En soit les lignes que vous voyez ne peuvent pas constituer une preuve, seulement une "évidence empirique concernant les petits nombres".

Toutefois, sous réserve que j'ai bien compris votre méthode de construction, les patrons que vous voyez apparaître sont l'équivalent d'un crible d'Eratosthène.

Si oui, « non aléatoire » implique-t-il qu’il existe un algorithme (encore inconnu bien sûr).

...et ce crible d'Eratosthène, qui est connu depuis, disons, un certain temps, est un algorithme pour déterminer la suite des nombres premiers.

Si par "aléatoire", vous voulez dire "impossible à reproduire par un algorithme", alors non les nombres premiers ne sont pas aléatoires. Il y a d'autres définitions toutefois.

Si on couvrait tous les nombres non premiers, cela serait-il la preuve d’un algorithme de nombres premiers existe ?

Donc non, mais oui l'algorithme existe (en fait il y en a plusieurs connus, et ce n'est pas très compliqué d'en faire d'autre).

EDIT: mais je vois que la réponse vous avais déjà été apporté il y a deux ans
EDIT2: et il y a quelques minutes aussi

[daniel100]

Merci pour vos éclaircissements, effectivement j’avais déjà une réponse, il y a deux ans, avec le crible d'Eratosthène, ma signature n’a jamais été aussi vraie. Le crible d'Eratosthène ressemble beaucoup à ce que j’ai fait.

Je m’aperçois que j’avais une mauvaise définition du terme « algorithme ». Je croyais qu’un algorithme étais du genre Y=F(X) , permettant d’obtenir « instantanément » une réponse, et non par extrapolation (ou programme permetant de trouver la réponse).

En fin de compte, il faudrait revoir la question en ayant à l’esprit Y=F(X) et non le terme algorithme.

Ma question reviendrait donc à :

Le principe d’un crible d'Eratosthène implique t-il l’existance d’un Y=F(X) des nombres premiers ? soit une formule qui donne le Xème nombre premiers.

Ou encore, cela permetrait-il de trouver un Y=F(X) des nombres NON premier, quel est le Xème nombre NON premier.

Merci,

[invite73192618]

Je m’aperçois que j’avais une mauvaise définition du terme « algorithme ». Je croyais qu’un algorithme étais du genre Y=F(X)

Un algorithme n'est pas nécessairement une fonction y=f(x), mais une fonction y=f(x) est nécessairement un algorithme. Je ne sais pas ce que tu veux dire par "instantanément".

il faudrait revoir la question en ayant à l’esprit Y=F(X)

Le crible d'Eratosthenes peut s'écrire sans difficulté sous forme y=f(x), avec y le xième nombre premier et f la fonction/programme qui calcule y en fonction de x.

Le principe d’un crible d'Eratosthène implique t-il l’existance d’un Y=F(X) des nombres premiers ? soit une formule qui donne le Xème nombre premiers.

Ou encore, cela permetrait-il de trouver un Y=F(X) des nombres NON premier, quel est le Xème nombre NON premier.

Donc oui, et une fois que tu as une fonction qui calcule le Xième nombre premier, il n'est pas compliqué de faire une fonction qui donne le Xième nombre composite (il suffit d'énumérer les nombres en enlevant le premier, deuxième, etc nombre premier, jusqu'à trouver le xième nombre non premier).

[daniel100]

Heu… il y a quelque qui m’échappe, mais grave !

Tu dis qu’il existe une fonction qui donne le Xème nombre premier, c’est ça ?

Par instantané (peut-être la mon soucis de compréhension), j’entends un programme qui donne le 2ème NP aussi rapidement que le 10 milliards d’ième.

Ce n’est pas une approche successive, mais un algorithme style fonction.

Alors, si effectivement il existe une fonction y = f(x), merci de m’en informer la formule, je n’ai rien vu de tel d’après mes rapides recherches sur le net.

[gg0]

Non, une telle fonction n'existe pas.

Enfin, on n'en connaît pas, qui donne aussi rapidement le milliardième premier que le cinquième, même en tenant compte de la taille des nombres.

Mais toi non plus, tu n'as pas une fonction de ce genre pour les non premiers !

Cordialement.

[invite73192618]

Tu dis qu’il existe une fonction qui donne le Xème nombre premier, c’est ça ?

Oui. (plusieurs en fait)

Par instantané (peut-être la mon soucis de compréhension), j’entends un programme qui donne le 2ème NP aussi rapidement que le 10 milliards d’ième.

C'est une définition étrange. En fait avec cette définition il n'existe pas de fonction y=f(x).

si effectivement il existe une fonction y = f(x), merci de m’en informer la formule, je n’ai rien vu de tel d’après mes rapides recherches sur le net.

def function [y]=myfunction(x)

ok=0; y=0; cp=0;
while ok==0

y=y+1;
if isprime(cp)==1 then cp=cp+1; endif
if cp==x then ok=1; endif

end while

end function

edit: croise croise

[Médiat]

Alors, si effectivement il existe une fonction y = f(x), merci de m’en informer la formule, je n’ai rien vu de tel d’après mes rapides recherches sur le net.

Il suffit de regarder sur FSG :http://forums.futura-sciences.com/ma...ml#post4586919.

Le temps de calcul devient vite excessif.

[invite73192618]

Le temps de calcul devient vite excessif.

A vue de pif c'est de l'ordre de 2^n avec n le nombre de digit, mais ce n'est probablement pas le plus efficace. Par curiosité, saurais-tu quel est le record?

EDIT google is my friend 2^(n/2)

http://stackoverflow.com/questions/4...-prime-numbers

[daniel100]

Oui, je connaissais ces infos, merci, mais je n’ai toujours pas de réponse à ma question, certes mal posée.

Chaque section de futura a sa spécificité, et j’ai du mal à formuler ma question.

Bon, on est d’accord, il n’y a pas de fonction magique qui donne le Xième nombre premier.

Oui, il existe des approches successives pour TROUVER les NB, facilement programmables.

Le crible d'Eratosthenes prouve que les NP ne sont pas aléatoires, d’après ce qui a été dit.

Je vais tenter de poser une dernière fois ma question différemment (je ne veux pas devenir lourdingue).

Une suite de nombre (premiers par exemple) prouvée comme non aléatoire (le crible d'Eratosthenes), implique t-il (ou pas) l’existence (encore inconnue à ce jour) d’une fonction ordonnant ces nombres. Je dis bien fonction et non pas un programme.

Pour moi, une fonction permet de trouver « à la main » avec un papier et un crayon, le résultat, et non pas des approximations informatiques.

Merci,

[invite73192618]

Je dis bien fonction et non pas un programme.

Encore une fois, dernière promis, une fonction est un programme.

j’ai du mal à formuler ma question.

Oui, c'est probablement le problème. Il y a certains mots que tu utilises avec une certaine idée en tête, idée qui ne correspond pas à leur définition standard. Peut-être une solution serait de les éviter?

Exemple:
-existe-t-il un stroumph qui, quand on lui dit un nombre x, répond le xième nombre premier? Réponse: oui, plusieurs stroumphs possèdent cette propriété.
-existe-t-il un stroumph qui, quand on lui dit un nombre x, répond le xième nombre premier avec un temps de réponse constant? Réponse: non, aucun stroumph ne peut posséder cette propriété.
-existe-t-il un stroumph qui, quand on lui dit un nombre x, répond le xième nombre premier avec un temps de réponse proportionnel au temps qu'il faut pour lire le nombre x? Réponse: il est considéré improbable, quoique ce ne soit pas prouvé, qu'un stroumph puisse avoir cette propriété.

[daniel100]

Y = 2 X
n’a pas besoin de programme pour définir la valeur de Y pour X= 1000000000000000000000000000

C’est cela (peut être à tord) que j’appels fonction.

[invite73192618]

Tu dis que tu n'as pas besoin de stroumph mais que c'est cela que tu appelles un stroumph... désolé je ne comprend pas. C'est quoi ça un stroumph?

[daniel100]

Je n’ai pas l’habitude de cette section de FS, vous être tous comme Jiav, ou est-ce moi qui à un problème de communication ?

[invite73192618]

Je n’ai pas l’habitude de cette section de FS, vous être tous comme Jiav, ou est-ce moi qui à un problème de communication ?

Je t'ai donné la réponse en clair quatre fois. Médiat, une. Tryss, une. gg0, une. Je gagne haut la main.

[daniel100]

On va dire que c’est moi qui a un problème de communication, bonne continuation à tous.

By by

[toothpick-charlie]

A vue de pif c'est de l'ordre de 2^n avec n le nombre de digit

donc de l'ordre de x.

[Médiat]

Bon, on est d’accord, il n’y a pas de fonction magique qui donne le Xième nombre premier.

Non, on n'est pas d'accord : il en existe plusieurs, même si les temps de calculs sont vite prohibitifs.

[invite73192618]

donc de l'ordre de x.

Oui pour une version naïve comme celle que je donne plus haut. Pour le champion en titre (prouvé) c'est plutôt de l'ordre de de 2^n/2 donc sqrt(x).

[invite765732342432]

Y = 2 X
n’a pas besoin de programme pour définir la valeur de Y pour X= 1000000000000000000000000000

Et pour X=24195341735434, tu n'utilises pas de "programme" (euh, pardon, stroumph) ?
Comment calcules-tu Y dans ce cas ?

Moi je ne fais de la manière suivante: je prend chaque chiffre un par un, je le multiplie par 2 en gardant une éventuelle retenue pour le chiffre d'après.
Quand j'ai tout concaténé, j'obtiens le résultat.
Ceci est bien un stroumph, non ?

[obi76]

(intervention qui ne sert à rien : c'est "Schtroumpf" )

[daniel100]

Et pour X=24195341735434, tu n'utilises pas de "programme" (euh, pardon, stroumph) ?
Comment calcules-tu Y dans ce cas ?

Moi je ne fais de la manière suivante: je prend chaque chiffre un par un, je le multiplie par 2 en gardant une éventuelle retenue pour le chiffre d'après.
Quand j'ai tout concaténé, j'obtiens le résultat.
Ceci est bien un stroumph, non ?

C’est bien ce que j’ai dis, on peut faire le calcul « à la main », c’est une suite de séquences. Contrairement à un programme qui comporte de multiples boucles (if – repeat – while …) et qui peut prendre énormément de temps machine.

Une fonction prend infiniment moins de temps qu’un programme. Et si un jour on trouve la fonction permettant de trouver DIRECTEMENT le Xème NB, ce serait méga rapide contrairement à un programme.

Une fonction n’est pas un programme, car ne comporte pas de boucles, ni de test.

[daniel100]

Y = 2 X n’est pas un programme

Peut-être aurais-je du utiliser le terme formule ou équation à la place de fonction.

Mais bon, c’est mal parti tout ça …

[gg0]

C'est normal que ce soit mal parti : tu fais une différence là où il n'y en a pas. Et bien que ça t'ait été dit plusieurs fois, tu ne veux pas accepter que le mot "programme" a un sens suffisamment large pour recouvrir ce que tu appelles un calcul (après tout, ta calculette fait les calculs à partir ...d'un programme).

Et finalement, on a répondu toujours la même chose à tes tentatives de reformulation de ta question. Pourquoi reviens-tu ? Parce que la réponse ne te convient pas ? Alors il ne faut pas reposer ta question et rester dans ta propre certitude de toi tout seul ...

Cordialement.

[Toufou]

C'est surtout toi qu'es mal parti à prendre tout le monde de haut avec si peu de connaissances...
Les bases de l'algorithmique ceux sont: la boucle, la conditionnelle et la séquence.
Comment tu calcules ta fonction sans séquence STP ?
Tu gribouilles une formule, et bing, t'as le Nième nombre premier qui t'apparait direct dans la tête. C'est pas Poudlard ici, hein...

[daniel100]

(après tout, ta calculette fait les calculs à partir ...d'un programme).

Je confirme, j’ai plus de 30 ans d’expériences en microprocesseur.

Je trouve ton argumentation, comme n’ayant aucun sens par rapport à la question initiale.

Pas très sympa ici, je sors définitivement de cette section.