Последовательность Колакоски

Последовательность Колакоски, также последовательность Ольденбургера — Колакоски — это бесконечная последовательность чисел 1 и 2, которая является кодированием длин серий^[1] и прототипом для бесконечного семейства родственных последовательностей. Первоначально она была названа в честь математика Уильяма Колакоски (William Kolakoski^[en]), который предложил её в 1965 году^[2], но последующие исследования показали, что она впервые появляется в статье Руфуса Олденбургера (Rufus Oldenburger^[en]) в 1939 году^[3].

Определение классической последовательности КолакоскиПравить

Начало последовательности Колакоски:

1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, … (последовательность A000002 в OEIS).

Последовательность, составленная из количества цифр, встречающихся в последовательности подряд, в точности совпадает с исходной последовательностью:

1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, …
1,   2,    2,  1, 1,   2,  1,   2,    2,  1,   2,    2,  1, 1,   2,  1, 1,   2,    2,  …

И наоборот, каждое число последовательности Колакоски порождает последующие одно или два числа, чередуя единицы и двойки.

Анимация, иллюстрирующая процесс

Это свойство самогенерации показывает, что последовательность Колакоски может быть описана как фрактал, то есть математический объект, кодирующий своё представление на других масштабах.

Последовательность Колакоски считается апериодической^[4], то есть не имеет повторяющегося шаблона.

Другие самогенерирующиеся последовательности КолакоскиПравить

Из конечных целочисленных множествПравить

Последовательность Колакоски является прототипом бесконечного семейства других последовательностей, каждая из которых имеет свою собственную кодировку длины выполнения. Некоторые из последовательностей Колакоски, перечисленных в OEIS:

Для множества {1, 3}

1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 1, 1, 1, 3, 3, 3, 1, 3, 1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 3, 3, 1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 1, 3, 3, 3, … (последовательность A064353 в OEIS)

Для множества {2, 3}

2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, … (последовательность A071820 в OEIS)

Для множества {1, 2, 3}

1, 2, 2, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 2, 2, 3, 3, 3, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 3, 1, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 1, 2, 3, 1, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 2, 2, 3, 3, 3, 1, 2, 3, 3, … (последовательность A079729 в OEIS)

Как и последовательность Колакоски для {1,2}, запись длин серий возвращает ту же последовательность. В общем случае любое множество целых чисел {n₁, n₂, n₃, …, n_i} может генерировать последовательность Колакоски, если одно и то же целое число не встречается дважды или более подряд и/или в начале и в конце множества. Например, для множества {3,1,2}:

3, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 2, 2, 3, 3, 3, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 3, 1, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 1, 2, 3, 1, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 2, 2, 3, 3, 3, 1, 2, 3, 3, 1, 1, …

И для множества {2, 1, 3, 1}:

2, 2, 1, 1, 3, 1, 2, 2, 2, 1, 3, 3, 1, 1, 2, 2, 1, 3, 3, 3, 1, 1, 1, 2, 1, 3, 3, 1, 1, 2, 1, 1, 1, 3, 3, 3, 1, 1, 1, 2, 1, 3, 1, 1, 2, 1, 1, 1, 3, 3, 3, 1, 2, 1, 1, 3, 1, 2, 1, 1, 1, 3, 3, 3, 1, 1, 1, 2, 1, 3, 1, 1, 2, 1, 1, 1, 3, 1, 2, 2, 1, 3, 1, 2, 2, 2, 1, 1, 1, 3, 3, 3, 1, 2, 2, 1, 3, 1, 1, 1, …

Опять же, запись длин серий возвращает ту же последовательность.

Из бесконечных целочисленных множествПравить

Последовательности Колакоски также могут быть созданы из бесконечных множеств целых чисел.

Например, для множества {1, 2, 1, 3, 1, 4, 1, 5, …}:

1, 2, 2, 1, 1, 3, 1, 4, 4, 4, 1, 5, 5, 5, 5, 1, 1, 1, 1, 6, 6, 6, 6, 1, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 9, 1, 10, 1, 11, 11, 11, 11, 11, 11, 1, 1, 1, 1, 1, 1, 12, 12, 12, 12, 12, 12, 1, 1, 1, 1, 1, 1, 13, 1, 1, 1, 1, 1, 1, 1, 14, 14, 14, 14, 14, 14, 14, 1, 1, 1, 1, 1, 1, 1, …

Бесконечное множество {1,2,3,4,5,…} генерирует последовательность Голомба:

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,2,3} одна из возможных последовательностей такова:

