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

Moser–de Bruijn sequence
Таблица сложения для где и оба принадлежат последовательности Мозера – де Брейна, а Кривая Z-порядка который соединяет суммы в числовом порядке

В теория чисел, то Последовательность Мозера – де Брейна является целочисленная последовательность названный в честь Лео Мозер и Николаас Говерт де Брёйн, состоящий из сумм различных степеней 4. Он начинается

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 принадлежит последовательности, потому что ее двоичное представление 10001012 имеет ненулевые цифры в позициях для 26, 22, и 20, все из которых имеют четные показатели. Цифры в последовательности также можно описать как числа, представление по основанию 4 использует только цифры 0 или 1.[1] Для числа в этой последовательности представление с основанием 4 можно найти из двоичного представления, пропустив двоичные цифры в нечетных позициях, которые все должны быть нулевыми. С другой стороны, это числа, шестнадцатеричный представление содержит только цифры 0, 1, 4, 5. Например, 69 = 10114 = 4516.

Эквивалентно, это числа, двоичные и негабаритный представления равны.[1][2]

График количества элементов последовательности до деленное на , в логарифмической горизонтальной шкале

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

В связи с Теорема Фюрстенберга – Шаркози на последовательностях чисел без разницы квадратов, Имре З. Ружа нашел конструкцию для больших бесквадратных разностей множеств, которая, как и бинарное определение последовательности Мозера – де Брейна, ограничивает цифры в чередующихся позициях в базовом числа.[5] При нанесении на основу , Конструкция Ружи генерирует последовательность Мозера – де Брейна, умноженную на два, набор, который снова является бесквадратным. Однако этот набор слишком разрежен, чтобы дать нетривиальные оценки снизу для теоремы Фюрстенберга – Шаркози.

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

Последовательность Мозера – де Брейна подчиняется свойству, аналогичному свойству Сидоновская последовательность: суммы , где и оба принадлежат последовательности Мозера – де Брейна, все уникальны. Никакие две из этих сумм не имеют одинаковой стоимости. Более того, каждое целое число можно представить в виде суммы , где и оба принадлежат последовательности Мозера – де Брейна. Чтобы найти сумму, которая представляет , вычислить , то побитовое логическое и из с двоичным значением (выраженным здесь в шестнадцатеричный), который имеет единицы на всех своих четных позициях, и установите .[1][6]

Последовательность Мозера – де Брейна - единственная последовательность с этим свойством, что все целые числа имеют уникальное выражение как . Именно по этой причине последовательность первоначально была изучена Мозер (1962).[7] Расширение собственности, де Брюйн (1964) нашел бесконечно много других линейных выражений, таких как Что, когда и оба принадлежат последовательности Мозера – де Брейна, однозначно представляют все целые числа.[8][9]

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

Разложение числа в , а затем обращаясь к и Сохраняющее порядок отображение последовательности Мозера – де Брейна в целые числа (заменой степеней четырех в каждом числе соответствующими степенями двух) дает биекция от неотрицательных целых чисел до заказанные пары неотрицательных целых чисел. Инверсия этого биектирования дает линейный порядок точек на плоскости с неотрицательными целочисленными координатами, который может использоваться для определения Кривая Z-порядка.[1][10]

В связи с этим приложением удобно иметь формулу для генерации каждого последующего элемента последовательности Мозера – де Брейна из ее предшественника. Это можно сделать следующим образом. Если является элементом последовательности, то следующий член после может быть получен путем заполнения битов в нечетных позициях двоичного представления по одному, добавляя единицу к результату и затем маскируя заполненные биты. Заполнение битов и добавление единицы можно объединить в одну операцию сложения. То есть следующий член - это номер, заданный формулой

.[1][6][10]

Две шестнадцатеричные константы, встречающиеся в этой формуле, можно интерпретировать как 2-адические числа и соответственно.[1]

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

Голомб (1966) исследовал игра на вычитание, аналогично вычесть квадрат, на основе этой последовательности. В игре Голомба два игрока по очереди извлекают монеты из кучи монеты. На каждом ходу игрок может убрать любое количество монет, принадлежащих последовательности Мозера – де Брейна. Удаление любого другого количества монет не допускается. Выигрывает игрок, убравший последнюю монету. Как замечает Голомб, «холодные» позиции в этой игре (те, в которых игрок, который собирается двигаться, проигрывает), в точности являются позициями вида где принадлежит последовательности Мозера – де Брейна. Выигрышная стратегия для этой игры - разложить текущее количество монет, , в где и оба принадлежат последовательности Мозера – де Брейна, и тогда (если не равно нулю), чтобы удалить монеты, оставив холодную позицию другому игроку. Если равен нулю, эта стратегия невозможна и нет выигрышного хода.[3]

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

Последовательность Мозера – де Брейна составляет основу примера иррациональный номер с необычным свойством, что десятичные представления и могут быть написаны просто и явно. Позволять обозначим саму последовательность Мозера – де Брейна. Тогда для

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

