Répondre à la discussion
Affichage des résultats 1 à 29 sur 29

Une représentation des entiers




  1. #1
    Archyves

    Une représentation des entiers

    Bonjour,

    Le théorème fondamental de l’arithmétique dit que tout entier naturel peut s’écrire comme un produit de nombres premiers, cette représentation étant unique si on ne se préoccupe pas de l’ordre des multiplications.
    Ex :80 = 2*2*2*2*5

    En partant de cela on peut écrire les entiers de manière très économe en symboles, voilà une méthode que je vous soumets.
    On déduit du théorème fondamental que tout entier n peut s’écrire :
    n = p1^a1 x p2^a2 x … pk^ak avec pi représentant le ième nombre premier, et les ai des exposants entier positifs ou nuls.
    Ex : 80 = 2^4 x 3^0 x 5^1

    On peut écrire les exposants de la même manière (récurrente) sous forme de produits de puissances de nombres premiers :
    80 = 2^(2^(2^1)) x 3^0 x 5^1

    Par convention je remplace dans l’expression tous les 1 par 1^0 :
    80 = 2^(2^(2^(1^0))) x 3^0 x 5^(1^0)
    Mon codage économe consiste à ne garder dans l’expression de droite que les parenthèses et les 0 :
    80 s’écrit alors : (((0)))0(0)

    J’appelle Primocode(n) la fonction qui a un entier positif n associe ce codage à base de parenthèses et de 0.
    Le codage des entiers de 1 à 10 donne :
    1 -> 0 ; 2 -> (0) ; 3 -> 0(0) ; 4 -> ; 5 -> 00(0) ; 6 -> (0)(0); 7 -> 000(0); 8 -> (0(0)) ; 9 -> 0((0)) : 10 -> (0)0(0)

    J’ai fait un petit programme qui calcule Primocode(n) et la fonction inverse. Un avantage de ce codage est qu’il exhibe la structure interne de chaque nombre (ses facteurs premiers), et qu’il permet donc de faire assez facilement les opérations de multiplication et d’élévation à la puissance. Mais en revanche il n’est pas possible de réaliser facilement des additions à partir de primocodes.

    Ma question : est-ce que vous savez si quelqu’un a déjà étudié une forme de représentation semblable des entiers ? Si vous avez des références cela m’intéresse.

    Yves

    -----


  2. Publicité
  3. #2
    Médiat

    Re : Une représentation des entiers

    Bonjour,

    J'avoue que je ne vois pas vraiment pourquoi la multiplication est simple sous cette forme, pourriez-vous en expliciter les règles?
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  4. #3
    Archyves

    Re : Une représentation des entiers

    Chaque terme de l'expression parenthésée a un rang, par exemple pour 80 = (((0)))0(0) on a au rang 1: (((0))), au rang 2: 0 et au rang 3 : (0)
    Si les 2 nombres à multiplier n'ont pas de facteurs communs, il suffit de conserver les rangs non nuls.
    Par exemple 7 s'écrit 000(0)
    Donc 80 x 7 s’écrit : (((0)))0(0)(0)
    S'ils ont des facteurs communs, il faut additionner les contenus de même rangs.
    15 s'écrit : 0(0)(0)
    Par exemple 80 x 15 s'écrit :
    (((0)))0(0) x 0(0)(0) = (((0)))(0)(0(0))
    Cela suppose de savoir faire des additions, par exemple ici pour le rang 3 on a besoin de savoir calculer 1+1. Avec une petite table d'addition on peut déjà faire un grand nombre de produits, mais je suis d'accord que ce n'est pas idéal car on retombe sur le problème de savoir faire des additions.
    Yves


  5. #4
    Archyves

    Re : Une représentation des entiers

    Désolé il fallait lire
    Par exemple 80 x 15 s'écrit :
    (((0)))0(0) x 0(0)(0) = (((0)))(0)((0))

  6. #5
    Médiat

    Re : Une représentation des entiers

    Citation Envoyé par Archyves Voir le message
    il faut additionner les contenus de même rangs.
    C'est bien là le problème, je vous cite :

    il n’est pas possible de réaliser facilement des additions à partir de primocodes.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  7. A voir en vidéo sur Futura
  8. #6
    Archyves

    Re : Une représentation des entiers

    Tout à fait.
    J'en reviens à ma question : si quelqu'un a déjà entendu parler de ce type de représentation, ça m'intéresse.
    Yves.

  9. #7
    gg0

    Re : Une représentation des entiers

    Bonsoir Archyves.

    Dans ta représentation, comment s'écrit 1270331 = 1009*1259 ?
    Et comment se passe la multiplication par 5065 ?

    Cordialement

  10. Publicité
  11. #8
    Archyves

    Re : Une représentation des entiers

    Bonjour gg0


    1009 x 1259 = 1270331
    000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000(0)
    x
    000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000(0)
    =
    000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000(0)000000000 00000000000000000000000000(0)

    et

    5065 = 00(0)0000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000(0)

    Pour la multiplication par 5065 c'est comme pour les autres nombres. Ici on a 2 facteurs premiers, 5 et 1013. Si le nombre à multiplier n'a pas de facteurs communs, par exemple 6 = (0)(0), il suffit de faire une "union" des 2 séquences en partant de la gauche, l'union de 0 et (0) donnant (0) :
    -> (0)(0)(0)0000000000..... 0(0)
    Sinon il faut faire des sommes des contenus des termes de même rangs. Par exemple essaie de faire 5065 x 10.
    Yves

  12. #9
    Deedee81

    Re : Une représentation des entiers

    Salut,

    Je trouve cette méthode/représentation terriblement compliquée.
    Quelle est son intérêt ?
    (et pour répondre à la question, il ne me semble pas avoir vu ça avant)
    Tout est relatif, et cela seul est absolu. (Auguste Comte)

  13. #10
    minushabens

    Re : Une représentation des entiers

    Le problème c'est la conversion de décimal vers cette notation. Si on passe beaucoup de temps à factoriser les nombres (d'autant qu'il faut le rang des facteurs premiers) pour en gagner un peu dans la multiplication ça n'a pas tellement d'intérêt.

  14. #11
    Deedee81

    Re : Une représentation des entiers

    Le volume de donnée aussi. 5065 en binaire (par exemple) c'est 13 chiffres. Alors qu'ici !!!!!
    Même une fois converti, ça complique les calculs.

    Mais voyons ce que va dire Archyves. Il a peut-être une utilité en tête qui nous a échappé (par exemple une utilité non pas pratique mais pour un usage en mathématique).
    Tout est relatif, et cela seul est absolu. (Auguste Comte)

  15. #12
    gg0

    Re : Une représentation des entiers

    Merci Archyves, d'avoir confirmé visuellement que cette représentation est inutilisable à la main (savoir s'il y a le bon nombre de zéros est difficile, c'est d'ailleurs pour cela qu'on a inventé la notation en puissances de 10).
    On attend que tu nous dises où elle est utile.

    Cordialement.

  16. #13
    Archyves

    Re : Une représentation des entiers

    Merci pour vos remarques, et pour la réponse à ma question.
    Je vais prendre le temps de répondre à vos questions dans un autre message (quand j'aurai un moment) en espérant que vous serez indulgents dans vos réactions car je n'ai pas de prétentions : c'est pour moi plus un jeu qu'autre chose qui débouche sur d'autres questions.
    Yves

  17. #14
    Deedee81

    Re : Une représentation des entiers

    Citation Envoyé par Archyves Voir le message
    c'est pour moi plus un jeu qu'autre chose
    C'est une motivation suffisante.
    On fait aussi des tas de choses pour le plaisir (je m'étais déjà amusé à construire des notations spéciales mais pour les réels. Il y a longtemps).
    Tout est relatif, et cela seul est absolu. (Auguste Comte)

  18. #15
    Archyves

    Re : Une représentation des entiers

    Pour répondre à deux remarques de Deedee81 :
    "Le volume de donnée aussi. 5065 en binaire (par exemple) c'est 13 chiffres. Alors qu'ici !!!!!"
    La comparaison que vous faites est incomplète : oui, pour les nombres premiers la représentation est très gourmande (sauf si on compresse). Ce n'est pas fait pour être manipulé à la main, mais par programme informatique.
    Considérez ce cas extrême inverse :
    2^65540 en binaire s'écrit avec 65541 caractères (en décimal environ 3.2 x 10^19729)
    2^65540 en primocode s'écrit (((((0))))) soit 11 caractères, ce qui montre qu'on ne peut pas généraliser votre exemple

    Je reviens sur une autre remarque : "je ne vois pas vraiment pourquoi la multiplication est simple sous cette forme, pourriez-vous en expliciter les règles ? "
    J'aurai dû dire : connaissant "quelques" additions, on peut faire facilement "beaucoup" de multiplications.
    En effet pour multiplier il faut additionner les exposants, et par exemple l'exposant maximum (dans la décomposition en facteurs premiers) qu'on obtient pour les nombres jusqu'à 2047 est 10 (2^11 -1 = 2047).
    Ainsi, avec la table d'addition de 2 nombres compris entre 1 et 10, si je ne me trompe pas, on peut déjà faire toutes les multiplications de 2 nombres quelconques pris entre 1 et 2047, et avec la table d'addition de 2 nombres de 1 à 16, on peut faire toutes les multiplications de 2 nombres compris entre 1 et 130 000.

    Mais comme je disais, ce n'est pas pour une utilité pratique que je m'amuse avec ces codages.
    J'ai étendu le codage à des valeurs non entières, ce qui va amener une autre question (pour ceux qui voudront bien me lire jusqu'au bout) .

    Pour rappel, je suis parti du fait que tout entier n peut s’écrire :
    n = p1^a1 x p2^a2 x … pk^ak , pi représentant le ième nombre premier

    J'ajoute un terme supplémentaire, qui n'est pas une puissance d'un nombre premier mais une puissance de -1, et on garde exactement le même système de codage
    x = (-1)^a0 x p1^a1 x p2^a2 x … pk^ak , pi représentant le ième nombre premier

    On obtient ainsi toujours les entiers naturels sauf le zéro, sous cette forme (que j'appellerai primocodes étendus) :
    0 -> -1^0 = 1
    0(0) -> -1^0 x 2^1 = 2
    00(0) -> -1^0 x 2^0 x 3^1= 3
    0(0(0)) -> -1^0 x 2^(-1^0 x 2^1) = 4
    000(0) -> -1^0 x 2^0 x 3^0 x 5^1= 5
    etc.
    On obient également les nombres négatifs, en commençant par (-1)^1 qui s'écrit donc (0)
    Ex : (0)00(0) = -5

    En utilisant le fait que je peux élever les nombres à la puissance -1, je peux obtenir tous les inverses des entiers :
    0((0)) -> -1^0 x 2^(-1^1) = 2^(-1) = 1/2
    00((0)) -> 1/3
    0((0)(0)) -> 1/4
    000((0)) -> 1/5
    etc.
    Je peux écrire toutes les fractions irréductibles, donc tous les rationnels (sauf le zéro)
    Ex : 00(0)((0)) -> 3/5

    Je peux réinjecter ces valeurs non entières en exposants, et on va ainsi obtenir les racines.
    Par exemple en utilisant 0((0)), qui vaut 1/2, en exposant :
    0(0((0))) -> racine(2)
    00(0((0))) -> racine(3)
    000(0((0))) -> racine(5)
    etc.
    De la même manière, comme on a tous les rationnels qu'on peut mettre en exposant, on obtient toutes les racines...
    Ce qu'on peut étendre aux complexes :
    (0((0))) -> i
    On peut obtenir tous les multiples de i, les puissances non entières de i, etc.
    On peut représenter des formules assez complexes, comme par exemple :
    (000((0)))(0((0))(0)) -> 2*racine(2)*(-1)^(1/5)
    J'ai étendu mon programme pour qu'il calcule les valeurs des primocodes étendus, ici le résultat est environ 2.288 + 1.663i (je pars de l'expression parenthésée et je calcule le résultat numérique, y compris quand le résultat est un complexe)

    J'en arrive enfin à ma question.
    Ce qui m'intéresserait c'est de pouvoir caractériser l'ensemble de définition de cette fonction primocode étendu, c'est à dire l'ensemble des nombres x pour lesquels primocode(x) existe.
    Je sais déjà que je ne peux pas écrire en primocode la valeur 0. Je ne pense pas pouvoir écrire 1+racine(2), ni 2+i (je n'ai pas de démonstration à l'appui, c'est plus un constat d'impuissance de ma part).
    Je ne sais pas du tout comment m'y prendre (mais mon niveau en math est BAC+2 scientifique, et ça date d'une trentaine d'année en arrière).

    Merci pour vos réponses.
    Yves

  19. #16
    Deedee81

    Re : Une représentation des entiers

    Salit,

    Arrrrg, j'ai vite décroché
    Ceci dit je te remercie pour cet effort d'explication, c'est juste que je n'ai pas encore bu mon café. Pitié pour mes pauvres neurones quinquagénaires.
    D'autres auront peut-être plus de courage que moi.
    Tout est relatif, et cela seul est absolu. (Auguste Comte)

  20. #17
    Médiat

    Re : Une représentation des entiers

    Bonjour,

    je vois quelques soucis en plus de la lisibilité :

    (-1)^(1/5) n'existe pas (mais on pourrait prendre comme convention qu'il s'agit de la racine cinquième de 1 ayant le plus petit argument)
    Comment écrivez-vous le résultat : 0(0) * 0(0(0((0)))) ?
    Dernière modification par Médiat ; 12/12/2017 à 09h54.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  21. #18
    minushabens

    Re : Une représentation des entiers

    @Archyves: tu n'as pas répondu à mon objection sur la difficulté à traduire un nombre en décimal ou en binaire vers ta notation.

    comment notes-tu 502560410469881 ? (il n'est pas premier)

  22. #19
    Archyves

    Re : Une représentation des entiers

    minushabens : La conversion de décimal ou binaire vers cette notation pas un objectif que j'ai (ni d'ailleurs de faire des multiplications rapides).

    Sauf erreur 502560410469881 est le produit de 2 grand nombre premiers (j'ai regardé sur internet), 15485867 x 32452843. Si vous avez compris le fonctionnement, il y aura plein de 0 et deux fois (0). Il n'y a pas trop d'intérêt à remplir ce post avec des lignes de 0 pour exprimer ce nombre dans ma notation.

    Yves

  23. #20
    Archyves

    Re : Une représentation des entiers

    Pour Médiat : "(-1)^(1/5) n'existe pas (mais on pourrait prendre comme convention qu'il s'agit de la racine cinquième de 1 ayant le plus petit argument)
    Comment écrivez-vous le résultat : 0(0) * 0(0(0((0)))) ?"


    Quand vous dites (-1)^(1/5) n'existe pas, j'imagine que cela signifie qu'il y a plusieurs valeurs possibles, non ?
    (-1)^(1/5) s'écrit : (000((0)))
    Mon programme ne se pose pas de question, si je lui entre (000((0))) il sort : 0.809 + 0.5878i (c'est probablement la racine cinquième de 1 ayant le plus petit argument ?)


    0(0) * 0(0((0))) revient à calculer 2^1 * 2^racine(2) c'est à dire : 2^(1+racine(2))
    Mais 1+racine(2) c'est justement un de ces cas dont je parlais dans mon post précédent que je ne sais pas calculer (vous m'auriez demandé 3 * 2^racine(2), j'aurai su faire
    Il y a hélas beaucoup de nombres réels ou complexes que je ne sais pas exprimer sous forme de notation primocodée, c'est bien le problème.
    Arriver à déterminer à l'avance ce que je peux coder ou non avec cette notation (au moins théoriquement), c'est ce qui m'intéresserait.
    Je pense que je touche là à des notions de maths qui me dépassent un peu, mais s'il y a des pistes de bouquins de maths qui pourraient m'aider à y voir plus clair, pourquoi pas.

    Yves

  24. #21
    Deedee81

    Re : Une représentation des entiers

    Salut,

    Il y a aussi un énorme problème pratique. Factoriser les grands nombres est un problème difficile. Tellement difficile qu'il est utilisé comme base de plusieurs systèmes de cryptages à clef publique.
    Donc impossible, même avec un super calculateur, de calculer les primocode des grands nombres.
    Ca me semble un handicap insurmontable.
    Tout est relatif, et cela seul est absolu. (Auguste Comte)

  25. #22
    Médiat

    Re : Une représentation des entiers

    Citation Envoyé par Archyves Voir le message
    Quand vous dites (-1)^(1/5) n'existe pas, j'imagine que cela signifie qu'il y a plusieurs valeurs possibles, non ?
    Oui



    0(0) * 0(0((0))) revient à calculer 2^1 * 2^racine(2) c'est à dire : 2^(1+racine(2))
    Mais 1+racine(2) c'est justement un de ces cas dont je parlais dans mon post précédent que je ne sais pas calculer
    Ce qui veut dire que la multiplication est problématique aussi.

    J'ai du mal à voir un intérêt mathématique à cette présentation, mais le simple fait que cela vous intéresse et vous motive est largement suffisant ; est-ce que la seule et unique question est bien de définir (simplement) l'ensemble des nombres représentables ainsi ?
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  26. #23
    minushabens

    Re : Une représentation des entiers

    Est-ce que toute suite finie des trois symboles ( ) et 0 qui respecte l'appariement de ( et ) peut être décodée en un nombre légitime?

  27. #24
    Archyves

    Re : Une représentation des entiers

    Oui Mediat : c'est la seule et unique question.
    Yves

  28. #25
    Archyves

    Re : Une représentation des entiers

    Citation Envoyé par minushabens Voir le message
    Est-ce que toute suite finie des trois symboles ( ) et 0 qui respecte l'appariement de ( et ) peut être décodée en un nombre légitime?
    Oui c'est le cas.
    Il y a une chose savoir, c'est qu'on peut facilement faire plusieurs primocodes qui donnent le même résultat : par exemple on peut ajouter à droite d'une expression valide autant de 0 qu'on veut, cela ne change pas la valeur du résultat (ajouter un 0 revient à multiplier par un nombre élevé à la puissance 0).

  29. #26
    minushabens

    Re : Une représentation des entiers

    En fait je crois que () ne représente aucun nombre. Il faut toujours au moins un zéro. Et : ((0)(0)) ?

  30. #27
    Archyves

    Re : Une représentation des entiers

    Citation Envoyé par minushabens Voir le message
    En fait je crois que () ne représente aucun nombre. Il faut toujours au moins un zéro. Et : ((0)(0)) ?
    Ou exact, j'avais oublié : () n'a pas de signification.

    Dans le codage initiale dont j'ai parlé au début (celui qui calcule sur des entiers uniquement)
    tu as (0)(0) -> 2 x 3 = 6
    donc ((0)(0)) = 2^6 = 64

    Mais si tu parles du codage 'étendu', c'est à dire avec (-1)^x en premier terme, cela donne :
    (0)(0) -> (-1)^1 * 2^1 = -2
    donc ((0)(0)) -> (-1)^(-2) = -1

  31. #28
    Archyves

    Re : Une représentation des entiers

    Oups !
    (-1)^(-2) = 1

  32. #29
    Archyves

    Re : Une représentation des entiers

    Citation Envoyé par Médiat Voir le message
    [/COLOR][/LEFT]

    J'ai du mal à voir un intérêt mathématique à cette présentation, mais le simple fait que cela vous intéresse et vous motive est largement suffisant ; est-ce que la seule et unique question est bien de définir (simplement) l'ensemble des nombres représentables ainsi ?
    Aucune petite piste à me proposer pour m'aider à définir les nombres représentables avec cette notation ? J'aurai aimé me pencher dessus pendant les vacances de Noël.
    Sinon bonne fêtes de fin d'année à tous, et bravo à tous les animateurs et modérateurs de futura-sciences pour leur sérieux et leur pédagogie.
    Yves D.

Sur le même thème :

Discussions similaires

  1. Réponses: 23
    Dernier message: 23/12/2015, 17h24
  2. Entiers naïf vs Entiers formels
    Par Médiat dans le forum Mathématiques du supérieur
    Réponses: 47
    Dernier message: 07/02/2015, 22h26
  3. Bijection entre l'ensemble des entiers naturels et des entiers pairs
    Par moial dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 04/07/2014, 22h02
  4. Les entiers naturels et les entiers relatifs
    Par Vousetesdesanimaux dans le forum Mathématiques du collège et du lycée
    Réponses: 10
    Dernier message: 28/05/2012, 15h12