2, 2, 1, 1, 3, 1, 3, 3, 3, 2, 1, 1, 1, 2, 2, 2, 1, 1, 1, 3, 3, 2, 1, 3, 2, 2, 3, 3, 2, 2, 3, 1, 3, 1, 1, 1, 3, 3, 3, 1, 1, 3, 2, 2, 2, 3, 3, 1, 1, 3, 3, 3, 1, 1, 1, 3, 3, 1, 1, 2, 2, 2, 3, 1, 1, 1, 3, 1, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 3, 2, 3, 3, 3, 2, 2, 1, 1, 2, 2, 3, 3, 3, 2, 2, 2, 1, 2, 1, 1, 1,…

По сути, последовательность основана на бесконечном множестве {2,1,3,1,3,2,1,2,1,3,2,…}, которая является случайной последовательностью единиц, двоек и троек, из которой были удалены повторы.

Цепочки последовательностейПравить

Так же, как классическая последовательность Колакоски генерирует сама себя, эти две последовательности генерируют друг друга:

1,1,2,1,1,2,2,1,2,2,1,2,1,1,2,2,1,2,2,1,1,2,1,2,2,1,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,2,1,1,2,1,2,2,… (последовательность A025142 в OEIS)

2,1,2,2,1,2,1,1,2,2,1,2,2,1,1,2,1,1,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,1,2,2,1,2,2,1,2,1,1,2,1,2,2,… (последовательность A025143 в OEIS)

Другими словами, если выписать длины серий первой последовательности, будет создана вторая, и если выписать длины серий второй последовательности, будет создана первая.

В следующей цепочке из трёх последовательностей длины серий каждой генерируют следующую:

1,1,2,2,3,3,1,1,1,2,3,1,1,2,2,3,3,3,1,1,1,2,2,2,3,1,2,3,3,1,1,1,2,3,3,… (последовательность A288723 в OEIS)

2,2,2,3,1,1,2,2,3,3,3,1,1,1,2,3,1,2,2,3,3,1,1,2,2,2,3,1,1,2,2,2,3,3,3,… (последовательность A288724 в OEIS)

3,1,2,2,3,3,1,1,1,2,2,2,3,1,2,3,3,1,1,1,2,3,1,1,2,2,3,3,3,1,1,1,2,2,2,… (последовательность A288725 в OEIS)

Последовательности используют целочисленное множество {1,2,3}, но каждая начинается с разных элементов множества.

Следующие пять последовательностей образуют подобную цепочку, используя множество {1,2,3,4,5}:

1,1,2,2,3,3,4,4,4,5,5,5,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,5,…

2,2,2,3,3,3,4,4,4,5,5,5,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,5,…

3,3,3,3,4,4,4,4,5,5,5,5,1,1,1,1,2,2,2,2,3,3,3,3,3,4,5,1,1,2,2,3,3,3,…

4,4,4,4,4,5,1,1,2,2,3,3,3,4,4,4,5,5,5,5,1,1,1,1,2,2,2,2,3,3,3,3,3,…

5,1,2,2,3,3,4,4,4,5,5,5,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,4,…

Однако, для создания цепочки из n элементов, необязательно иметь множество из n элементов. Например, следующая цепочка из пяти последовательностей использует множество {1, 2}:

2,1,1,2,2,1,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,1,2,2,1,…

1,2,2,1,1,2,1,1,2,1,2,2,1,2,2,1,1,2,1,2,2,1,2,1,1,2,1,1,2,2,1,2,2,…

1,2,2,1,2,1,1,2,1,2,2,1,1,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,…

1,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,…

1,1,2,1,2,2,1,1,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,…

Каждая последовательность уникальна, и длины выполнения каждой генерируют члены следующей последовательности в цепи. Целочисленные множества, используемые для создания цепочки, также могут быть разных размеров. Из множеств {1,2} и {1,2,3,4,5} генерируются следующие последовательности:

1,2,2,1,1,2,2,2,1,1,1,2,2,2,2,1,1,1,1,1,2,1,2,2,1,1,2,2,2,…

1,2,2,3,3,4,5,1,1,2,2,3,3,4,5,1,2,2,3,3,4,4,5,5,1,2,3,4,5,…

Доля единиц в последовательностиПравить

Кажется правдоподобным, что доля единиц в классической последовательности Колакоски равна 1/2, но эта гипотеза остаётся недоказанной.^[4] Václav Chvátal доказал, что верхняя граница доли единиц меньше 0.50084^[5]. Джон Нильсон использовал тот же метод с гораздо большей вычислительной мощностью для получения границы 0.500080^[6].

