Base d'or

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, le nombre d'or, à savoir

\varphi=\frac{1+\sqrt5}2

peut être utilisé comme une base de numération. Ce système est connu sous le nom de système de numération en base d'or, ou accessoirement, développement phinaire (car le symbole pour le nombre d'or est la lettre grecque « phi »), mais aussi système de numération de Bergman[1] . Tout nombre réel positif possède une représentation standard en base φ où seuls les chiffres 0 et 1 sont utilisés, et où la suite « 11 » est évitée. Une base φ non standard avec cette suite de chiffres (ou avec d'autres chiffres) peut toujours être réécrite en forme standard, la reliant aux propriétés algébriques du nombre φ — c'est-à-dire que φ + 1 = φ2. Par exemple 11φ = 100φ. Malgré l'usage d'une base irrationnelle, tous les entiers naturels possèdent une représentation unique en développement fini dans la base φ. Tous les nombres qui possèdent une représentation finie (avec une quantité finie de 0 et 1) dans la base phinaire sont les entiers de ℚ(5) positifs.

Les autres nombres possèdent des représentations standard en base φ, les nombres rationnels positifs ayant des représentations récurrentes. Ces représentations sont uniques, excepté celles des nombres qui ont un développement fini ainsi qu'un développement non fini (de la même manière qu'en base 10 : 2,2 = 2,199999…)

Cette base est présentée en 1957 par George Bergman (en). À cette époque, George Bergman entrevoit peu d'utilisations pratiques de son système mais pense ouvrir un nouveau champ d'investigation en théorie des nombres[2] mais depuis, l'étude de la base d'or a produit des fruits en informatique, notamment pour la conception de convertisseurs analogiques digitaux et de processeurs tolérants au bruit[3].

Ce système est un cas particulier de β-expansion (en).

Notation[modifier | modifier le code]

Par la suite, par analogie avec l'écriture décimale positionnelle, on notera

\sum_{i\leq n}a_i \varphi^i= a_na_{n-1}\dots\ a_1a_0, a_{-1}a_{-2}\dots _{\varphi}

Si, pour tout i inférieur ou égal à n, ai appartient à {0;1} et (ai, ai-1) est différent de (1,1), l'écriture sera appelé écriture phinaire standard ou minimale[4], ou la plus simple [5].

On utilisera parfois, de manière intermédiaire, la notation dans le cas où, pour tout i inférieur ou égal à n, aiappartient à {0;1} mais où la série 11 peut apparaitre ou même dans le cas où les ai sont choisis dans un autre ensemble que {0,1}. On parlera alors de représentations phinaires non standards.

Certaines de ses représentation non standards sont également étudiées : celle ne comportant que des 0 et des 1 mais sans 0 consécutifs, ou bien celle ne comportant que des 0 et 1 mais dont la longueur est minimale[4].

Développement phinaire fini[modifier | modifier le code]

Standardisation et déstandardisation[modifier | modifier le code]

Tout nombre ayant une représentation phinaire finie composée de 0 et de 1 possède également un développement phinaire standard obtenu en chassant successivement les couples 11, par la gauche, en remplaçant 11φ par 100φ

Exemple : 110101,1101φ = 1000101,1101φ=1000110,0101φ=1001000,0101φ

Dans une représentation phinaire standard, il est possible de remplacer un chiffre 1 par un chiffre 0, ou un chiffre 0 par un chiffre 1 tout en conservant une représentation phinaire non standard ne comportant que des 0 et de 1.

  • Pour remplacer un chiffre 1 par un chiffre 0, on regarde la série de chiffres situés à droite de 1
    • la série [1]00, peut se remplacer par [0]11
    • la série [1]0101...0100 peut se remplacer par [0]1111...1111
  • Pour remplacer un chiffre 0 par un chiffre 1, on regarde la série de chiffres situés à gauche de 0
    • la série 1000...[0] comportant un nombre pair de 0 peut se remplacer par 0101..1[1]
    • la série 10...[0] comportant un nombre impair de 0, demande un traitement plus spécial : il faut commencer par mettre un 0 à droite du 0 à modifier puis on remplace la série ..1000...[0] 0 par 0101..[1]1

