Suite de Golomb

La suite de Golomb, ou suite de SilvermanModèle:,, 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$Modèle: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 (Modèle: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 Modèle:7e 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⩾3$, $a(n)$ est le plus petit entier $k$ tel que $s(k):=a(1)+a(2)+\cdots +a(k)⩾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. , Modèle:OEIS.

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

Bibliographie

• Modèle:Article