Последовательность Мозера – де Брейна

Число, сумма различных степеней 4

Таблица сложения, где и оба принадлежат последовательности Мозера – де Брёйна, и кривая Z-порядка , соединяющая суммы в числовом порядке. ${\displaystyle x+2y}$ ${\displaystyle x}$ ${\displaystyle y}$

В теории чисел последовательность Мозера -де Брюйна представляет собой целочисленную последовательность , названную в честь Лео Мозера и Николааса Говерта де Брейна , состоящую из сумм различных степеней 4. Эквивалентно, это числа, двоичные представления которых отличны от нуля только в четных позициях.

Числа Мозера –де Брейна в этой последовательности растут пропорционально квадратам чисел . Это квадраты для модифицированной формы арифметики без переноса . Разность двух чисел Мозера – де Брейна, умноженная на два, никогда не является квадратной. Каждое натуральное число может быть сформировано уникальным образом как сумма числа Мозера–де Брюйна и удвоенного числа Мозера–де Брюйна. Это представление в виде суммы определяет взаимно однозначное соответствие между целыми числами и парами целых чисел, перечисленных в порядке их положения на кривой Z-порядка .

Последовательность Мозера-де Брюйна можно использовать для построения пар трансцендентных чисел , которые являются мультипликативными обратными друг другу и оба имеют простые десятичные представления. Простое рекуррентное соотношение позволяет вычислять значения последовательности Мозера – де Брюйна на основе более ранних значений и может использоваться для доказательства того, что последовательность Мозера – де Брюйна является 2-регулярной последовательностью .

Определение и примеры

Числа в последовательности Мозера-де Брейна образуются путем сложения различных степеней четырех. В последовательности эти числа перечислены в отсортированном порядке; оно начинается ^[1]

0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85, 256, ... (последовательность A000695 в OEIS )

Например, число 69 принадлежит этой последовательности, поскольку оно равно 64 + 4 + 1, сумме трёх различных степеней 4.

Другое определение последовательности Мозера-де Брюйна состоит в том, что это упорядоченная последовательность чисел, двоичное представление которой имеет ненулевые цифры только в четных позициях. Например, 69 принадлежит последовательности, потому что ее двоичное представление 1000101 ₂ имеет ненулевые цифры в позициях 2 ⁶ , 2 ² и 2 ⁰ , все из которых имеют четные показатели. Числа в последовательности также можно описать как числа, представление которых по основанию 4 использует только цифры 0 или 1. ^[1] Для числа в этой последовательности представление по основанию 4 можно найти из двоичного представления, пропустив двоичные цифры в нечетных позициях, которые все должны быть равны нулю. Шестнадцатеричное представление этих чисел содержит только цифры 0, 1, 4, 5. Например, 69 = 1011 ₄ = 45 ₁₆ . Эквивалентно, это числа, двоичное и негабинарное представления которых равны. ^{[1] [2]} Поскольку в их двоичных представлениях нет двух последовательных ненулей, последовательность Мозера-де Брюйна образует подпоследовательность фиббинарных чисел .

Темпы роста и различия

График количества элементов последовательности до деленного на в логарифмическом горизонтальном масштабе ${\displaystyle n}$ ${\displaystyle {\sqrt {n}}}$

Из определения этих чисел либо в двоичном формате, либо в формате с основанием 4 следует, что они растут примерно пропорционально квадрату чисел . Число элементов в последовательности Мозера-де Брюйна, находящихся ниже любого заданного порога, пропорционально , ^​​[3] — факт, который также верен для квадратных чисел. Точнее, число колеблется между (для чисел вида ) и (для ). Фактически числа в последовательности Мозера-де Брюйна представляют собой квадраты для версии арифметики без двоичных чисел, в которой сложение и умножение отдельных битов являются соответственно операциями исключения или логического соединения . ^[4] ${\displaystyle n}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle n=4^{k}}$ ${\displaystyle {\sqrt {3n}}}$ ${\displaystyle n\sim 4^{k}/3}$

