В теории чисел последовательность Мозера – де Брёйна - это целочисленная последовательность, названная в честь Лео Мозера и Николааса Говерта де Брёйна , состоящая из сумм различных степеней 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 принадлежит последовательности, потому что ее двоичное представление 1000101 2 имеет ненулевые цифры в позициях для 2 6 , 2 2 и 2 0 , все из которых имеют четные показатели. Числа в последовательности также можно описать как числа, представление которых по основанию 4 использует только цифры 0 или 1. [1] Для числа в этой последовательности представление с основанием 4 можно найти из двоичного представления, пропустив двоичные цифры в нечетных позициях, которые должны быть нулевыми. С другой стороны, это числа, шестнадцатеричное представление которых содержит только цифры 0, 1, 4, 5. Например, 69 = 1011 4 = 45 16 .
Эквивалентно, это числа, двоичное и отрицательное представления которых равны. [1] [2]
Из двоичного определения этих чисел или определения числа с основанием 4 следует, что они растут примерно пропорционально квадратным числам . Количество элементов в последовательности Мозера – де Брейна, которые ниже любого заданного порога. пропорционально , [3] факт, который также верен для квадратных чисел. Фактически числа в последовательности Мозера – де Брейна представляют собой квадраты для версии арифметики без переноса двоичных чисел, в которой сложение и умножение отдельных битов являются соответственно операциями исключающего ИЛИ и логического соединения . [4]
В связи с теоремой Фюрстенберга – Шаркози о последовательностях чисел без разницы квадратов Имре З. Ружа нашел конструкцию для больших бесквадратных разностей множеств, которая, как и двоичное определение последовательности Мозера – де Брейна, ограничивает цифры в чередование позиций в базе-числа. [5] При нанесении на базу, Конструкция Ружи генерирует последовательность Мозера – де Брейна, умноженную на два, набор, который снова является бесквадратным. Однако этот набор слишком разрежен, чтобы дать нетривиальные оценки снизу для теоремы Фюрстенберга – Шаркози.
Уникальное представление в виде сумм
Последовательность Мозера – де Брейна подчиняется свойству, аналогичному свойству последовательности Сидона : суммы, где а также оба принадлежат последовательности Мозера – де Брейна, все они уникальны. Никакие две из этих сумм не имеют одинаковой стоимости. Более того, каждое целое число можно представить в виде суммы , где а также оба принадлежат последовательности Мозера – де Брейна. Чтобы найти сумму, которая представляет, вычислить , побитовое логическое и изс двоичным значением (выраженным здесь в шестнадцатеричном формате ), имеющим единицы во всех четных позициях, и установите. [1] [6]
Последовательность Мозера – де Брейна - единственная последовательность с этим свойством, что все целые числа имеют уникальное выражение как . Именно по этой причине последовательность была первоначально изучена Мозером (1962) . [7] Расширяя свойство, Де Брюйн (1964) нашел бесконечно много других линейных выражений, таких как Что, когда а также оба принадлежат последовательности Мозера – де Брейна, однозначно представляют все целые числа. [8] [9]
Кривая Z-порядка и формула преемника
Разложение числа в , а затем обращаясь к а также Сохраняющее порядок отображение из последовательности Мозера – де Брейна в целые числа (заменой степеней четырех в каждом числе соответствующими степенями двух) дает биекцию неотрицательных целых чисел на упорядоченные пары неотрицательных целых чисел. Обратное этой биекции дает линейный порядок точек на плоскости с неотрицательными целочисленными координатами, который может использоваться для определения кривой Z-порядка . [1] [10]
В связи с этим приложением удобно иметь формулу для генерации каждого последующего элемента последовательности Мозера – де Брейна из ее предшественника. Это можно сделать следующим образом. Если является элементом последовательности, то следующий член после может быть получен путем заполнения битов в нечетных позициях двоичного представления по одному, добавляя единицу к результату, а затем маскируя заполненные биты. Заполнение битов и добавление единицы можно объединить в одну операцию сложения. То есть следующий член - это номер, заданный формулой
Две шестнадцатеричные константы, фигурирующие в этой формуле, можно интерпретировать как 2-адические числа а также , соответственно. [1]
Игра на вычитание
Голомб (1966) исследовал игру на вычитание , аналогичную вычитанию квадрата , основанную на этой последовательности. В игре Голомба два игрока по очереди извлекают монеты из кучимонеты. На каждом ходу игрок может убрать любое количество монет, принадлежащих последовательности Мозера – Де Брёйна. Удаление любого другого количества монет не допускается. Победителем становится игрок, убравший последнюю монету. Как замечает Голомб, «холодные» позиции этой игры (те, в которых игрок, который собирается двигаться, проигрывает), в точности являются позициями вида где принадлежит последовательности Мозера – де Брейна. Выигрышная стратегия для этой игры - разложить текущее количество монет,, в где а также оба принадлежат последовательности Мозера – де Брейна, и тогда (если не равно нулю), чтобы удалить монеты, оставляя холодную позицию другому игроку. Еслиравен нулю, эта стратегия невозможна и нет выигрышного хода. [3]
Десятичные обратные
Последовательность Мозера – де Брейна составляет основу примера иррационального числа с необычным свойством, что десятичные представления а также могут быть написаны просто и явно. Позволятьобозначим саму последовательность Мозера – Де Брейна. Тогда для
десятичное число, ненулевые цифры которого находятся в позициях, заданных последовательностью Мозера – Де Брейна, отсюда следует, что ненулевые цифры его обратной величины расположены в позициях, заданных удвоением чисел в и добавив ко всем по единице: :
В качестве альтернативы можно написать:
Подобные примеры работают и в других базах. Например, два двоичных числа , ненулевые биты которых находятся в тех же позициях, что и ненулевые цифры двух десятичных чисел, указанных выше, также являются иррациональными обратными. [13] Эти двоичные и десятичные числа, а также числа, определенные таким же образом для любых других оснований путем повторения одной ненулевой цифры в позициях, заданных последовательностью Мозера – де Брейна, являются трансцендентными числами . Их трансцендентность может быть доказана тем фактом, что длинные цепочки нулей в их цифрах позволяют более точно аппроксимировать их рациональными числами, чем это допускала бы теорема Рота, если бы они были алгебраическими числами . [12]
Производящая функция
Функция генерирования
чьи показатели в развернутом виде задаются последовательностью Мозера – де Брейна, подчиняется функциональным уравнениям
- [1] [2]
а также
- [14]
Например, эту функцию можно использовать для описания двух десятичных обратных величин, указанных выше: один - а другой . Тот факт, что они являются обратными, является примером первого из двух функциональных уравнений. Эти частичные произведения вида продукта порождающей функции могут быть использованы для создания дробей цепной дроби разложения самих этих чисел, а также кратных них. [11]
Повторяемость и регулярность
Последовательность Мозера – де Брюйна подчиняется рекуррентному соотношению, которое допускает n- е значение последовательности, (начинается с ), который определяется по значению в позиции :
Повторение этого повторения позволяет любую подпоследовательность вида должна быть выражена как линейная функция исходной последовательности, что означает, что последовательность Мозера – Де Брейна является 2-регулярной последовательностью . [15]
Смотрите также
- Последовательность Стэнли и множество Кантора , множества, определенные аналогично с использованием трех представлений их элементов
Заметки
- ^ Б с д е е г Sloane, Н. Дж А. (ред.), «Последовательность A000695 (Moser-Де Брейна последовательность)» , энциклопедия целочисленных последовательностей , OEIS фонд
- ^ а б Арндт, Йорг (2011), Вычислительные вопросы: идеи, алгоритмы, исходный код (PDF) , Springer, стр. 59, 750..
- ^ а б Голомб, Solomon W. (1966), "Математическое исследование игр " на вынос " ", Журнал комбинаторной теории , 1 (4): 443-458, DOI : 10.1016 / S0021-9800 (66) 80016-9 , MR 0209015.
- ^ Эпплгейт, Дэвид ; ЛеБрун, Марк; Sloane, NJA (2011), «Мрачная арифметика» (PDF) , Журнал целочисленных последовательностей , 14 (9): статья 11.9.8, 34, arXiv : 1107.1130 , Bibcode : 2011arXiv1107.1130A , MR 2859992.
- ^ Ruzsa, IZ (1984), "Разностные множества без квадратов", Periodica Mathematica Hungarica , 15 (3): 205-209, DOI : 10.1007 / BF02454169 , МР 0756185.
- ^ a b Константы в этой формуле выражены в шестнадцатеричном формате и основаны на 32-битном размере слова. Тот же битовый шаблон должен быть расширен или уменьшен очевидным образом для обработки слов других размеров.
- ^ Мозер, Лео (1962), «Применение производящих рядов», Mathematics Magazine , 35 (1): 37–38, JSTOR 2689100 , MR 1571147.
- ^ Де Брейна, Н. (1964), "Некоторые прямые разложения множества целых чисел", Математика вычислений , 18 : 537-546, DOI : 10,2307 / 2002940 , МР 0167447.
- ^ Эйген, SJ; Ito, Y .; Прасад, В. С. (2004), "Универсально плохие числа и 2-adics", Журнал теории чисел , 107 (2): 322-334, DOI : 10.1016 / j.jnt.2004.04.001 , MR 2072392.
- ^ а б Тиягалингам, Джейараджан; Бекманн, Олав; Келли, Пол HJ (сентябрь 2006 г.), "Является ли макет Morton конкурентоспособным для больших двумерных массивов?" (PDF) , Параллелизм и вычисления: практика и опыт , 18 (11): 1509–1539, doi : 10.1002 / cpe.v18: 11 , заархивировано из оригинала (PDF) 29 марта 2017 г. , извлечено 11 ноября 2016 г. 18.
- ^ а б van der Poorten, AJ (1993), "Непрерывные дроби формальных степенных рядов" (PDF) , Успехи в теории чисел (Kingston, ON, 1991) , Oxford Sci. Publ., Oxford Univ. Press, New York, pp. 453–466, MR 1368441..
- ^ а б Бланшар, Андре; Mendès France, Мишель (1982), "Symétrie et transcendance", 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 , MR 2144954. См., В частности, обсуждение после теоремы 4.2.
- ^ Lehmer, DH ; Малер К .; ван - дер - Poorten, AJ (1986), "Целые с цифр 0 или 1", Математика вычислений , 46 (174): 683-689, DOI : 10,2307 / 2008006 , МР 0829638.
- ^ Аллуш, Жан-Поль; Shallit, Джеффри (1992), "Кольцо K -регулярных последовательностей", Теоретическая информатика , 98 (2): 163-197, DOI : 10.1016 / 0304-3975 (92) 90001-В , МР 1166363. Пример 13, с. 188.
Внешние ссылки
- Вайсштейн, Эрик В. , «Последовательность Мозера – Де Брейна» , MathWorld