secuencia de Golomb

En matemáticas, la sucesión de Golomb , llamada así por Solomon W. Golomb (pero también conocida como sucesión de Silverman ), es una sucesión de enteros monótonamente creciente donde a _n es el número de veces que n aparece en la sucesión, comenzando con a ₁ = 1, y con la propiedad de que para n > 1 cada a _n es el entero positivo más pequeño que permite satisfacer la condición. Por ejemplo, a ₁ = 1 significa que 1 aparece solo una vez en la sucesión, por lo que a ₂ no puede ser 1 también, pero puede ser 2, y por lo tanto debe ser 2. Los primeros valores son

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 (secuencia A001462 en el OEIS ) .

a ₁ = 1 Por lo tanto, el 1 aparece exactamente una vez en esta secuencia.

a ₂ > 1 a ₂ = 2

El 2 aparece exactamente 2 veces en esta secuencia. a ₃ = 2

El número 3 aparece exactamente 2 veces en esta secuencia.

un ₄ = un ₅ = 3

El 4 aparece exactamente 3 veces en esta secuencia. El 5 aparece exactamente 3 veces en esta secuencia.

un ₆ = un ₇ = un ₈ = 4 un ₉ = un ₁₀ = un ₁₁ = 5

etc.

Colin Mallows ha proporcionado una relación de recurrencia explícita.${\displaystyle a(1)=1;a(n+1)=1+a(n+1-a(a(n)))}$. ^{[ 1 ]} Una expresión asintótica para a _n es

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

dónde${\displaystyle \varphi }$es la proporción áurea (aproximadamente igual a 1,618034). ^{[ 1 ]}

• Everest, Graham; van der Poorten, Alf; Shparlinski, Igor; Ward, Thomas (2003). Secuencias de recurrencia . Mathematical Surveys and Monographs. Vol.  104. Providence, RI : American Mathematical Society . pp.  10, 256. ISBN 0-8218-3387-1. Zbl 1033.11006 . 
• Guy, Richard K. (2004). Problemas sin resolver en teoría de números (3.ª  ed.). Springer-Verlag . Sección E25. ISBN 0-387-20860-7. Zbl 1058.11001 . 

• Código Python para la secuencia de Golomb