Sequência de Golomb

Em matemática, a sequência de Golomb, em homenagem a Solomon W. Golomb (mas também chamada sequência de Silverman), é uma sequência não-decrescente de números inteiros, onde ${\displaystyle a(n)}$ é o número de vezes em que ${\displaystyle n}$ ocorre na sequência, começando com ${\displaystyle a(1)=1}$, e com a propriedade de que, para n> 1, cada um ${\displaystyle a(n)}$ é o menor número inteiro que faz com que seja possível satisfazer a condição. Por exemplo, ${\displaystyle a(1)=1}$ diz que uma só ocorre o valor 1 uma vez na sequência, de modo que ${\displaystyle a(2)}$ não pode ser 1 também, e portanto deve ser de 2.

Os primeiros valores são: 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12 (sequência A001462 na OEIS).

Colin Mallows obteve a seguinte relação de recorrência ${\displaystyle a(1)=1;a(n+1)=1+a(n+1-a(a(n)))}$. Uma fórmula fechada para ${\displaystyle a_{n}}$ é

${\displaystyle \varphi ^{2-\varphi }n^{\varphi -1}}$

onde ${\displaystyle \varphi }$ é a razão áurea.

• Richard K. Guy, problemas não resolvidos na teoria dos números (3 ª ed), Springer Verlag, 2004 ISBN 0-387-20860-7; seção E25.