Хотя в расчётах были использованы первые 3×10⁸ значений последовательности, по-видимому, его плотность сходятся к значению немного отличается от 1/2, но более поздние расчёты показали, что расширение последовательности в первых 10¹³ значения отклоняются от доли единиц 1/2 всё меньше и меньше, поэтому можно ожидать, что предельная доля единиц на самом деле 1/2^[7].

Последовательность антиколакоскиПравить

В последовательности антиколакоски длины серий единиц и двоек никогда не совпадают с членами исходной последовательности:

2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 2, 1, 1, … (последовательность A049705 in the OEIS).

2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, …
1,   2,    2,  1, 1,   2,  1,   2,    2,  1,   2,    2,  1, 1,   2,  1, 1,   2,    2,  1, …

Как видно, единицы в последовательности антиколакоски находятся на тех позициях, где в классической последовательности Колакоски стоят двойки, и наоборот.

Постоянная КолакоскиПравить

Постоянная Колакоски определяется в двоичной системе счисления следующим образом. На каждой двоичной позиции после запятой находится 1, если на соответствующей позиции классической последовательности Колакоски находится двойка, и 0, если единица^[8]. Первая единица последовательности игнорируется. Таким образом,

0.11001011011001001101001011001001011…₂ = 0.7945071927794792762403624156360456462…₁₀.

См. такжеПравить

ПримечанияПравить

↑ N. Pytheas Fogg. Substitutions in dynamics, arithmetics and combinatorics. — Berlin: Springer-Verlag, 2002. — С. 93. — ISBN 3-540-44141-7.
↑ William Kolakoski. Problem 5304 (англ.) // American Mathematical Monthly. — 1965. — Vol. 72. — P. 674.
↑ Rufus Oldenburger. Exponent trajectories in symbolic dynamics (англ.) // Transactions of the American Mathematical Society. — 1939. — Vol. 46. — P. 453—466.
↑ ¹ ² Clark Kimberling. Integer Sequences and Arrays (неопр.). University of Evansville (13 октября 2016). Дата обращения: 9 августа 2018. Архивировано 13 ноября 2008 года.
↑ Václav Chvátal. Notes on the Kolakoski Sequence. — 1993. Архивная копия от 4 августа 2017 на Wayback Machine
↑ J. Nilsson. Letter Frequencies in the Kolakoski Sequence (неопр.) (24 апреля 2014). Дата обращения: 9 августа 2018. Архивировано 2 июня 2018 года.
↑ Johan Nilsson. A space-efficient algorithm for calculating the digit distribution in the Kolakoski sequence (англ.) // Journal of Integer Sequences. — No. 6. — P. 13. Архивировано 18 октября 2016 года.
↑ Kolakoski Sequence at MathWorld (неопр.) (16 июня 2017). Дата обращения: 9 августа 2018. Архивировано 11 августа 2018 года.

[1] N. Pytheas Fogg. Substitutions in dynamics, arithmetics and combinatorics. — Berlin: Springer-Verlag, 2002. — С. 93. — ISBN 3-540-44141-7.

[2] William Kolakoski. Problem 5304 (англ.) // American Mathematical Monthly. — 1965. — Vol. 72. — P. 674.

[3] Rufus Oldenburger. Exponent trajectories in symbolic dynamics (англ.) // Transactions of the American Mathematical Society. — 1939. — Vol. 46. — P. 453—466.

[:3-4] ¹ ² Clark Kimberling. Integer Sequences and Arrays (неопр.). University of Evansville (13 октября 2016). Дата обращения: 9 августа 2018. Архивировано 13 ноября 2008 года.

[5] Václav Chvátal. Notes on the Kolakoski Sequence. — 1993. Архивная копия от 4 августа 2017 на Wayback Machine

[6] J. Nilsson. Letter Frequencies in the Kolakoski Sequence (неопр.) (24 апреля 2014). Дата обращения: 9 августа 2018. Архивировано 2 июня 2018 года.

[7] Johan Nilsson. A space-efficient algorithm for calculating the digit distribution in the Kolakoski sequence (англ.) // Journal of Integer Sequences. — No. 6. — P. 13. Архивировано 18 октября 2016 года.

[8] Kolakoski Sequence at MathWorld (неопр.) (16 июня 2017). Дата обращения: 9 августа 2018. Архивировано 11 августа 2018 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]