В связи с теоремой Фюрстенберга-Саркози о последовательностях чисел без квадратичной разности Имре З. Ружа нашел конструкцию для больших множеств без квадратных разностей, которая, как и двоичное определение последовательности Мозера-де Брюйна, ограничивает цифры в чередование позиций в базовых числах. ^[5] Применительно к базе конструкция Ружи генерирует последовательность Мозера-де Брейна, умноженную на два, набор, который снова не содержит квадратичных разностей. Однако это множество слишком разрежено, чтобы обеспечить нетривиальные оценки снизу для теоремы Фюрстенберга–Саркози. ${\displaystyle b}$ ${\displaystyle b=2}$

Уникальное представление в виде сумм

Последовательность Мозера-де Брёйна обладает свойством , аналогичным свойству последовательности Сидона : суммы и обе принадлежат последовательности Мозера-де Брёйна, все уникальны. Никакие две из этих сумм не имеют одинакового значения. Более того, каждое целое число можно представить в виде суммы , где и оба принадлежат последовательности Мозера – де Брейна. Чтобы найти сумму, которая представляет , вычислите побитовое логическое значение и of с двоичным значением (выраженным здесь в шестнадцатеричном виде ), которое имеет единицы во всех четных позициях, и установите . ^{[1] [6]} ${\displaystyle x+2y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle n}$ ${\displaystyle x+2y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle n}$ ${\displaystyle x=n\ \&\ \mathrm {0x55555555} }$ ${\displaystyle n}$ ${\displaystyle y=(n-x)/2}$

Последовательность Мозера-де Брюйна — единственная последовательность, обладающая этим свойством: все целые числа имеют уникальное выражение как . Именно по этой причине последовательность первоначально изучалась Мозером (1962). ^[7] Расширяя это свойство, Де Брейн (1964) обнаружил бесконечное множество других линейных выражений, подобных этому, когда и оба принадлежат последовательности Мозера – де Брюйна, однозначно представляют все целые числа. ^{[8] [9]} ${\displaystyle x+2y}$ ${\displaystyle x+2y}$ ${\displaystyle x}$ ${\displaystyle y}$

Кривая Z-порядка и формула преемника

Разложение числа на , а затем применение к и сохраняющего порядок отображения последовательности Мозера – де Брейна на целые числа (путем замены степеней четырех в каждом числе соответствующими степенями двойки) дает биекцию из неотрицательных целых чисел. к упорядоченным парам неотрицательных целых чисел. Обратная биекция дает линейный порядок точек плоскости с неотрицательными целочисленными координатами, которые можно использовать для определения кривой Z-порядка . ^{[1] [10]} ${\displaystyle n}$ ${\displaystyle n=x+2y}$ ${\displaystyle x}$ ${\displaystyle y}$

В связи с этим приложением удобно иметь формулу для генерации каждого последующего элемента последовательности Мозера-де Брейна из его предшественника. Это можно сделать следующим образом. Если является элементом последовательности, то следующий за ним член можно получить, заполнив биты в нечетных позициях двоичного представления единицами, добавив единицу к результату и затем замаскировав заполненные биты. Заполнение битов и добавление одного можно объединить в одну операцию сложения. То есть следующим членом является число, заданное формулой ^{[1] [6] [10]} Две шестнадцатеричные константы, входящие в эту формулу, можно интерпретировать как 2-адические числа и соответственно. ^[1] ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ $${\displaystyle \displaystyle (x+{\textrm {0xaaaaaaab}})\ \&\ {\textrm {0x55555555}}.}$$ ${\displaystyle 1/3}$ ${\displaystyle -1/3}$

Игра на вычитание

