Suite de Golomb

La suite de Golomb, ou suite de Silverman, est l'unique suite croissante d'entiers naturels, auto-descriptive, commençant par 1 et telle que pour tout entier $n$ supérieur ou égal à 1, le $n$^e terme de la suite est le nombre d'occurrences de l'entier $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.

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 : $a(1)=1;a(n+1)=1+a(n+1-a(a(n)))$.

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

• Cela signifie que $a(n)=k$ pour tous les entiers $n$ allant de $s(k-1)+1$ à $s(k)$.
• $s(s(k))=a(1)+2a(2)+\cdots +ka(k)$.
• 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 : $a(n)\sim \varphi ^{2-\varphi }n^{\varphi -1},$ où $\varphi$ est le nombre d'or.

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).

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)