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 = φ². 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, φⁿ = 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^{[réf. nécessaire]} 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 < φⁿ⁺¹ ; on pose alors a_n = 1 et R_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^{[source 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 (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₈ + L₆ + L₃ + L₁ = 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é.

Sources

• (en) George Bergman, « A Number System with an Irrational Base », Mathematics Magazine, vol. 31, n^o 2,‎ 1957, p. 98-110 (DOI 10.2307/3029218, JSTOR 3029218, lire en ligne).
• (en) Cecil Clyde Rousseau, « The Phi Number system Revisited », Mathematics Magazine, vol. 68, n^o 2,‎ 1995, p. 283-284 (JSTOR 2690574).
• (en) Sarkis Agaian et Yicong Zhou, chap. 78810M « Generalized phi number system and its applications for image decomposition and enhancement », dans David Akopian, Reiner Creutzburg, Cees G. M. Snoek, Nicu Sebe et Lyndon Kennedy, Multimedia on Mobile Devices 2011; and Multimedia Content Access: Algorithms and Systems V (conférence IS&T (en)/SPIE Electronic Imaging, 23-27 janvier 2011, San Francisco), Bellingham, SPIE, coll. « Proceedings » (n^o 7881), 2011 (DOI 10.1117/12.878778, lire en ligne).
• (en) Alexey Stakhov, The Mathematics of Harmony : From Euclid to Contemporary Mathematics and Computer Science, World Scientific, 2009, 694 p. (ISBN 978-981-27-7583-2 et 981-27-7583-8, présentation en ligne).
• (en) Ron Knott, « Phigits and the Base Phi representation : », Université de Surrey (consulté le 2 mars 2015).
• (en) Eric W. Weisstein, « Phi Number System », sur MathWorld.
• Alexey Stakhov (en), Museum of Harmony.