Голомб (1966) исследовал игру на вычитание , аналогичную вычитанию квадрата , основанную на этой последовательности. В игре Голомба два игрока по очереди вынимают монеты из кучки монет. За каждый ход игрок может убрать любое количество монет, принадлежащих последовательности Мозера – де Брейна. Удаление любого другого количества монет не допускается. Победителем становится тот игрок, который уберет последнюю монету. Как замечает Голомб, «холодные» позиции этой игры (те, в которых проигрывает игрок, собирающийся сделать ход) — это в точности позиции формы, принадлежащей последовательности Мозера–де Брейна. Выигрышная стратегия в этой игре состоит в том, чтобы разложить текущее количество монет, , на где и оба принадлежат последовательности Мозера-де Брюйна, а затем (если ненулевое) удалить монеты, оставив холодную позицию другому игроку. Если равен нулю, эта стратегия невозможна и выигрышного хода нет. ^[3] ${\displaystyle n}$ ${\displaystyle 2y}$ ${\displaystyle y}$ ${\displaystyle n}$ ${\displaystyle x+2y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$

Десятичные обратные величины

Последовательность Мозера-де Брюйна составляет основу примера иррационального числа с необычным свойством, которое дает десятичное представление, и которое может быть записано просто и явно. Обозначим через саму последовательность Мозера–де Брейна. Тогда для десятичного числа, чьи ненулевые цифры находятся в позициях, заданных последовательностью Мозера-де Брюйна, отсюда следует, что ненулевые цифры его обратного числа расположены в позициях 1, 3, 9, 11, ..., заданных удвоением числа числа и прибавление ко всем единицам: ^{[11] [12]} ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle 1/x}$ ${\displaystyle E}$ $${\displaystyle x=3\sum _{n\in E}10^{-n}=3.300330000000000330033\dots ,}$$ ${\displaystyle E}$ $${\displaystyle {\frac {1}{x}}=3\sum _{n\in E}10^{-2n-1}=0.30300000303\dots \ .}$$

Альтернативно можно написать: $${\displaystyle \displaystyle \left(\sum _{n\in E}10^{-n}\right)\left(\sum _{n\in E}10^{-2n}\right)={\frac {10}{9}}.}$$

Подобные примеры работают и в других базах. Например, два двоичных числа , чьи ненулевые биты находятся в тех же позициях, что и ненулевые цифры двух десятичных чисел, приведенных выше, также являются иррациональными обратными величинами. ^[13] Эти двоичные и десятичные числа, а также числа, определенные таким же образом для любой другой основы путем повторения одной ненулевой цифры в позициях, заданных последовательностью Мозера-де Брюйна, являются трансцендентными числами . Их трансцендентность может быть доказана тем фактом, что длинные цепочки нулей в их цифрах позволяют более точно аппроксимировать их рациональными числами , чем это было бы разрешено теоремой Рота, если бы они были алгебраическими числами , имеющими меру иррациональности не менее 3. ^{[12] ]}

Генерирующая функция

Производящая функция , показатели которой в расширенном виде заданы последовательностью Мозера – де Брюйна, подчиняется функциональным уравнениям ^{[1] [2]} и ^[14]. Например, эту функцию можно использовать для описания двух десятичных обратных величин, приведенных выше: одно есть и другое есть . Тот факт, что они являются обратными величинами, является примером первого из двух функциональных уравнений. Частичные произведения формы произведения производящей функции можно использовать для создания подходящих дробей разложения в непрерывную дробь самих этих чисел, а также кратных им. ^[11] $${\displaystyle F(x)=\prod _{i=0}^{\infty }(1+x^{4^{i}})=1+x+x^{4}+x^{5}+x^{16}+x^{17}+\cdots ,}$$ $${\displaystyle F(x)F(x^{2})={\frac {1}{1-x}}}$$ $${\displaystyle F(x)=(1+x)F(x^{4}).}$$ ${\displaystyle 3F(1/10)}$ ${\displaystyle {\tfrac {3}{10}}F(1/100)}$

Повторяемость и регулярность

Последовательность Мозера-де Брюйна подчиняется рекуррентному соотношению , которое позволяет определить n -е значение последовательности (начиная с ) из значения в позиции : Итерация этой рекуррентности позволяет выразить любую подпоследовательность формы как линейную функцию от исходная последовательность, что означает, что последовательность Мозера – де Брюйна является 2-регулярной последовательностью . ^[15] ${\displaystyle S(n)}$ ${\displaystyle S(0)=0}$ ${\displaystyle \lfloor n/2\rfloor }$ $${\displaystyle {\begin{aligned}S(2n)&=4S(n)\\S(2n+1)&=4S(n)+1\end{aligned}}}$$ ${\displaystyle S(2^{i}n+j)}$

Смотрите также

• Последовательность Стэнли и множество Кантора , наборы, определенные аналогичным образом с использованием представлений их элементов по основанию 3.

Примечания

