Ai-je la preuve que les nombres premiers ne sont pas aléatoires ? et qu’un algorithme existe ! - Page 2
Répondre à la discussion
Page 2 sur 2 PremièrePremière 2
Affichage des résultats 31 à 37 sur 37

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



  1. #31
    Chanur

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


    ------

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

    -----
    Dernière modification par Chanur ; 20/09/2013 à 14h15.
    Ce qui se conçoit bien s'énonce clairement ; et les mots pour le dire arrivent aisément.

  2. #32
    daniel100

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

    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,
    Je comprends vite mais il faut m'expliquer longtemps

  3. #33
    gg0
    Animateur Mathématiques

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

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

  4. #34
    Amanuensis

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

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

    Citation Envoyé par Chanur Voir le message
    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).
    Dernière modification par Amanuensis ; 20/09/2013 à 15h16.
    Pour toute question, il y a une réponse simple, évidente, et fausse.

  5. #35
    gg0
    Animateur Mathématiques

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

    Citation Envoyé par Toufou Voir le message
    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é

  6. #36
    invite73192618

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

    Citation Envoyé par Amanuensis Voir le message
    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.

  7. #37
    Amanuensis

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

    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.
    Dernière modification par Amanuensis ; 20/09/2013 à 16h18.
    Pour toute question, il y a une réponse simple, évidente, et fausse.

Page 2 sur 2 PremièrePremière 2

Discussions similaires

  1. Existe-t-il une infinité de nombres premiers ?
    Par Kwaz1973 dans le forum Mathématiques du supérieur
    Réponses: 93
    Dernier message: 01/06/2023, 08h20
  2. Il existe une infinité de nombres premiers
    Par Seirios dans le forum Mathématiques du supérieur
    Réponses: 31
    Dernier message: 07/04/2018, 19h45
  3. nombres premiers en algorithme
    Par dalida1111 dans le forum Programmation et langages, Algorithmique
    Réponses: 3
    Dernier message: 30/11/2011, 22h57
  4. Preuve originale de l'infinitude des nombres premiers
    Par invited6afcb96 dans le forum Mathématiques du supérieur
    Réponses: 10
    Dernier message: 24/11/2006, 09h52
  5. Algorithme pour nombres premiers.
    Par Antikhippe dans le forum Mathématiques du supérieur
    Réponses: 26
    Dernier message: 22/05/2005, 23h28