последовательность Дуччи

Последовательность Дуччи — это последовательность из n кортежей , целых чисел иногда называемая «игрой Диффи», поскольку она основана на последовательностях.

Дан n целых чисел набор из $(a_{1},a_{2},...,a_{n})$, следующий n -кортеж в последовательности формируется путем взятия абсолютных разностей соседних целых чисел:

$(a_{1},a_{2},...,a_{n})\rightarrow (|a_{1}-a_{2}|,|a_{2}-a_{3}|,...,|a_{n}-a_{1}|)\,.$

Другой способ описания этого заключается в следующем. Расположите n целых чисел в круге и создайте новый круг, взяв разницу между соседями, игнорируя знаки минус; затем повторите операцию. Последовательности Дуччи названы в честь Энрико Дуччи (1864–1940), итальянского математика, который в 1930-х годах обнаружил, что каждая такая последовательность со временем становится периодической.

Последовательности Дуччи также известны как карта Дуччи или игра n чисел . Открытые проблемы в изучении этих карт остаются до сих пор.

Характеристики

Начиная со второго n -кортежа и далее, становится ясно, что каждое целое число в каждом n -кортеже последовательности Дуччи больше или равно 0 и меньше или равно разнице между максимальным и минимальным членами первого n- кортежа. кортеж. Поскольку существует только конечное число возможных n -кортежей с этими ограничениями, последовательность n-кортежей должна рано или поздно повториться. Таким образом, каждая последовательность Дуччи в конечном итоге становится периодической .

Если n является степенью 2, каждая последовательность Дуччи в конечном итоге достигает n -кортежа (0,0,...,0) за конечное число шагов.

Если n является не степенью двойки, последовательность Дуччи либо в конечном итоге достигнет n -кортежа нулей, либо превратится в периодический цикл из «двоичных» n -кортежей; то есть n -кортежей вида $k(b_{1},b_{2},...b_{n})$, $k$ является константой, и $b_{i}\in \{0,1\}$.

Очевидным обобщением последовательностей Дуччи является то, что членами n -кортежей могут быть любые действительные числа, а не просто целые числа. Например, этот четырехкортеж сходится к (0, 0, 0, 0) за четыре итерации: $(e,\pi ,{\sqrt {2}},1)\rightarrow (\pi -e,\pi -{\sqrt {2}},{\sqrt {2}}-1,e-1)\rightarrow (e-{\sqrt {2}},\pi -2{\sqrt {2}}+1,e-{\sqrt {2}},2e-\pi -1)\rightarrow$ $(\pi -e-{\sqrt {2}}+1,\pi -e-{\sqrt {2}}+1,\pi -e-{\sqrt {2}}+1,\pi -e-{\sqrt {2}}+1)\rightarrow (0,0,0,0)$

Представленные здесь свойства не всегда справедливы для этих обобщений. Например, последовательность Дуччи, начинающаяся с n -кортежа (1, q , q ² , q ³ ) где q — (иррациональный) положительный корень кубики $x^{3}-x^{2}-x-1=0$ не достигает (0,0,0,0) за конечное число шагов, хотя в пределе сходится к (0,0,0,0).

Примеры

Последовательности Дуччи могут быть сколь угодно длинными, прежде чем они достигнут кортежа нулей или периодического цикла. Последовательность из 4 кортежей, начинающаяся с (0, 653, 1854, 4063), требует 24 итераций для достижения кортежа нулей.

$(0,653,1854,4063)\rightarrow (653,1201,2209,4063)\rightarrow (548,1008,1854,3410)\rightarrow$ $\cdots \rightarrow (0,0,128,128)\rightarrow (0,128,0,128)\rightarrow (128,128,128,128)\rightarrow (0,0,0,0)$

Эта последовательность из 5 кортежей входит в двоичный «цикл» с периодом 15 после 7 итераций.

${\begin{matrix}15799\rightarrow &42208\rightarrow &20284\rightarrow &22642\rightarrow &04220\rightarrow &42020\rightarrow \\22224\rightarrow &00022\rightarrow &00202\rightarrow &02222\rightarrow &20002\rightarrow &20020\rightarrow \\20222\rightarrow &22000\rightarrow &02002\rightarrow &22022\rightarrow &02200\rightarrow &20200\rightarrow \\22202\rightarrow &00220\rightarrow &02020\rightarrow &22220\rightarrow &00022\rightarrow &\cdots \quad \quad \\\end{matrix}}$

Следующая последовательность из 6 кортежей показывает, что последовательности кортежей, длина которых не является степенью двойки, все равно могут достигать кортежа нулей:

${\begin{matrix}121210\rightarrow &111111\rightarrow &000000\\\end{matrix}}$

Если к любой последовательности Дуччи, состоящей из кортежа «степени двойки», наложены некоторые условия, для достижения кортежа нулей потребуется эта степень двух или меньших итераций. Предполагается, что эти последовательности соответствуют правилу.

Форма по модулю два

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

$(|a_{1}-a_{2}|,|a_{2}-a_{3}|,...,|a_{n}-a_{1}|)\ =(a_{1}+a_{2},a_{2}+a_{3},...,a_{n}+a_{1}){\bmod {2}}$

Это составляет основу для доказательства того, что последовательность обращается в нуль.

Клеточные автоматы

Линейную карту по модулю 2 можно далее идентифицировать как клеточный автомат, обозначенный как правило 102 в коде Вольфрама и связанный с правилом 90 через карту Мартина-Одлизко-Вольфрама. Правило 102 воспроизводит треугольник Серпинского .

Другие связанные темы

Карта Дуччи является примером разностного уравнения , категории, которая также включает нелинейную динамику , теорию хаоса и численный анализ . сходство с круговыми полиномами . Также было отмечено Хотя в настоящее время карта Дуччи не имеет практического применения, ее связь с широко применяемой областью разностных уравнений привела к предположить, что форма карты Дуччи также может найти применение в будущем.

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

• Последовательность Дуччи, заархивированная 26 августа 2004 г. в Wayback Machine.
• Целочисленные итерации по кругу при разрезании узла