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

• Portail des mathématiques