Matière et temps. Réalité Générale de l'Univers. R.G.U.L'univers est nombre.: Zeckendorf

Bienvenue

“The methods of theoretical physics should be applicable to all those branches of thought in which the essential features are expressible with numbers.”

—	Paul Dirac ((from the speech at the Nobel Banquet in Stockholm, December 10, 1933)

"l'univers est nombre."

"l'univers est écrit en langage mathématique. " Galilée

Le nombre porte en lui sa dimension temporelle ET matérielle.

R.G.U. : Réalité Générale de l'Univers

le temps .

Et Dieu créa le nombre, comme mesure du temps, l'homme le chiffre.

Constante arithmétique (Cf constante cosmologique) :

CKPLAN=5,55382562855700000E-17

"13 chiffres significatifs, somme 66 "

Me signaler par E-Mail , ou au tel , les inepties, ou erreurs ou imprécisions, banalités, ouverture de portes ouvertes, en faisant référence au message ECRIT ou vous n’êtes pas d'accord ou dans le doute, ou dans la compréhension , et non pas à des considérations philosophiques ou littéraires, générales .

CARPE DIEM.

Rendons grâce à Dieu.

Suivez les mises à jour en inscrivant votre e-mail :

mardi 2 mai 2023

Zeckendorf

$exemple où le nombre mystère est 48$

Magie des nombres de Fibonacci et décomposition de Zeckendorf (cnrs.fr)

Zeckendorf's theorem - Wikipedia

Le théorème de Zeckendorf, dénommé ainsi d'après le mathématicien belge Édouard Zeckendorf, est un théorème de théorie additive des nombres qui garantit que tout entier naturel $N$ peut être représenté, de manière unique, comme somme de nombres de Fibonacci distincts et non consécutifs. Cette représentation est appelée la représentation de Zeckendorf de $N$ .

Énoncé et exemple

Théorème de Zeckendorf1 — Pour tout entier naturel $N$ , il existe une unique suite d’entiers $c 0, ... , c k$ , avec $c_{0}\geq 2$ et $c i +1 > c i + 1$ , tels que

N=\sum _{i=0}^{k}F_{c_{i}}

où $F n$ est le $n$ -ième nombre de Fibonacci.

Par exemple, $0$ est représenté par la somme vide. La représentation de Zeckendorf du nombre $100$ est

100=89+8+3

Le nombre $100$ possède d'autres représentations comme somme de nombres de Fibonacci. Ainsi :

100=89+8+2+1

100=89+5+3+2+1

100=55+34+8+3

100=55+34+8+2+1

100=55+34+5+3+2+1

100=55+21+13+8+3

mais ces représentations contiennent des nombres de Fibonacci consécutifs. À toute représentation d'un entier $N$ , on associe un mot binaire, dont la $n$ -ième lettre est $1$ si $F n$ figure dans la représentation de $N$ et $0$ sinon. Ainsi, aux représentations de $100$ ci-dessus sont associés les mots :

1000010100

1000010011

1000001111

110010100

110010011

110001111

101110100

L'ensemble des mots binaires associés aux représentations de Zeckendorf forme un langage rationnel : ce sont le mot vide et les mots commençant par $1$ et ne contenant pas deux $1$ consécutifs. Une expression rationnelle de ce langage est

0+1(0+01)^{*}

Le codage de Fibonacci d'un entier est, par définition, le mot binaire associé à sa représentation, retourné et suivi d'un symbole $1$ . Ainsi, le codage de Fibonacci du nombre $100$ est $00101000011$ .

Note historique

Zeckendorf a publié sa démonstration du théorème en 19721, alors que l'énoncé était connu, sous le nom de « théorème de Zeckendorf », depuis longtemps. Ce paradoxe est expliqué dans l'introduction de l'article de Zeckendorf : un autre mathématicien, Gerrit Lekkerkerker , a rédigé la preuve du théorème (et d'autres résultats) à la suite d'un exposé de Zeckendorf, et l'a publié2 en 1952, tout en attribuant la paternité à Zeckendorf. D'après Clark Kimberling3, c'est un article de David E. Daykin4, publié dans un journal prestigieux, qui a contribué à faire connaître le résultat et son auteur.

Démonstration

La preuve du théorème est en deux parties :

1. Existence : L'existence de la représentation se prouve par l'emploi de l'algorithme glouton ou par récurrence sur $N$ .