Ces deux techniques offrent un moyen simple d'ajouter ou retrancher une puissance de φ à un nombre écrit en représentation standard en passant provisoirement en représentation non standard.

  • Exemple d'ajout :10[1]001φ + 1000φ = 10[0]111φ +1000φ =101111φ =11010φ =100010φ
  • Exemple de retrait : 1[0]010φ - 1000φ = 0[1]110φ -1000φ =110φ =1000φ

Elles permettent de montrer que l'ensemble des nombres possédant une représentation phinaire standard finie est stable par addition et par soustraction.

Ensemble des nombres possédant une représentation phinaire finie[modifier | modifier le code]

Bergman[5] utilise la technique de remplacement de 1 par 0 pour démontrer successivement que chaque entier strictement positif possède un développement phinaire fini et déterminer les développements des premiers entiers

Décomposition (standard) des dix premiers entiers
Entier Calculs intermédiaires Ecriture standard Puissances de \varphi\,
1 1 \varphi^0\,
2 0,11+1=1,11 10,01 \varphi^1 + \varphi^{-2}\,
3 11,01 100,01 \varphi^2 + \varphi^{-2}\,
4 101,01 \varphi^2 + \varphi^0 + \varphi^{-2}\,
5 100,1111+1=101,1111 1000,1001 \varphi^3 + \varphi^{-1} + \varphi^{-4}\,
6 1001,1001 1010,0001 \varphi^3 + \varphi^1 + \varphi^{-4}\,
7 1011,0001 10000,0001 \varphi^4 + \varphi^{-4}\,
8 10001,0001 \varphi^4 + \varphi^0 + \varphi^{-4}\,
9 10000,1101 + 1= 10001,1101 10010,0101 \varphi^4 + \varphi^1 + \varphi^{-2} + \varphi^{-4}\,
10 10011,0101 10100,0101 \varphi^4 + \varphi^2 + \varphi^{-2} + \varphi^{-4}\,


Une multiplication par φ consistant seulement à décaler tous les chiffres d'un cran vers la gauche, tout nombre s'écrivant bφ où b est un entier strictement positif possède aussi un développement phinaire fini.

La stabilité par addition et soustraction prouve que tout nombre strictement positif s'écrivant a + bφ , avec a et b entiers relatifs, possède un développement phinaire standard fini. Tout élément de ℤ[φ], c'est à dire tout entier de ℚ(5) possède donc un développement phinaire standard fini.

Comme, d'autre part, on peut démontrer que, pour tout entier relatif n, φn = Fn–1 + Fnφ, où (Fn) désigne la suite de Fibonacci généralisée aux indices négatifs, toute puissance de φ est élément de ℤ[φ], et tout nombre possédant un développement phinaire standard fini est élément de ℤ[φ].

Les nombres possédant un développement phinaire standard fini sont donc les éléments strictement positifs de ℤ[φ].

On peut en outre démontrer[réf. nécessaire] que ce développement phinaire standard fini est unique.

Techniques d'addition de soustraction et de multiplication[modifier | modifier le code]

Les techniques de substitutions décrites précédemment permettent, dans une addition, d'éviter d'ajouter deux chiffres 1 dans une même colonne, ou d'avoir à soustraire 1 dans une colonne où figure un 0. Par exemple

  • 2 + 3 = 10,01 + 100,01 = 10,01 + 100,0011 = 110,0111 = 1000,1001 ;
  • 7 − 2 = 10000,0001 - 10,01 = 1100,0001 − 10,01 = 1011,0001 − 10,01 = 1010,1101 - 10,01 = 1000,1001.

Mais on peut également utiliser un développement phinaire intermédiaire non standart utilisant des 2 et des -1 (notés 1) que l'on transformera ensuite sous forme standard en utilisant les techniques

  • 010φ = 101φ.
  • 0200φ = 1001φ

Pour l'addition de deux nombres en base φ, il suffit d'ajouter chaque paire de chiffres, sans retenue, puis de convertir le nombre en forme standard. Pour la soustraction, on déduit chaque paire de chiffres sans retenue, puis on convertit le nombre en forme standard. Pour la multiplication, on peut multiplier de façon habituelle, sans retenue, puis convertir le nombre en forme standard.

