Base d'or
# Base d'or

La base d'or ou base φ est, en mathématiques, le système de numération utilisant le nombre d'or, à savoir $\varphi ={\frac {1+{\sqrt {5}}}{2}}$ comme base. Ce système de numération en base non entière est également désigné plus rarement comme « 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 ». 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 représentation non standard en base φ avec ces deux chiffres (ou avec d'autres chiffres) peut toujours être réécrite en forme standard, en utilisant les 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 φ. Les réels positifs 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 positifs possèdent des représentations standards infinies 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 dix : 2,2 = 2,199999… ou 1 = 0,999…).

Cette base est présentée en 1957 par George Bergman. À 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 mais depuis, l'étude de la base d'or a produit des fruits en informatique, notamment pour la conception de convertisseurs analogique-numérique et de processeurs tolérants au bruit.

## Notation

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

$\sum _{i\leq n}a_{i}\varphi ^{i}=a_{n}a_{n-1}\dots \ a_{1}a_{0},a_{-1}a_{-2}\dots _{\varphi }$

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

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

Certaines de ces représentations 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.

## Développement phinaire fini

### Standardisation et déstandardisation

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_φ$ = $110011_φ$ = $1000011_φ$ = $1000100_φ.$
* 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

Bergman 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$ = $F_{n–1}$ + $F_nφ,$ où $(F_n)$ 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 que ce développement phinaire standard fini est unique.

### Techniques d'addition, de soustraction et de multiplication

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

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 $a_n$ = 1 et $R_n$ = ${N/φ^n}$ ;
* pour tout i inférieur ou égal à n, on pose $a_{i-1}$ = $E(φR_i)$ et $R_{i-1}$ = ${φR_i}.$

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.

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 $(L_n).$ Pour un entier N supérieur à 3, on cherche le plus grand entier k tel que $L_k$ ≤ N, puis on recommence le processus sur N – $L_k$ tant que le nombre obtenu est supérieur à 3. On écrit ainsi N comme somme de nombres de Lucas. Comme $L_k$ = $φ^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 = $L_8$ + $L_6$ + $L_3$ + $L_1$ = 101001010,10100101 = 101001000,10010101.

### Nombre de 1

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.

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é

### Existence et non-unicité

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

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) — égal à ℚ(φ) — 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

La représentation phinaire est liée aux suites de Fibonacci $(F_n)$ et de Lucas $(L_n).$ 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 : $u_{n+2}$ = $u_{n+1}$ + $u_n.$ 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 :

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

$N=\sum _{-m\leq i\leq n}a_{i}\varphi ^{i}=a_{n}a_{n-1}\dots \ a_{1}a_{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é.

