Последовательность Голомба - Golomb sequence

В математике Последовательность Голомба, названный в честь Соломон В. Голомб (но также называется Последовательность Сильвермана), является неубывающей целочисленная последовательность где а_п это количество раз, когда п встречается в последовательности, начиная с а₁ = 1, и с тем свойством, что при п > 1 каждый а_п - наименьшее уникальное целое число, которое позволяет удовлетворить условию. Например, а₁ = 1 означает, что 1 встречается в последовательности только один раз, поэтому а₂ тоже не может быть 1, но может быть и, следовательно, должно быть 2. Первые несколько значений

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 (последовательность A001462 в OEIS ).

Примеры

а₁ = 1
Следовательно, 1 встречается в этой последовательности ровно один раз.

а₂ > 1
а₂ = 2

2 встречается в этой последовательности ровно 2 раза.
а₃ = 2

3 встречается в этой последовательности ровно 2 раза.

а₄ = а₅ = 3

4 встречается в этой последовательности ровно 3 раза.
5 встречается в этой последовательности ровно 3 раза.

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

и т.п.

Повторение

Колин Мэллоуз дал явный отношение повторения ${ Displaystyle а (1) = 1; а (п + 1) = 1 + а (п + 1-а (а (п)))}$. An асимптотическое выражение для а_п является

${ Displaystyle varphi ^ {2- varphi} п ^ { varphi -1},}$

где ${ displaystyle varphi}$ это Золотое сечение (примерно 1.618034).

использованная литература

• Эверест, Грэм; ван дер Поортен, Альф; Шпарлинский, Игорь; Уорд, Томас (2003). Повторяющиеся последовательности. Математические обзоры и монографии. 104. Провиденс, Род-Айленд: Американское математическое общество. С. 10, 256. ISBN  0-8218-3387-1. Zbl  1033.11006.
• Гай, Ричард К. (2004). Нерешенные проблемы теории чисел (3-е изд.). Springer-Verlag. Раздел E25. ISBN  0-387-20860-7. Zbl  1058.11001.

внешние ссылки

• Код Python для последовательности Голомба