[11][12]

В качестве альтернативы можно написать:

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

Производящая функция

В производящая функция

чьи показатели в развернутом виде задаются последовательностью Мозера – де Брейна, подчиняется функциональные уравнения

[1][2]

и

[14]

Например, эту функцию можно использовать для описания двух десятичных обратных величин, указанных выше: один - а другой . Тот факт, что они взаимны, является примером первого из двух функциональных уравнений. частичные продукты формы произведения производящей функции можно использовать для генерации подходящих дробей непрерывная дробь расширение самих этих чисел, а также кратных им.[11]

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

Последовательность Мозера – де Брейна подчиняется отношение повторения что позволяет пое значение последовательности, (начинается с ), который определяется из значения в позиции :

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

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

Заметки

  1. ^ а б c d е ж г Слоан, Н. Дж. А. (ред.), «Последовательность A000695 (последовательность Мозера-де Брейна)», В Он-лайн энциклопедия целочисленных последовательностей, Фонд OEIS
  2. ^ а б Арндт, Йорг (2011), Имеет значение вычислительные: идеи, алгоритмы, исходный код (PDF), Springer, стр.59, 750..
  3. ^ а б Голомб, Соломон В. (1966), "Математическое исследование игр" на вынос"", Журнал комбинаторной теории, 1 (4): 443–458, Дои:10.1016 / S0021-9800 (66) 80016-9, Г-Н 0209015.
  4. ^ Эпплгейт, Дэвид; ЛеБрун, Марк; Слоан, Н. Дж. А. (2011), «Мрачная арифметика» (PDF), Журнал целочисленных последовательностей, 14 (9): Статья 11.9.8, 34, arXiv:1107.1130, Bibcode:2011arXiv1107.1130A, Г-Н 2859992.
  5. ^ Ружа, И.З. (1984), «Разностные множества без квадратов», Periodica Mathematica Hungarica, 15 (3): 205–209, Дои:10.1007 / BF02454169, Г-Н 0756185.
  6. ^ а б Константы в этой формуле выражены в шестнадцатеричный и на основе 32-битного размера слова. Тот же битовый шаблон должен быть расширен или уменьшен очевидным образом для обработки других размеров слова.
  7. ^ Мозер, Лев (1962), «Применение производящих рядов», Математический журнал, 35 (1): 37–38, JSTOR 2689100, Г-Н 1571147.
  8. ^ де Брёйн, Н.Г. (1964), "Некоторые прямые разложения множества целых чисел", Математика вычислений, 18: 537–546, Дои:10.2307/2002940, Г-Н 0167447.
  9. ^ Eigen, S.J .; Ито, Й .; Прасад, В. С. (2004), "Универсально плохие целые числа и 2-адики", Журнал теории чисел, 107 (2): 322–334, Дои:10.1016 / j.jnt.2004.04.001, Г-Н 2072392.
  10. ^ а б Тиягалингам, Джейараджан; Бекманн, Олав; Келли, Пол Х. Дж. (Сентябрь 2006 г.), «Является ли компоновка Morton конкурентоспособной для больших двумерных массивов?» (PDF), Параллелизм и вычисления: практика и опыт, 18 (11): 1509–1539, Дои:10.1002 / cpe.v18: 11, заархивировано из оригинал (PDF) на 2017-03-29, получено 2016-11-18.
  11. ^ а б ван дер Поортен, А. Дж. (1993), «Непрерывные дроби формального степенного ряда» (PDF), Достижения в теории чисел (Кингстон, ОН, 1991), Oxford Sci. Publ., Oxford Univ. Press, New York, pp. 453–466, Г-Н 1368441.
  12. ^ а б Бланшар, Андре; Мендес Франс, Мишель (1982), "Symétrie et transcendance", Bulletin des Sciences Mathématiques, 106 (3): 325–335, Г-Н 0680277. Как цитирует ван дер Поортен (1993).
  13. ^ Бейли, Дэвид Х.; Борвейн, Джонатан М.; Крэндалл, Ричард Э.; Померанс, Карл (2004), «О двоичных разложениях алгебраических чисел», Журнал де Теори де Номбр де Бордо, 16 (3): 487–518, Дои:10.5802 / jtnb.457, Г-Н 2144954. См., В частности, обсуждение после теоремы 4.2.
  14. ^ Лемер, Д. Х.; Малер, К.; ван дер Поортен, А. Дж. (1986), «Целые числа с цифрами 0 или 1», Математика вычислений, 46 (174): 683–689, Дои:10.2307/2008006, Г-Н 0829638.
  15. ^ Аллуш, Жан-Поль; Шаллит, Джеффри (1992), «Кольцо k-регулярные последовательности », Теоретическая информатика, 98 (2): 163–197, Дои:10.1016 / 0304-3975 (92) 90001-В, Г-Н 1166363. Пример 13, с. 188.

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