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

[invite1c6b0acc]

Bonjour,
Le terme "fonction" est un terme mathématique qui a une signification précise (une relation d'un ensemble dans un autre qui à un élément de l'ensemble de départ fait correspondre au plus une valeur de l'ensemble d'arrivée), laquelle définition ne précise absolument pas la façon dont on peut calculer l'image d'un élément.

C'est assez mal venu, sur un forum de mathématiques de prendre un tel terme dans une acceptation différente de celle que TOUS les lecteurs s'attendent à trouver ...


D'autre part, je ne vois pas comment on pourrait calculer 2x pour un entier naturel x quelconque sans faire ni boucle ni test.
Pour moi, l’algorithme permettant de calculer 2x pourrait s'écrire comme ça :

initialiser la retenue à 0
initialiser le chiffre courant au chiffre des unités du nombre à traiter
tant qu'il y a des chiffres à traiter
    multiplier par 2 le chiffre courant
    ajouter la retenue au résultat
    afficher le chiffre des unités du résultat
    si le résultat est supérieur à 10
        mettre la retenue à 1
    sinon
        la mettre à 0
    passer au chiffre suivant

(en affichant le résultat de droite à gauche, évidemment (sinon ce ne serait pas des chiffres arabes ))

Et "tant que" désigne une boucle, "si" un test ...



Actuellement, pour calculer la fonction qui à X fait correspondre le Xième nombre premier, je ne connais pas d'autre algorithme que de calculer les X-1 nombres premiers précédents.

C'est vrai que ce serait sympa d'avoir des algorithmes plus simples et plus rapides.
Tu as une idée d'une façon de faire ?

Edit: trop tard, daniel100 est parti.
-----

[invitee6f0086a]

Merci Chanur,

C’est le genre de discussion à quelle je m’attendais : essayer de faire comprendre à des non connaisseurs leur éventuelles erreurs et de les éclairer dans leur questionnement.

Ce sera ma dernière intervention ici, et je suis content que cela se termine sur l’intervention positive de Chanur.

By by,

[gg0]

Chanur,

C'est Daniel100 qui a introduit le mot "fonction" dans le sens "moyen de calculer". Ne nous reproche pas de l'avoir suivi sur son vocabulaire.
D'ailleurs la fonction qui associe à un entier n le n-ième nombre premier est parfaitement définie, et bien connue en termes de fonction mathématique.

Donc ton intervention tape à côté du sujet.

Dommage !

NB : Daniel100 n'était pas parti ! Il reviendra encore ...

[Amanuensis]

HS, pour répondre à un "je ne vois pas comment"

D'autre part, je ne vois pas comment on pourrait calculer 2x pour un entier naturel x quelconque sans faire ni boucle ni test.
Pour moi, l’algorithme permettant de calculer 2x pourrait s'écrire comme ça :

L'algorithme donné n'est pas exactement le calcul de 2x, mais le calcul de la représentation décimale de 2x étant donnée la représentation décimale de x (une représentation décimale étant une chaîne de longueur variable de symboles décimaux). Pour cette fonction là, a priori difficile de faire sans boucle et test.

Pour le calcul à partir d'une représentation binaire, l'algo est un simple décalage d'un cran vers les poids forts, simple concaténation côté faible d'un 0 ; et peut être exécuté avec une seule instruction élémentaire (selon la machine), donc sans boucle et sans test (du moins si on accepte de limiter le domaine de définition pour ne pas prendre en compte le débordement, ce qui n'est pas fait dans le programme indiqué).

---

Au passage cela met quelques bémols sur la relation entre fonctions et algorithmes. La notion de fonction est mathématique et abstraite, les algorithmes (tel celui indiqué par Chanur) travaillent sur des représentations particulière d'ensembles abstraits, et dépendent dans leurs détails des représentations et des machines. L'algorithme est "syntaxique" (manipulation aveugle de symboles), l'interprétation comme fonction mathématique est "sémantique" (représentation).

[gg0]

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...

Quand l'hôpital se fout de la charité

[invite6c250b59]

Pour le calcul à partir d'une représentation binaire, l'algo est un simple décalage d'un cran vers les poids forts, simple concaténation côté faible d'un 0

C'est à la fois trivialement juste, et en même temps il y a quelque chose qui ne marche pas dans cette idée. Analogie:

Si on prend deux nombres à partir de leur représentation dans un système de numération basé sur les nombres premiers, la multiplication et la factorisation prennent un temps linéaire. Est-ce que cela veut dire que les algorithmes de multiplication et de factorisation prennent un temps linéaire? Non, le travail difficile est simplement pelleté dans l'étape de codage initial.

Si on prend deux nombres finis représenté dans un système de numération tel que le premier vaut 10 (ce qui toujours possible, par simple convention), alors pas besoin de boucle, il suffit de concaténer un 0 au second nombre. Est-ce que cela veut dire qu'il n'y a pas besoin de boucles pour la multiplication? Amha non, on a simplement pelleté les boucles dans l'étape de codage initial.

[Amanuensis]

Lis comme tu veux mon message. L'idée importante est qu'un algo, décrit à un niveau de détail comparable à celui donné par Chanur, dépend de la représentation choisie.

On ne peut pas proposer des généralités à partir d'un exemple avec une représentation particulière.

Pour les entiers, la simple traduction d'un entier en une représentation compatible avec les capacités d'une machine de Turing élémentaire demande une boucle et un test ("pelleté les boucles dans l'étape de codage initial")! Pour faire x2, on peut les mettre dans la traduction en une représentation binaire, et rien ensuite ; ou prendre une représentation inadaptée (e.g., décimale) et avoir boucle/test en plus ailleurs.

Tout cela est sans grand intérêt, mais cette discussion fonction vs. algorithme de même, pour les mêmes raisons.