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 $a(n)$ é o número de vezes em que $n$ ocorre na sequência, começando com $a(1)=1$, e com a propriedade de que, para n> 1, cada um $a(n)$ é o menor número inteiro que faz com que seja possível satisfazer a condição. Por exemplo, $a(1)=1$ diz que uma só ocorre o valor 1 uma vez na sequência, de modo que $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 $a(1)=1;a(n+1)=1+a(n+1-a(a(n)))$. Uma fórmula fechada para $a_{n}$ é

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

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

Referências

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