1. Слоан, Нью-Джерси (редактор), «Последовательность A000695 (последовательность Мозера – Де Брёйна)», Интернет -энциклопедия целочисленных последовательностей , Фонд OEIS
2. Арндт, Йорг (2011), Вопросы вычислений: идеи, алгоритмы, исходный код (PDF) , Springer, стр. 59, 750.
3. Голомб, Соломон В. (1966), «Математическое исследование игр «на вынос»", Журнал комбинаторной теории , 1 (4): 443–458, doi : 10.1016/S0021-9800(66)80016-9 , MR  0209015..
4. Эпплгейт, Дэвид ; ЛеБрун, Марк; Слоан, Нью-Джерси (2011), «Мрачная арифметика» (PDF) , Журнал целочисленных последовательностей , 14 (9): Статья 11.9.8, 34, arXiv : 1107.1130 , Бибкод : 2011arXiv1107.1130A, MR  2859992.
5. Ружа, ИЗ (1984), «Разностные множества без квадратов», Periodica Mathematica Hungarica , 15 (3): 205–209, doi : 10.1007/BF02454169, MR  0756185, S2CID  122624503.
6. Константы в этой формуле выражаются в шестнадцатеричном формате и основаны на 32-битном размере слова. Один и тот же битовый шаблон должен быть расширен или уменьшен очевидным образом для обработки слов других размеров.
7. Мозер, Лео (1962), «Применение порождающих рядов», Mathematics Magazine , 35 (1): 37–38, doi : 10.1080/0025570X.1962.11975291, JSTOR  2689100, MR  1571147.
8. Де Брейн, Н.Г. (1964), «Некоторые прямые разложения множества целых чисел», Mathematics of Computation , 18 (88): 537–546, doi : 10.2307/2002940 , JSTOR  2002940, MR  0167447.
9. Эйген, SJ; Ито, Ю.; Прасад, В.С. (2004), «Универсально плохие целые числа и 2-адики», Журнал теории чисел , 107 (2): 322–334, doi : 10.1016/j.jnt.2004.04.001 , MR  2072392.
10. Тиягалингам, Джеяраджан; Бекманн, Олав; Келли, Пол Х.Дж. (сентябрь 2006 г.), «Является ли макет Мортона конкурентоспособным для больших двумерных массивов?» (PDF) , Параллелизм и вычисления: практика и опыт , 18 (11): 1509–1539, doi :10.1002/cpe.v18:11, заархивировано из оригинала (PDF) 29 марта 2017 г. , получено 11 ноября 2016 г. 18.
11. ван дер Поортен, AJ (1993), «Продолжительные дроби формальных степенных рядов» (PDF) , Достижения в теории чисел (Кингстон, Онтарио, 1991) , Oxford Sci. Публикация, Оксфордский университет. Пресс, Нью-Йорк, стр. 453–466, MR  1368441..
12. Бланшар, Андре; Мендес Франс, Мишель (1982), «Симетрия и трансцендентность», Bulletin des Sciences Mathématiques , 106 (3): 325–335, MR  0680277. Цитируется ван дер Портеном (1993).
13. Бэйли, Дэвид Х .; Борвейн, Джонатан М .; Крэндалл, Ричард Э .; Померанс, Карл (2004), «О двоичных разложениях алгебраических чисел», Journal de Théorie des Nombres de Bordeaux , 16 (3): 487–518, doi : 10.5802/jtnb.457 , hdl : 1959.13/1037857 , MR  2144954 , S2CID  122848891. См., в частности, обсуждение после теоремы 4.2.
14. Лемер, Д.Х .; Малер, К .; ван дер Поортен, AJ (1986), «Целые числа с цифрами 0 или 1», Mathematics of Computation , 46 (174): 683–689, doi : 10.2307/2008006, JSTOR  2008006, MR  0829638.
15. Аллуш, Жан-Поль; Шалит, Джеффри (1992), «Кольцо k -регулярных последовательностей», Theoretical Computer Science , 98 (2): 163–197, doi : 10.1016/0304-3975(92)90001-V, MR  1166363. Пример 13, с. 188.

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

• Вайсштейн, Эрик В. , «Последовательность Мозера – Де Брёйна», MathWorld