Par exemple :

  • 2 + 3 = 10,01 + 100,01 = 110,02 = 110,1001 = 1000,1001 ;
  • 2 × 3 = 10,01 × 100,01 = 1000,1 + 1,0001 = 1001,1001 = 1010,0001 ;
  • 7 − 2 = 10000,0001 − 10,01 = 10010,0101 = 1110,0101 = 1001,0101 = 1000,1001.

Recherche du développement phinaire fini d'un entier[modifier | modifier le code]

Bergman propose une méthode pas à pas décrite ci-dessus pour déterminer les développements phinaires des entiers de 1 à N mais fait aussi remarquer que les techniques opératoires décrites ci-dessus offrent des moyens d'arriver plus rapidement au résultat.

Exemple : 70 = 10 × 7 = 10100,0101φ × 10000,0001φ = 101000101φ +1,01000101φ= 101000101φ +0,11110101φ= 101000101,11110101φ=101001000,10010101φ

Il existe également un algorithme glouton pour trouver le développement phinaire de N (dans la suite on notera E(x) la partie entière de x et {x} sa partie fractionnaire ou décimale):

  • on cherche l'entier n tel que φn ≤ N < φn+1 , on pose alors an = 1 et Rn = {N/ φn}
  • pour tout i inférieur ou égal à n, on pose ai-1 =E(φRi ) et Ri-1 = {φRi }.

Cet algorithme est équivalent à celui consistant à ôter à N la plus grande puissance de φ inférieure à N et à recommencer sur le nombre obtenu. On peut démontrer que cet algorithme s'arrête si N est un entier[6][réf. insuffisante] .

La procédure ci-dessus ne donnera jamais la suite « 11 », puisque 11φ = 100φ, donc obtenir un « 11 » signifie que l'on a manqué un « 1 » auparavant.

On peut enfin se servir des nombres de Lucas (Ln). Pour un entier N supérieur à 3, on cherche le plus grand entier k tel que LkN, puis on recommence le processus sur N - Lk tant que le nombre obtenu est supérieur à 3. On écrit ainsi N comme somme de nombres de Lucas. Comme Lk = φk + (-φ)-k, on obtient un développement phinaire non standard comportant des 1 et des -1 séparés par des 0, développement qu'il suffit de standardiser.

Exemple : 70 = 47 + 18 + 4 + 1 = L8 +L6 + L3 + L1 = 101001010,10100101=101001000,10010101

Nombre de 1[modifier | modifier le code]

Dans une écriture phinaire finie, formée de 0 et de 1, le nombre de 1 indique le nombre de puissances de φ utilisées pour écrire le nombre en question. L'écriture phinaire standard est celle qui minimise le nombre de 1[4].

La suite qui donne, pour chaque entier N, le nombre de puissances de φ nécessaires à son écriture est la suite A055778 de l'OEIS. On suppose, sans l'avoir encore démontré que ce nombre est toujours supérieur ou égal au nombre de termes de la représentation de Zeckendorf de N.

Développement phinaire illimité[modifier | modifier le code]

Existence et non unicité[modifier | modifier le code]

L'algorithme glouton précédent appliqué à un réel positif quelconque fournit un développement phinaire standard éventuellement illimité, pour tout réel x positif.

Réciproquement, tout développement phinaire converge vers un réel car la somme des termes pour les indices négatifs correspond à une série dont le terme général, positif, est inférieur ou égal à (1/φ)k , terme général d'une série convergente.

