Secuencia de Golomb

En matemáticas, la sucesión de Golomb , llamada así por Solomon W. Golomb (pero también llamada sucesión de Silverman ), es una sucesión de números enteros monótonamente crecientes 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 hace posible satisfacer la condición. Por ejemplo, a ₁ = 1 dice que 1 solo aparece 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, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11, 12, 12, 12, 12, 12 (secuencia A001462 en la OEIS ).

Ejemplos

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

un ₂ > 1
un ₂ = 2

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

3 aparece exactamente 2 veces en esta secuencia.

un ₄ = un ₅ = 3

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

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

etc.

Reaparición

Colin Mallows ha dado una relación de recurrencia explícita . Una _expresión asintótica para n es ${\displaystyle a(1)=1;a(n+1)=1+a(n+1-a(a(n)))}$

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

donde es la proporción áurea (aproximadamente igual a 1,618034). ${\displaystyle \varphi }$

Referencias

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

Enlaces externos

• Código Python para la secuencia de Golomb