Генератор последовательности Мозера-де Брёйна | Калькулятор степеней 4

Что такое последовательность Мозера — де Брёйна?

Последовательность Мозера — де Брёйна — это список целых чисел, каждое из которых можно представить как сумму различных степеней числа 4. Она начинается так: 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85 и продолжается бесконечно. Она названа в честь математиков Лео Мозера и Николаса Говерта де Брёйна. В Онлайн-энциклопедии целочисленных последовательностей она зарегистрирована под номером A000695.

Число принадлежит последовательности тогда и только тогда, когда в его записи в системе счисления с основанием 4 используются только цифры 0 и 1, но не 2 и 3. Например, число 21 в системе счисления с основанием 4 записывается как 111, поэтому оно принадлежит последовательности. Число 22 в системе счисления с основанием 4 записывается как 112, поэтому оно в неё не входит.

Формула последовательности Мозера — де Брёйна

Последовательность можно определить тремя эквивалентными способами.

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

Число n принадлежит последовательности, если его можно представить в виде

$n = \sum_{i \in S} 4^i$

для некоторого множества S неотрицательных целых чисел, причём каждая степень числа 4 используется не более одного раза.

Проверка цифр в системе счисления с основанием 4

Запишите число в системе счисления с основанием 4. Если каждая цифра равна 0 или 1, число принадлежит последовательности. Если встречается цифра 2 или 3, оно в неё не входит.

Подстановка двоичных цифр в систему счисления с основанием 4

Если считать члены, начиная с n = 0, то член с индексом n равен

$M(n) = \sum_{i=0}^{k} b_i \cdot 4^i$

где $b_i$ — двоичные цифры числа n. Иными словами, запишите n в двоичной системе, а затем прочитайте каждую двоичную цифру как цифру в системе счисления с основанием 4 на той же позиции. Именно этот метод использует генератор, поскольку ему нужно лишь проверять биты и складывать числа.

Как вычислить член с индексом n

Чтобы найти M(n), генератор выполняет следующие действия для каждого индекса n, начиная с n = 0:

1. Рассмотреть двоичную запись числа n.
2. Для каждого бита, равного 1, на позиции j прибавить 4^j к текущей сумме.
3. Пропустить биты, равные 0.
4. Текущая сумма равна M(n).

Пример вычисления: M(5)

• Число 5 в двоичной системе записывается как 101.
• Бит 0 (крайний справа) равен 1, поэтому прибавляем 4⁰ = 1.
• Бит 1 равен 0, поэтому ничего не прибавляем.
• Бит 2 равен 1, поэтому прибавляем 4² = 16.
• Итого: 1 + 16 = 17.

Итак, M(5) = 17. Это шестое значение, выдаваемое генератором, поскольку отсчёт начинается с M(0).

Пример: первые 32 членов

Как проверить, принадлежит ли число последовательности

Переведите число в систему счисления с основанием 4 и изучите его цифры.

• 85: в системе счисления с основанием 4 число 85 записывается как 1111 (64 + 16 + 4 + 1). В записи встречаются только 0 и 1, поэтому 85 принадлежит последовательности.
• 90: в системе счисления с основанием 4 число 90 записывается как 1122. В нём есть цифра 2, поэтому 90 не принадлежит последовательности.

Темп роста

Последовательность растёт быстро, поскольку каждый дополнительный бит индекса может примерно в четыре раза увеличить добавляемое значение. M(19) = 261. M(99) = 5 125. M(999), наибольший член, который может выдать этот генератор, равен 349 205. По мере роста индекса члены удаляются друг от друга всё сильнее, поэтому последовательность разреженная: большинство целых чисел в ней не встречается, хотя она содержит бесконечно много членов.

Как пользоваться генератором последовательности Мозера — де Брёйна

1. Введите количество членов для генерации. Если поле оставить пустым, по умолчанию используется значение 20.
2. Список членов обновляется автоматически, начиная с M(0).
3. Скопируйте весь список с помощью кнопки «Копировать результат».

Инструмент принимает целые числа от 1 до 1000. Десятичные дроби, отрицательные числа и нечисловые значения отклоняются. Запрос 20 членов возвращает значения от M(0) до M(19); последнее показанное значение — 261. Все вычисления выполняются в браузере, поэтому результаты появляются сразу, а данные не отправляются на сервер.

Связанные последовательности

• Степени числа 2 (OEIS A000079): 1, 2, 4, 8, 16, 32 и так далее. Именно из них складываются обычные двоичные числа.
• Суммы различных степеней числа 3 (OEIS A005836): 0, 1, 3, 4, 9, 10, 12, 13 и так далее. Та же идея, что и в последовательности Мозера — де Брёйна, но построенная на системе счисления с основанием 3, а не 4.
• Фиббинарные числа (OEIS A003714): 0, 1, 2, 4, 5, 8, 9, 10 и так далее. Это числа, в двоичной записи которых нет двух последовательных единиц 1.

История

Лео Мозер (1921-1970) был австрийско-канадским математиком и занимался теорией чисел, комбинаторикой и геометрией. Николас Говерт де Брёйн (1918-2012) был нидерландским математиком, известным работами по комбинаторике, теории графов и информатике; его не связанные с этой последовательностью последовательности де Брёйна широко используются в теории кодирования. Оба изучали аддитивные базисы — множества целых чисел, например степени числа 4, из которых каждое представимое число имеет единственное представление в виде суммы. Последовательность, носящая их имена, является одним из примеров такого базиса.

Часто задаваемые вопросы

Для чего используется последовательность Мозера — де Брёйна?

Она встречается в аддитивной теории чисел и комбинаторике, особенно при изучении множеств, не содержащих сумм, и аддитивных базисов. Её также используют для обучения переводу между системами счисления и побитовым операциям в информатике.

Как построить последовательность Мозера — де Брёйна?

Запишите индекс n в двоичной системе, а затем прочитайте каждую двоичную цифру как цифру в системе счисления с основанием 4 на той же позиции. Для n = 5 (двоичная запись 101) получается 4² + 4⁰ = 17.

Как проверить, принадлежит ли число последовательности?

Переведите его в систему счисления с основанием 4. Если каждая цифра равна 0 или 1, число принадлежит последовательности. Если встречается цифра 2 или 3, оно в неё не входит.

Какова формула n-го члена?

M(n) = сумма по всем i величин $b_i \cdot 4^i$, где $b_i$ — двоичные цифры числа n.

Является ли последовательность бесконечной?

Да. Она содержит бесконечно много членов, хотя по мере роста n они располагаются всё реже.

Чем она отличается от двоичной системы?

Двоичная система, то есть представление в виде сумм различных степеней числа 2, позволяет представить любое неотрицательное целое число. В последовательности Мозера — де Брёйна вместо этого используются степени числа 4, поэтому большинство целых чисел в ней не встречается.