Suite de Golomb

La suite de Golomb, ou suite de Silverman^[1],[2], est l'unique suite croissante d'entiers naturels, auto-descriptive, commençant par 1 et telle que pour tout entier ${\displaystyle n}$ supérieur ou égal à 1, le ${\displaystyle n}$^e terme de la suite est le nombre d'occurrences de l'entier ${\displaystyle n}$ dans cette suite.

Elle porte le nom du mathématicien Solomon W. Golomb qui l'a proposée en 1966 dans l'American Mathematical Monthly^[3].

Les vingt premiers termes de la suite de Golomb (suite A001462 de l'OEIS) sont :

1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8.

Par exemple, le 7^e terme de la suite étant 4, donc l'entier 7 apparaît 4 fois dans la suite.

Propriétés

• Colin Mallows a donné la définition par récurrence suivante : ${\displaystyle a(1)=1;a(n+1)=1+a(n+1-a(a(n)))}$^[4].

• Autre définition par récurrence : ${\displaystyle a(1)=1,a(2)=2}$, et pour ${\displaystyle n\geqslant 3}$, ${\displaystyle a(n)}$ est le plus petit entier ${\displaystyle k}$ tel que ${\displaystyle s(k):=a(1)+a(2)+\cdots +a(k)\geqslant n}$.

• Cela signifie que ${\displaystyle a(n)=k}$ pour tous les entiers ${\displaystyle n}$ allant de ${\displaystyle s(k-1)+1}$ à ${\displaystyle s(k)}$^[4].
• ${\displaystyle s(s(k))=a(1)+2a(2)+\cdots +ka(k)}$^[4].
• Désignant par "plage" ("run" en anglais) une séquence maximale de termes consécutifs égaux, la suite formée des longueurs successive des plages redonne la même suite : 1, 2, 2, 3, 3, 4, 4, 4, etc. C'est l'unique suite croissante faisant intervenir tous les entiers à partir de 1 ayant cette propriété. On peut construire des suites ayant cette propriété sur d'autres ensembles d'entiers comme par exemple sur les naturels impairs : 1, 3, 3, 3, 5, 5, 5, 7, 7, 7, etc. , suite A080605 de l'OEIS.

• On a l'équivalent : ${\displaystyle a(n)\sim \varphi ^{2-\varphi }n^{\varphi -1},}$ où ${\displaystyle \varphi }$ est le nombre d'or^[3].

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Golomb sequence » (voir la liste des auteurs).

1. (en) R. K. Guy, Unsolved Problems in Number Theory, Silverman's Sequences, problem E25, New York, Springer-Verlag, pp. 225-226, 1994, 1981, p. 126
2. (en) Eric Weisstein, « Silverman's Sequence », sur Mathworld
3. (en) Solomon W. Golomb, « Problem 5407 », Amer. Math. Monthly, vol. 73, n^o 6,‎ 1966, p. 674 (lire en ligne )
4. Graham, Knuth et Patashnik, Concrete Mathematics, Thomson publishing, 1998, p. 36, 535-536, exercice 2.36, traduit en Ronald Graham, Donald Knuth et Oren Patashnik (trad. Alain Denise), Mathématiques concrètes : Fondations pour l'informatique, Paris, Vuibert, 2003, 2^e éd., 687 p. (ISBN 978-2-7117-4824-2).

Bibliographie

• Jean-Luc Rémy, « Sur la suite autodécrite de Golomb », Journal of Number Theory, vol. 66,‎ septembre 1997, p. 21-26 (lire en ligne)