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

В математике последовательность Голомба , названная в честь Соломона В. Голомба (но также называемая последовательностью Сильвермана ), представляет собой монотонно возрастающую целочисленную последовательность где n _— это количество раз, которое n встречается в последовательности, начиная с 1 _, = 1, и со свойством, что при n > 1 каждое n _{является наименьшим уникальным целым числом} , позволяющим удовлетворить этому условию. Например, 1 _не = 1 означает, что 1 встречается в последовательности только один раз, поэтому 2 _{может также быть 1} , но может быть 2 и, следовательно, должно быть 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 встречается в этой последовательности ровно 2 раза.

а ₄ = а ₅ = 3

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

а6 = а7 ₇ ​​= а8 ₄ =
а ₉ = а ₁₀ = а ₁₁ = 5

и т. д.

Повторение

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

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

где $\varphi$ – золотое сечение (приблизительно равно 1,618034).

Ссылки

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

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

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