Войти
Визуализация от 3-го до 50-го членов последовательности Колакоски в виде спирали. Термины начинаются с точки в середине спирали. В следующем обороте каждая дуга повторяется, если член равен 1, или делится на две равные половины, если это 2. Первые два члена не могут быть показаны, поскольку они являются самореферентными. В изображении SVG наведите указатель мыши на дугу или метку, чтобы выделить его и показать его статистику. В математике, последовательность Колакоски, иногда также известная поскольку последовательность Ольденбургера-Колакоски, представляет собой бесконечную последовательность символов {1,2}, которая представляет собой последовательность длин серий в ее собственном кодировании длин серий, и прототип бесконечного семейства связанных последовательностей. Он назван в честь математика-любителя Уильяма Колакоски (1944–97), который описал его в 1965 году, но последующие исследования показали, что последовательность ранее обсуждалась Руфусом Ольденбургером в 1939 году.
последовательность Колакоски описывает ее собственную длину серии Начальный тер ms последовательности Колакоски:
Каждый символ встречается в «серии» (последовательность равных элементов) одного или двух последовательных членов, и запись длин этих прогонов дает точно такую же последовательность:
Следовательно, описание последовательности Колакоски обратимо. Если K означает «последовательность Колакоски», описание №1 логически подразумевает описание №2 (и наоборот):
Соответственно, можно сказать, что каждый член последовательности Колакоски порождает серию из одного или двух будущих членов. Первая 1 последовательности генерирует серию «1», то есть сама; первые 2 генерируют серию «22», которая включает себя; вторые 2 генерируют серию «11»; и так далее. Каждое число в последовательности - это длина следующего прогона, который должен быть сгенерирован, а генерируемый элемент чередуется между 1 и 2:
Как видно, длина последовательности на каждом этапе равна сумме членов на предыдущем этапе. Эта анимация иллюстрирует процесс:
Эти самогенерируемые свойства, которые остаются, если последовательность записана без начальной единицы, означают, что последовательность Колакоски может быть описана как фрактал или математический объект, который кодирует собственное представление в других масштабах. Бертран Стейнски создал рекурсивную формулу для i-го члена последовательности, но эта последовательность считается апериодической, то есть ее члены не имеют общего повторяющегося образца (см. иррациональный числа, например π и √2 ).
Последовательность Колакоски является прототипом бесконечного семейства других последовательностей, каждая из которых является собственной кодировкой длин серий. Каждая последовательность основана на том, что формально называется алфавитом целых чисел. Например, описанная выше классическая последовательность Колакоски имеет алфавит {1,2}. Некоторые из дополнительных последовательностей Колакоски, перечисленных в OEIS :
Подобно {1,2} -последовательности Колакоски, запись run-lengths возвращает ту же последовательность. В общем, любой алфавит целых чисел, {n 1,n2,.. n i }, может генерировать последовательность Колакоски, если то же целое число не встречается 1) дважды и более подряд; 2) в начале и в конце алфавита. Например, альп habet {3,1,2} порождает:
И алфавит {2,1, 3,1} генерирует:
Опять же, запись длин серий возвращает ту же последовательность.
Последовательности Колакоски также могут быть созданы из бесконечных алфавитов целых чисел, таких как {1,2,1,3,1,4,1,5,... }:
Бесконечный алфавит {1,2,3,4,5,...} порождает последовательность Голомба :
Последовательность Колакоски также может быть создана из целых чисел, выбранных случайным образом из конечного алфавита, с ограничением, что одно и то же число не может быть выбрано дважды подряд. Если конечный алфавит равен { 1,2,3}, возможна следующая последовательность:
Фактически, последовательность основана на бесконечном алфавите {2,1,3,1,3,2,1,2,1,3,2,...}, который содержит случайная последовательность единиц, двоек и троек, из которых удалены повторы.
В то время как классическая {1,2} -последовательность Колакоски генерирует сама себя, эти две последовательности генерируют друг друга:
Другими словами, если вы запишете длины серий первой последовательности, вы создадите вторую ; если вы записываете длины серий второй, вы генерируете первую. В следующей цепочке из трех последовательностей длины серий каждой генерируют следующую в порядке 1 → 2 → 3 → 1:
Последовательности используют целочисленный алфавит {1,2,3}, но каждая начинается с разные точки в алфавите. Следующие пять последовательностей образуют аналогичную цепочку с использованием алфавита {1,2,3,4,5}:
Однако, чтобы создать последовательность-цепочку длины l, необязательно иметь различные целые алфавиты размера l. Например, алфавитный ряд {2,1}, {1,2}, {1,2}, {1,2} и {1,2} достаточен для пятизвенной цепи:
Каждая последовательность уникальна и длины прогонов каждого из них генерируют члены следующей последовательности в цепочке. Целочисленные алфавиты, используемые для создания цепочки, также могут быть разных размеров. Зеркало Колакоски (так можно назвать двухзвенную цепочку) можно создать из алфавитов {1,2} и {1,2,3,4,5}:
Кажется правдоподобным, что плотность единиц в {1,2} -последовательности Колакоски равна 1/2, но это предположение остается недоказанным. Вацлав Хватал доказал, что верхняя плотность единиц меньше чем 0.50084. Нильссон использовал тот же метод с гораздо большей вычислительной мощностью, чтобы получить границу 0,500080.
Хотя расчеты первых 3 × 10 значений последовательности показали, что ее плотность сходится к значению, немного отличающемуся от 1/2, более поздние расчеты, которые расширили последовательность до первых 10 значений, показывают, что отклонение от плотности 1/2 становится меньше, как и следовало ожидать, если на самом деле предельная плотность равна 1/2.
Стивен Вольфрам описывает последовательность Колакоски в связи с историей циклических систем тегов.
Некоторые обсуждения классической последовательности Колакоски утверждают, что, написанные с помощью или без начального 1, это «единственная последовательность», которая является ее собственным кодированием длины серии, или единственная такая последовательность, которая начинается с 1. Как видно выше, это неверно: бесконечное количество дополнительных последовательностей обладает этими свойствами. Однако {1,2} - и {2,1} -последовательности Колакоски являются единственными такими последовательностями, в которых используются только целые числа 1 и 2.
-Последовательность Колакоски, длины единиц и двоек никогда не совпадают с членами исходной последовательности:
Как можно видеть, длины серий антиколакосковской последовательности возвращают Колакоски { 1,2} -последовательность, что означает, что первая может быть создана из последней простым вычитанием. Если k (i) является i-м членом {1,2} -последовательности Колакоски, а ak (i) является i-й член последовательности анти-Колакоски, тогда ak (i) = 3-k (i), так же как k (i) = 3-ak (i). Соответственно, как и последовательность Колакоски, последовательность анти-Колакоски сохраняет свое определяющее свойство, когда записывается без своего начального члена, то есть 2.
Так называемая константа Колакоски создается путем вычитания 1 от каждого члена {2,1} -последовательности Колакоски (которая начинается с 22112122122...) и обработки результата как двоичной дроби.
Последовательность Колакоски {1,2} может быть сгенерирована алгоритмом , который на i-й итерации считывает значение x i, которое уже было выведено. в качестве i-го значения последовательности (или, если такое значение еще не было выведено, устанавливает x i = i). Затем, если i нечетно, он выводит x i копий числа 1, а если i четно, он выводит x i копий числа 2. Таким образом, первые несколько шаги алгоритма:
Этот алгоритм занимает линейное время, но, поскольку ему нужно вернуться к более ранним позициям в последовательности, ему необходимо сохранить всю последовательность, занимая линейное пространство. Альтернативный алгоритм, который генерирует несколько копий последовательности с разной скоростью, причем каждая копия последовательности использует выходные данные предыдущей копии для определения того, что делать на каждом шаге, может использоваться для генерации последовательности за линейное время и только логарифмический пробел.
В общем, последовательность Колакоски для любого целочисленного алфавита {n 1, n 2,.. n j } может быть сгенерировано алгоритмом , который на i-й итерации считывает значение x i, которое уже было выведено как i-е значение последовательности (или, если такое значение еще не было выведено, устанавливает x i = n i). На каждом этапе вывод n i регулируется в соответствии с размером алфавита, возвращаясь к n 1, когда конечная позиция в алфавите превышена. Первые несколько шагов алгоритма для алфавита {1,2,3,4}:
Результирующая последовательность:
Цепи Колакоски любой желаемой длины могут быть сгенерированы с помощью простого алгоритма. Предположим, что кто-то желает сгенерировать цепочку из 3 последовательностей, в которых условия seq ( i) генерируются длинами серий seq (i + 1), а алфавит равен {1,2}. Начните с установки первого члена seq (1), начальной последовательности в цепочке, на значение 2.Следующая последовательность в цепочке, seq (2), длины серий которой генерируют члены seq (1), поэтому должна иметь члены (1,1). Следовательно, seq (3), длины серий которой генерируют seq ( 2) = (1,1), должен иметь прогоны (1,2). Вот первый этап алгоритма:
Теперь обратите внимание, что длины серий seq (1) порождают члены seq (3), что означает что члены seq (3) порождают серии seq (1). Поскольку seq (3) = (1,2) после этапа 1 алгоритма, seq (1) должен быть равен (2,1,1) на следующем этапе. Из этого расширенного seq (1) можно сгенерировать дальнейшие прогоны (и члены) seq (2), затем дальнейшие прогоны (и члены) seq (3):
Теперь используйте термины seq (3) на этапе 2 для генерации дальнейших прогонов seq (1) на этапе 3:
Теперь последовательности можно переупорядочить так, чтобы длины серий seq (i) сгенерировать члены seq (i + 1) (где seq (3 + 1) = seq (1)):
Если в цепочке 5 последовательностей, алгоритм выдает следующие этапы:
Наконец, последовательности перегруппированы так что длины серий seq (i) порождают члены seq (i + 1):