Deux preuves de l'existence

Première preuve

On raisonne par récurrence bien fondée sur l'entier naturel

N

. Si

N

est nul, il est représenté par la somme vide. Sinon, soit

F k

, avec

k\geq 2

, le plus grand nombre de Fibonacci inférieur ou égal à

N

et soit

M=N-F_{k}

. Par hypothèse de récurrence,

M

possède une représentation. Alors, pour tout nombre

F_{\ell }

de cette représentation,

F_{k}+F_{\ell }\leq F_{k}+M=N<F_{k+1}=F_{k}+F_{k-1}

donc

F_{\ell }<F_{k-1}

. La représentation de

M

, augmentée de

F k

, est donc bien une représentation de

N

Seconde preuve

On raisonne par récurrence sur l'entier

n

considéré. L'existence est facilement vérifiable pour les petites valeurs de

n

. Supposons qu'elle soit vraie pour un entier

n

donné et décomposons cet entier en rangeant les nombres de Fibonacci par ordre croissant. Plusieurs cas sont à considérer :

Si $n=F_{i_{1}}+F_{i_{2}}+\cdots +F_{i_{s}}$ avec $4\leq i_{1}$ et $\forall j,i_{j+1}\geq i_{j}+2$ , alors :
$n+1=F_{2}+F_{i_{1}}+F_{i_{2}}+\cdots +F_{i_{s}}$
Si $n=F_{3}+F_{5}+\cdots +F_{2r-1}+F_{i_{r}}+F_{i_{r+1}}+\cdots +F_{i_{s}}$ avec $i_{r}\geq 2r+2$ et $\forall j,i_{j+1}\geq i_{j}+2$ (et éventuellement $i_{s}=2r-1$ auquel cas les termes $F_{i_{r}}+F_{i_{r+1}}+\cdots +F_{i_{s}}$ n'existent pas). Alors :
$n+1=F_{2r}+F_{i_{r}}+F_{i_{r+1}}+\cdots +F_{i_{s}}$
Si $n=F_{2}+F_{4}+\cdots +F_{2r-2}+F_{i_{r}}+F_{i_{r+1}}+\cdots +F_{i_{s}}$ avec $i_{r}\geq 2r+1$ et $\forall j,i_{j+1}\geq i_{j}+2$ (et éventuellement $i_{s}=2r-2$ auquel cas les termes $F_{i_{r}}+F_{i_{r+1}}+\cdots +F_{i_{s}}$ n'existent pas). Alors :
$n+1=F_{2r-1}+F_{i_{r}}+F_{i_{r+1}}+\cdots +F_{i_{s}}$

Ainsi,

n+1

admet aussi une décomposition.

2. Unicité : Pour cette partie, on utilise le lemme suivant :

Lemme — La somme de tout ensemble non vide de nombres de Fibonacci distincts et non consécutifs, dont le plus grand élément est $F j$ , est strictement inférieure à $F j +1$ .

Deux démonstrations du lemme

Première démonstration

On raisonne par récurrence simple sur le nombre d'éléments d'un tel ensemble

S

. L'initialisation est immédiate. Pour l'hérédité, si

S

a plus d'un élément, enlevons

F j

. Par hypothèse de récurrence, la somme des éléments restants est strictement inférieure à

F j -1

, donc la somme totale est strictement inférieure à

F j +1 + F j = F j +1

Seconde démonstration

n=F_{i_{1}}+F_{i_{2}}+\cdots +F_{i_{s}}

avec

\forall j,i_{j+1}\geq i_{j}+2

. Alors :

si $i s$ est pair :
$F_{i_{1}}+F_{i_{2}}+\cdots +F_{i_{s-1}}\leq F_{i_{s}-2}+F_{i_{s}-4}+\cdots +F_{2}$
donc :
$F_{i_{1}}+F_{i_{2}}+\cdots +F_{i_{s-1}}<F_{i_{s}-2}+F_{i_{s}-4}+\cdots +F_{2}+1=F_{i_{s}-1}$
si $i s$ est impair :
$F_{i_{1}}+F_{i_{2}}+\cdots +F_{i_{s-1}}\leq F_{i_{s}-2}+F_{i_{s}-4}+\cdots +F_{3}$
donc :
$F_{i_{1}}+F_{i_{2}}+\cdots +F_{i_{s-1}}<F_{i_{s}-2}+F_{i_{s}-4}+\cdots +F_{3}+1=F_{i_{s}-1}$

Donc, dans tous les cas,

F_{i_{s}}\leq n<F_{i_{s}}+F_{i_{s}-1}=F_{i_{s}+1}

Preuve de l'unicité

On raisonne par récurrence bien fondée sur l'entier naturel $N$ . D'après le lemme, dans une décomposition de $N$ , le plus grand indice $k$ pour lequel $F k$ apparaît (si la décomposition est non vide, c.-à-d. si $N\neq 0$ ) est entièrement déterminé par $F_{k}\leq N<F_{k+1}$ . Par hypothèse de récurrence, la décomposition de $N - F k$ (donc le reste de la décomposition de $N$ ) est également unique.

Représentation des premiers entiers

Dans la table, $R (N)$ dénote la représentation de $N$ sous forme de mot binaire.

$N$	$R (N)$
0	0
1	1
2	10
3	100
4	101
5	1000
6	1001
7	1010
8	10000
9	10001
10	10010
11	10100

L'alternance des 0 et 1 dans chacune des colonnes correspond à l'absence ou la présence d'un rectangle dans la figure en tête de la page. La suite des derniers chiffres est

010010100100\cdots

C'est le début du mot de Fibonacci. En effet, le n-ième symbole du mot de Fibonacci est 0 ou 1 selon que n est « Fibonacci pair » ou « Fibonacci impair ».

Variations

Représentation par des nombres de Fibonacci d'indices négatifs

La suite des nombres de Fibonacci peut être étendue aux indices négatifs, puisque la relation

F_{n}=F_{n-1}+F_{n-2}

permet de calculer $F_{{n-2}}$ à partir de $F n$ et de $F_{{n-1}}$ . On a (voir la section correspondante de l'article sur les nombres de Fibonacci) :

F_{-n}=(-1)^{n+1}F_{n}.

La suite complète est $\ldots ,-8,5,-3,2,-1,1,0,1,1,2,3,5,8,\ldots$ Donald Knuth a remarqué5 que tout entier relatif est somme de nombres de Fibonacci d'indices strictement négatifs qu'il appelle « Negafibonacci », la représentation étant unique si deux nombres utilisés ne sont pas consécutifs. Par exemple :

$-11=F_{-4}+F_{-6}=(-3)+(-8)$ ;
$12=F_{-2}+F_{-7}=(-1)+13$ ;
$24=F_{-1}+F_{-4}+F_{-6}+F_{-9}=1+(-3)+(-8)+34$ ;
$-43=F_{-2}+F_{-7}+F_{-10}=(-1)+13+(-55)$ .

Comme plus haut, on associe à la représentation d'un entier $N$ un mot binaire, dont la $n$ -ième lettre est $1$ si $F n$ figure dans la représentation de $N$ et $0$ sinon. Ainsi, $24$ est représenté par le mot $100101001$ . On observe que l'entier $N$ est positif si et seulement si la longueur du mot associé est impaire.

Multiplication de Fibonacci

Donald Knuth6 considère une opération de multiplication $a\circ b$ d'entiers naturels $a$ et $b$ définie comme suit : étant donné les représentations $a=\sum _{i=0}^{k}F_{c_{i}}\;(c_{i}\geq 2)$ et $b=\sum _{j=0}^{l}F_{d_{j}}\;(d_{j}\geq 2)$ le produit de Fibonacci est l'entier $a\circ b=\sum _{i=0}^{k}\sum _{j=0}^{l}F_{c_{i}+d_{j}}$ .

Par exemple, comme $2 = F 3$ et $4 = F 4 + F 2$ , on a $2\circ 4=F_{3+4}+F_{3+2}=13+5=18$ .

Knuth a prouvé le fait surprenant que cette opération est associative.

Autres suites

Zeckendorf prouve l'existence et l'unicité, sous condition, pour la représentation par les nombres de Lucas1.

Knuth mentionne que le théorème de Zeckendorf reste vrai pour les suites de k-bonacci, sous réserve que l'on n'utilise pas $k$ nombres consécutifs d'une telle suite7.

Aviezri Fraenkel a donné un énoncé général qui étend les théorèmes précédents8 : Soit $1=u_{0}<u_{1}<u_{2}<\cdots$ une suite d'entiers. Tout entier naturel $N$ a exactement une représentation de la forme