Comme pour le développement décimal où le développement de 0,99999..... converge vers le nombre 1, on observe que tout développement phinaire qui se conclut par une alternance infinie de 0 et de 1 converge vers un nombre qui possède également un développement phinaire fini. Ce phénomène provient du fait que 0,1010101…φ=1. Il existe plusieurs manières de justifier cette affirmation

  • En convertissant 1 vers une forme non standard : 1  = 0,11_{\varphi} = 0,1011_{\varphi} = 0,101011_{\varphi} = \ldots = 0,10101010 \ldots_\varphi
  • En utilisant une série géométrique : 1,0101010 \ldots_\varphi=\sum_{k=0}^\infty \varphi^{-2k}=\frac{1}{1-\varphi^{-2}} = \varphi
  • En effectuant la différence entre deux « déplacements » : \varphi^2 x - x = 10,101010 \ldots_{\varphi} - 0,101010 \ldots_{\varphi} = 10_{\varphi} = \varphi c'est-à-dire x = \varphi/(\varphi^2-1) = 1

Division et développement périodique[modifier | modifier le code]

Il est possible de diviser un entier a par un entier b écrits tous deux en base d'or en utilisant la méthode de la division longue. Les quotients successifs étant de 0 ou 1, le travail consiste seulement à savoir effectuer des soustractions.

Exemple : division de 100φ par 1001φ

0, 0 1 0 0 1
1001 1 0 0, 0 0 0
1 0 0 1
1 0 0 0 0
1 0 0 1
  1 0 etc.

Ici, on obtient le même reste; la division se poursuit indéfiniment et le quotient de 100φ par 1001φ est 0,01001001001...φ.

Puisqu'il existe un nombre fini de restes possibles, le quotient d'un entier a par un entier b a un développement phinaire fini (si le quotient est entier) ou périodique.

De même, comme tout élément positif du corps ℚ[5] (confondu avec ℚ[φ] ) est le quotient d'un élément de ℤ[φ] (de développement fini) par un entier (de développement fini), il est de développement fini ou périodique.

Réciproquement, tout développement périodique correspond à un élément de ℚ(5) . En effet, si la période est de longueur k et commence à l'indice j, le réel en question s'écrit

 x = A + B\varphi^{j-k+1}(1+\varphi^{-k}+ \varphi^{-2k}+\dots)= A + \frac{B\varphi^{j-k+1}}{1-\varphi^{-k}}

où A et B sont à développements finis. Il s'agit de sommes, produits et quotients d'éléments de ℚ(5) . Le réel x est bien élément de ℚ(5)

Relations avec les suites de Fibonnacci et Lucas[modifier | modifier le code]

La représentation phiniare est liée aux suites de Fibonacci (Fn) et de Lucas (Ln). En effet, la suite des puissances de φ, la suite de Fibonacci et les nombres de Lucas vérifient tous trois la relation de récurrence : un+2=un+1+un. Les termes des suites de Fibonacci et de Lucas s'expriment à l'aide de puissances de φ. Les puissances de φ s'expriment à l'aide de la suite de Fibonacci généralisée éventuellement aux nombres négatifs :

\varphi^n=F_{n-1}+\varphi F_n

Il en est de même des nombres de Lucas :

L_n=2F_{n-1}+\varphi F_n

De ces deux relations naissent deux théorèmes concernant la représentation phinaire standard des nombres entiers[7]:

Soit N un nombre dont la représentation phinaire standart est finie :

N=\sum_{-m\leq i \leq n}a_i \varphi^i= a_na_{n-1}\dots\ a_1a_0, a_{-1}a_{-2}\dots a_{-m}

N est un entier si et seulement si \sum_{-m\leq i \leq n}a_i F_i = 0

N est un entier si et seulement si \sum_{-m\leq i \leq n}a_i L_i = 2N

Ces propriétés sont utiles pour le contrôle des informations dans un système informatisé[8].

Notes et références[modifier | modifier le code]

  1. Stakhov 2009, p. 476
  2. Bergman 1957, p. 109
  3. Stakhov 2009, p. 477
  4. a, b et c (en) Ron Knott, « Phigits and the Base Phi representation : » (consulté le 2 mars 2015)
  5. a et b Bergman 1957, p. 100
  6. (en) Jeffrey Quesnelle, « The golden ratio base » (consulté en mars 2015)
  7. Z et D- property of natural numbers(Stakhov 2009, p. 499)
  8. (en) Alexey Stakhov, « Bergman's number system », sur Museum of Harmony (consulté en mars 2015)

Sources[modifier | modifier le code]