Последовательность Колакоски
В математике последовательность Колакоски , иногда также известная как последовательность Ольденбургера-Колакоски , [1] — это бесконечная последовательность символов {1,2}, которая представляет собой последовательность длин серий в собственной кодировке длин серий . [2] Он назван в честь математика-любителя Уильяма Колакоски (1944–97), описавшего его в 1965 году. [3] но ранее это обсуждалось Руфусом Ольденбургером в 1939 году. [1] [4]
Определение
[ редактировать ]
Начальные члены последовательности Колакоски:
Каждый символ встречается в «серии» (последовательности равных элементов) одного или двух последовательных терминов, и запись длин этих серий дает точно такую же последовательность:
- 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 ,2, 1,1 ,2,1, 2,2 ,1, 2,2 , 1,1 ,2,1, 2,2 ,...
- 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, 2 ,...
Таким образом, описание последовательности Колакоски обратимо. Если K означает «последовательность Колакоски», описание №1 логически подразумевает описание №2 (и наоборот):
- 1. Члены K порождаются сериями (т. е. длинами серий) K
- 2. Серии K порождаются членами K
Соответственно, можно сказать, что каждый член последовательности Колакоски порождает серию из одного или двух будущих членов. Первая единица последовательности генерирует серию «1», т.е. саму себя; первые 2 генерируют серию «22», которая включает себя; вторые 2 генерируют серию «11»; и так далее. Каждое число в последовательности представляет собой длину следующего генерируемого прогона, а элемент генерируемый чередуется между 1 и 2:
- 1,2 (длина последовательности l = 2; сумма слагаемых s = 3)
- 1,2,2 ( л = 3, с = 5)
- 1,2,2,1,1 ( л = 5, с = 7)
- 1,2,2,1,1,2,1 ( l = 7, s = 10)
- 1,2,2,1,1,2,1,2,2,1 ( л = 10, с = 15)
- 1,2,2,1,1,2,1,2,2,1,2,2,1,1,2 ( л = 15, с = 23)
Как видно, длина последовательности на каждом этапе равна сумме слагаемых на предыдущем этапе. Эта анимация иллюстрирует процесс:
Эти самогенерирующиеся свойства, сохраняющиеся, если последовательность записана без начальной единицы, означают, что последовательность Колакоски можно описать как фрактал или математический объект, кодирующий собственное представление в других масштабах. [1] Бертран Стайнски создал рекурсивную формулу для i -го члена последовательности [5] но предполагается, что последовательность апериодическая , [6] то есть его члены не имеют общего повторяющегося шаблона (ср. иррациональные числа, такие как π и √ 2 ).
Исследовать
[ редактировать ]Плотность
[ редактировать ]Кажется правдоподобным, что плотность единиц в {1,2}-последовательности Колакоски равна 1/2, но эта гипотеза остается недоказанной. [6] Вацлав Хватал доказал, что верхняя плотность единиц меньше 0,50084. [7] Нильссон использовал тот же метод с гораздо большей вычислительной мощностью, чтобы получить границу 0,500080. [8]
Хотя расчеты первых 3×10 8 значения последовательности, казалось, показывали, что ее плотность приближается к значению, немного отличающемуся от 1/2, [5] более поздние вычисления расширили последовательность до первых 10 13 Значения показывают, что отклонение от плотности 1/2 становится меньше, как и следовало ожидать, если бы предельная плотность на самом деле составляла 1/2. [9]
Связь с системами тегов
[ редактировать ]Последовательность Колакоски также можно описать как результат простой циклической системы тегов . Однако, поскольку эта система представляет собой систему с двумя тегами, а не с одним тегом (то есть она заменяет пары символов другими последовательностями символов, а не работает с одним символом за раз), она находится в области параметры, для которых системы тегов являются полными по Тьюрингу , что затрудняет использование этого представления для рассуждения о последовательности. [10]
Алгоритмы
[ редактировать ]Последовательность Колакоски может быть сгенерирована с помощью алгоритма , который на i -й итерации считывает значение x i , которое уже было выведено, как i -е значение последовательности (или, если такое значение еще не было выведено, устанавливает Икс я знак равно я ). Затем, если i нечетное число, он выводит x i копий числа 1, а если i четное, он выводит x i копий числа 2.Таким образом, первые несколько шагов алгоритма таковы:
- Первое значение еще не выведено, поэтому установите x 1 = 1 и выведите 1 копию числа 1.
- Второе значение еще не выведено, поэтому установите x 2 = 2 и выведите 2 копии числа 2.
- Третье значение x 3 на втором шаге было выведено как 2, поэтому выведите 2 копии числа 1.
- Четвертое значение x 4 было выведено как 1 на третьем шаге, поэтому выведите 1 копию числа 2. И т.д.
Этот алгоритм требует линейного времени , но поскольку ему необходимо вернуться к более ранним позициям в последовательности, ему необходимо сохранить всю последовательность, занимая линейное пространство. Альтернативный алгоритм, который генерирует несколько копий последовательности с разной скоростью, при этом каждая копия последовательности использует выходные данные предыдущей копии для определения того, что делать на каждом шаге, может использоваться для генерации последовательности в линейном времени и только в логарифмическом пространстве. . [9]
См. также
[ редактировать ]- Последовательность Голомба - еще одна самогенерирующаяся последовательность, основанная на длине серии.
- Последовательность Гейсвейта
- Последовательность «посмотри и скажи»
Примечания
[ редактировать ]- ^ Jump up to: Перейти обратно: а б с Слоан, Нью-Джерси (ред.). «Последовательность A000002 (последовательность Колакоски: a(n) — длина n-го прогона; a(1) = 1; последовательность состоит только из единиц и двоек)» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.
- ^ Пифей Фогг, Н. (2002). Берта, Валери ; Ференци, Себастьян; Модуит, Кристиан; Сигел, А. (ред.). Замены в динамике, арифметике и комбинаторике . Конспект лекций по математике. Том. 1794. Берлин: Springer-Verlag . п. 93. ИСБН 3-540-44141-7 . Збл 1014.11015 .
- ^ Колакоски, Уильям (1965). «Проблема 5304». Американский математический ежемесячник . 72 :674. дои : 10.2307/2313883 . JSTOR 2313883 . Частичное решение см. Учолук, Недждет (1966). «Самогенерирующие прогоны». Американский математический ежемесячник . 73 : 681–682. дои : 10.2307/2314839 . JSTOR 2314839 .
- ^ Ольденбургер, Руфус (1939). «Показательные траектории в символической динамике». Труды Американского математического общества . 46 (3): 453–466. дои : 10.2307/1989933 . JSTOR 1989933 . МР 0000352 .
- ^ Jump up to: Перейти обратно: а б Стайнский, Бертран (2006). «Рекурсивная формула для последовательности Колакоски A000002» (PDF) . Журнал целочисленных последовательностей . 9 (3). Статья 06.3.7. Бибкод : 2006JIntS...9...37S . МР 2240857 . Збл 1104.11012 .
- ^ Jump up to: Перейти обратно: а б Кимберлинг, Кларк . «Целочисленные последовательности и массивы» . Университет Эвансвилля . Проверено 13 октября 2016 г.
- ^ Хватал, Васек (декабрь 1993 г.). Заметки о последовательности Колакоски . Технический отчет 93-84. ДИМАКС.
- ^ Нильссон, Дж. «Частота букв в последовательности Колакоски» (PDF) . Acta Physics Polonica А. Проверено 24 апреля 2014 г.
- ^ Jump up to: Перейти обратно: а б Нильссон, Йохан (2012). «Экономичный алгоритм расчета распределения цифр в последовательности Колакоски» (PDF) . Журнал целочисленных последовательностей . 15 (6): Статья 12.6.7, 13. MR 2954662 .
- ^ ван дер Портен, Эй Джей (1981). «Автоматы подстановки, функциональные уравнения и «алгебраические функции над конечным полем» ». Статьи по алгебре, анализу и статистике (Хобарт, 1981) . Современная математика. Том. 9. Провиденс, Род-Айленд: Американское математическое общество. стр. 307–312. МР 0655988 . См., в частности, стр. 308 .
Дальнейшее чтение
[ редактировать ]- Аллуш, Жан-Поль; Шалит, Джеффри (2003). Автоматические последовательности: теория, приложения, обобщения . Издательство Кембриджского университета . п. 337 . ISBN 978-0-521-82332-6 . Збл 1086.11015 .
- Деккинг, FM (1997). «Что такое дальний порядок в последовательности Колакоски?». В Moody, RV (ред.). Труды Института перспективных исследований НАТО, Ватерлоо, Онтарио, 21 августа – 1 сентября 1995 г. Дордрехт, Нидерланды: Клувер. стр. 115–125.
- Феду, Дж. М.; Фичи, Г. (2010). «Некоторые замечания о дифференцируемых последовательностях и рекурсивности» (PDF) . Журнал целочисленных последовательностей . 13 (3). Статья 10.3.2.
- Кин, MS (1991). «Эргодическая теория и сдвиги конечного типа». В Бедфорде, Т.; Кин, М. (ред.). Эргодическая теория, символическая динамика и гиперболические пространства . Оксфорд, Англия: Издательство Оксфордского университета. стр. 35–70.
- Лагариас, Дж. К. (1992). «Теория чисел и динамические системы» . В Берре, ЮАР (ред.). Необоснованная эффективность теории чисел . Провиденс, Род-Айленд: Американское математическое общество. стр. 35–72. ISBN 9780821855010 .
- Паун, Георге; Саломаа, Арто (1996). «Последовательности самочтения». Американский математический ежемесячник . 103 (2): 166–168. дои : 10.2307/2975113 . JSTOR 2975113 . Збл 0854.68082 .
- Шалит, Джеффри (1999). «Теория чисел и формальные языки». В Хейхале, Деннис А .; Фридман, Джоэл; Гуцвиллер, Мартин С .; Одлызко, Эндрю М. (ред.). Новые приложения теории чисел. По материалам летней программы IMA, Миннеаполис, Миннесота, США, 15–26 июля 1996 г. Тома IMA по математике и ее приложениям. Том. 109. Шпрингер-Верлаг . стр. 547–570. ISBN 0-387-98824-6 . Збл 0919.00047 .
Внешние ссылки
[ редактировать ]- Вайсштейн, Эрик В. «Последовательность Колакоски» . Математический мир .
- Константа Колакоски до 25000 цифр, вычисленная Оливье Жераром в апреле 1998 г.
- Беллос, Алекс . «Последовательность Колакоски» (видео) . Брэйди Харан . Архивировано из оригинала 21 декабря 2021 г. Проверено 24 июля 2017 г.