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

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

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

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

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

Числа в последовательности Мозера – де Брюйна образуются путем сложения различных степеней 4. В последовательности эти числа перечислены в отсортированном порядке; это начинается ^{[ 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 можно найти из двоичного представления, пропуская двоичные цифры в нечетных позициях, которые все должны быть равны нулю. Шестнадцатеричное 4 представление этих чисел содержит только цифры 0, 1, 4, 5. Например, 69 = 1011 ₌ 45 ₁₆ . Эквивалентно, это числа, двоичное и негабинарное представления которых равны. ^{[ 1 ]}^{[ 2 ]} Поскольку в их двоичных представлениях нет двух последовательных ненулевых чисел, последовательность Мозера-де Брюйна образует подпоследовательность фиббинарных чисел .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Примечания

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

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

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

[oeis-1] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час Слоан, Нью-Джерси (редактор), «Последовательность A000695 (последовательность Мозера – Де Брёйна)» , Интернет -энциклопедия целочисленных последовательностей , Фонд OEIS

[arndt-2] Jump up to: ^а ^б Арндт, Йорг (2011), «Вычислительные вопросы: идеи, алгоритмы, исходный код» (PDF) , Springer, стр. 59, 750 .

[golomb-3] Jump up to: ^а ^б Голомб, Соломон В. (1966), «Математическое исследование игр на вынос» , Журнал комбинаторной теории , 1 (4): 443–458, doi : 10.1016/S0021-9800(66)80016-9 , МР 0209015 .

[als-4] Эпплгейт, Дэвид ; ЛеБрун, Марк; Слоан, Нью-Джерси (2011), «Мрачная арифметика» (PDF) , Журнал целочисленных последовательностей , 14 (9): Статья 11.9.8, 34, arXiv : 1107.1130 , Bibcode : 2011arXiv1107.1130A , MR 2859992 .

[ruzsa-5] Ружа, Из (1984), «Разностные множества без квадратов», Periodica Mathematica Hungarica , 15 (3): 205–209, doi : 10.1007/BF02454169 , MR 0756185 , S2CID 122624503 .

[32bit-6] Jump up to: ^а ^б Константы в этой формуле выражаются в шестнадцатеричном формате и основаны на 32-битном размере слова. Один и тот же битовый шаблон должен быть расширен или уменьшен очевидным образом для обработки слов других размеров.

[moser-7] Мозер, Лео (1962), «Применение порождающих рядов», Mathematics Magazine , 35 (1): 37–38, doi : 10.1080/0025570X.1962.11975291 , JSTOR 2689100 , MR 1571147 .

[debruijn-8] Де Брёйн, Н.Г. (1964), «Некоторые прямые разложения множества целых чисел», Mathematics of Computation , 18 (88): 537–546, doi : 10.2307/2002940 , JSTOR 2002940 , MR 0167447 .

[eip-9] Эйген, С.Дж.; Ито, Ю.; Прасад, В.С. (2004), «Универсально плохие целые числа и 2-адики», Journal of Number Theory , 107 (2): 322–334, doi : 10.1016/j.jnt.2004.04.001 , MR 2072392 .

[morton-10] Jump up to: ^а ^б Тиягалингам, Джеяраджан; Бекманн, Олав; Келли, Пол Х.Дж. (сентябрь 2006 г.), «Является ли макет Мортона конкурентоспособным для больших двумерных массивов?» (PDF) , Параллелизм и вычисления: практика и опыт , 18 (11): 1509–1539, doi : 10.1002/cpe.v18:11 , заархивировано из оригинала (PDF) 29 марта 2017 г. , получено 11 ноября 2016 г. 18 .

[vdp-11] Jump up to: ^а ^б ван дер Поортен, А.Дж. (1993), «Продолжительные дроби формальных степенных рядов» (PDF) , Достижения в теории чисел (Кингстон, Онтарио, 1991) , Oxford Sci. Публикация, Оксфордский университет. Пресс, Нью-Йорк, стр. 453–466, MR 1368441 .

[bmf-12] Jump up to: ^а ^б Бланшар, Андре; Мендес Франс, Мишель (1982), «Симетрия и трансцендентность», Bulletin des Sciences Mathématiques , 106 (3): 325–335, MR 0680277 . Цитируется ван дер Портеном (1993) .

[bbcp-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.

[lmp-14] Лемер, ДХ ; Малер, К .; ван дер Поортен, AJ (1986), «Целые числа с цифрами 0 или 1», Mathematics of Computation , 46 (174): 683–689, doi : 10.2307/2008006 , JSTOR 2008006 , MR 0829638 .

[as-15] Аллуш, Жан-Поль; Шалит, Джеффри (1992), «Кольцо $k$ -регулярных последовательностей», Theoretical Computer Science , 98 (2): 163–197, doi : 10.1016/0304-3975(92)90001-V , MR 1166363 . Пример 13, с. 188.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]