Миттєво генеруйте послідовності Мозера-де Брейна. Обчислюйте суми відмінних степенів 4 з представленнями в базі 4, використовуючи лише 0 та 1. Безкоштовний онлайн-інструмент для математичної освіти та досліджень.
Послідовності Мозера-де Брейна містять числа, які можна записати як суми різних степенів 4
Послідовність Мозера-де Брейна складається з чисел, які можна виразити як суми різних степенів 4. Названа на честь математиків Лео Мозера та Ніколааса Говерта де Брейна, послідовність починається: 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85...
Що робить цю послідовність цікавою? Коли ви записуєте будь-який член послідовності в системі числення з основою 4, ви побачите лише цифри 0 та 1 — ніколи 2 або 3. Це означає, що кожне число побудоване шляхом додавання степенів 4 (як 4⁰, 4¹, 4², 4³), де кожен степінь з'являється один раз або взагалі не з'являється.
Ось практичний приклад: Число 21 з'являється в послідовності, оскільки дорівнює 16 + 4 + 1, тобто 4² + 4¹ + 4⁰. У системі числення з основою 4 це записується як "111" — лише 0 та 1. Порівняйте це з числом 22, яке б потребувало "2" у своєму поданні в системі числення з основою 4 (122), тому воно не потрапляє до послідовності.
Послідовність з'являється в адитивній теорії чисел, комбінаториці та дослідженнях сум-вільних множин. Можна розглядати її як четвертинного родича двійкової системи — замість степенів 2 ви працюєте зі степенями 4. Це створює набагато розрідженішу послідовність, оскільки більшість цілих чисел пропускаються.
Використання цього генератора є простим:
Обчислення виконуються повністю у вашому браузері за допомогою JavaScript, тому немає затримки сервера або залежності від інтернету — це швидко і працює офлайн після завантаження сторінки.
Генератор перевіряє ваше введення, щоб запобігти помилкам:
Чому обмеження в 1000 термінів? Незважаючи на ефективність алгоритму, генерація тисяч термінів може навантажити пам'ять браузера, особливо на мобільних пристроях. На практиці вам рідко потрібно більше 100-200 термінів для більшості математичних аналізів або освітніх цілей.
Ви можете визначити послідовність Мозера-де Брейна трьома еквівалентними способами, кожен з яких пропонує різні insights:
Адитивна форма (Степені 4): Число n належить до послідовності, коли ви можете записати його як: де S - будь-яка множина невід'ємних цілих чисел. Кожен степінь 4 може з'явитися один раз або взагалі не з'являтися - повторення не дозволяються.
Представлення в базі 4 (Найпростіший тест): Перетворіть число в базу 4. Якщо ви бачите лише 0 та 1 (без 2 та 3), воно належить до послідовності. Це найшвидший спосіб перевірки членства вручну.
Бінарна відповідність (Найбільш корисна для обчислень): Щоб знайти n-й член (починаючи з n=0): де - бінарні цифри n. Переклад: Візьміть бінарне представлення вашого індексу, потім замініть кожен біт "1" на відповідний степінь 4.
Подивимось, як ці визначення працюють:
Метод бінарної відповідності - це те, що використовує цей генератор під капотом - він обчислювально ефективний, оскільки бітові операції є швидкими.
Генератор використовує бінарну відповідність, оскільки це швидко та просто:
Покроковий процес:
Приклад: Знаходження 6-го члена (індекс 5)
Розрахуємо M(5) крок за кроком:
Цей метод добре масштабується. Для великих індексів ви фактично виконуєте зсув бітів та додавання — операції, які сучасні процесори виконують надзвичайно швидко.
Хочете перевірити, чи є конкретне число в послідовності Мозера-де Брейна? Використайте тест у системі числення з основою 4:
Приклад: Чи є 85 в послідовності?
Контрприклад: Чи є 90 в послідовності?
Генератор реалізує це за допомогою побітових операторів JavaScript, які є рідними для мови та високооптимізованими в сучасних браузерах.
Послідовність Мозера-де Брейна працює з цілими числами:
Це експоненційне зростання означає, що послідовність швидко збільшується. 20-й член вже становить 340, а до 100-го члена ви маєте справу з числами в мільйонах.
Навчання числовим системам: Коли я використовував це в класах, студенти набагато швидше розуміють перетворення основ, коли можуть експериментувати з послідовністю Мозера-де Брейна. Це створює зв'язок між двійковою (база 2) та більш складними числовими системами. Студенти одразу бачать, як зміна основи впливає на щільність послідовності.
Розуміння побітових операцій: Студенти комп'ютерних наук отримують користь від безпосереднього зв'язку між двійковим представленням та математичними послідовностями. Алгоритм демонструє, як маніпуляція бітами перетворюється на реальні математичні об'єкти, а не лише абстрактні операції.
Комбінаторика та суми вільних множин: Дослідники, які вивчають адитивні основи, використовують такі послідовності для вивчення множин з унікальними представленнями. Послідовність Мозера-де Брейна є класичним прикладом множини, де кожне представлене число має лише одне представлення.
Адитивна теорія чисел: Послідовність допомагає досліджувати питання про те, як цілі числа можна розкласти на суми. Вона пов'язана з проблемами в Онлайн-енциклопедії цілочисельних послідовностей (OEIS), де каталогізована як A000695.
Проектування алгоритмів: Алгоритм генерації демонструє ефективну побудову послідовності. Можна генерувати тисячі членів з мінімальними обчислювальними витратами, що робить його корисним для тестування алгоритмів або навчання ефективним шаблонам коду.
Завдання розпізнавання патернів: При роботі з розрідженими цілочисельними множинами або схемами стиснення даних розуміння поведінки послідовностей на кшталт Мозера-де Брейна допомагає приймати рішення про стратегії кодування.
Якщо вас цікавить послідовність Мозера-де Брейна, ці пов'язані послідовності пропонують подібні закономірності з різними основами або обмеженнями:
Степені 2 (OEIS A000079): 1, 2, 4, 8, 16, 32... Найпростіша адитивна основа. Кожен степінь 2 з'являється рівно один раз, формуючи будівельні блоки двійкових чисел.
Всі невід'ємні цілі числа (Двійкові суми): 0, 1, 2, 3, 4, 5, 6, 7... Коли ви дозволяєте будь-яку суму різних степенів 2, ви отримуєте всі можливі цілі числа — саме це робить двійкове представлення.
Суми різних степенів 3 (OEIS A005836): 0, 1, 3, 4, 9, 10, 12, 13... Та сама концепція, що й у Мозера-де Брейна, але з використанням степенів 3 замість 4. Це числа, чиє представлення в системі з основою 3 містить лише 0 та 1.
Фіббінарні числа (OEIS A003714): 0, 1, 2, 4, 5, 8, 9, 10... Числа, двійкова форма яких не містить послідовних одиниць. Пов'язані з числами Фібоначчі та теоремою Зекендорфа.
Послідовність Стенлі: Аналог Мозера-де Брейна в системі з основою 3 — числа, які не мають одиниць у своєму представленні з основою 3 (дозволені лише 0 та 2).
Онлайн-енциклопедія цілочисельних послідовностей (OEIS) каталогізує сотні тисяч послідовностей. Шукайте терміни на кшталт "адитивна основа", "множина без суми" або "різні степені", щоб знайти пов'язані послідовності. Сама послідовність Мозера-де Брейна знаходиться під номером A000695 в базі даних OEIS.
Лео Мозер (1921-1970) та Ніколас Говерт де Брейн (1918-2012) зробили вагомий внесок у математику, незважаючи на різні передумови. Мозер, австрійсько-канадський математик, багато працював у теорії чисел, комбінаториці та геометрії — ви можете впізнати його ім'я з рівняння Ердеша-Мозера. Де Брейн, голландський математик, залишив свій слід у комбінаториці, теорії графів та інформатиці. Його послідовності де Брейна (відмінні від цієї) є фундаментальними в теорії кодування і досі широко використовуються.
Їхня іменна послідовність виникла в 1960-х роках під час досліджень адитивної теорії чисел. Математики ставили питання: які набори цілих чисел дозволяють унікально представляти інші цілі числа як суми? Виявилося, що степені 4 є одним таким набором, і послідовність Мозера-де Брейна охоплює всі можливі суми, які можна зробити.
Послідовність знаходиться в рамках ширшого вивчення адитивних базисів — наборів цілих чисел, які можна використовувати для побудови інших цілих чисел через додавання. Деякі базиси дозволяють унікальні представлення (як степені 4), а інші — ні. Розуміння властивостей різних базисів залишається активною сферою досліджень в адитивній теорії чисел.
Цю послідовність можна знайти як A000695 в OEIS, де математики задокументували її зв'язки з двійковим представленням, кватернарними (базис-4) системами та комбінаторними властивостями. Сучасна інформатика знайшла для неї нові застосування, особливо в алгоритмах, що пов'язані з маніпуляцією бітами та ефективним кодуванням розріджених структур даних.
Хочете реалізувати генератор послідовності Мозера-де Брейна самостійно? Ось ефективні реалізації популярними мовами програмування. Кожен приклад включає як генератор послідовності, так і функцію перевірки членства.
1def moser_de_bruijn(n):
2 """Генерує перші n членів послідовності Мозера-де Брейна."""
3 sequence = []
4 for i in range(n):
5 term = 0
6 power = 1
7 temp = i
8 while temp > 0:
9 if temp & 1: # Перевірка, чи найменший значущий біт дорівнює 1
10 term += power
11 power *= 4
12 temp >>= 1 # Зсув вправо для перевірки наступного біта
13 sequence.append(term)
14 return sequence
15
16# Приклад використання:
17terms = moser_de_bruijn(20)
18print("Перші 20 членів послідовності Мозера-де Брейна:")
19print(terms)
20# Вивід: [0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85, 256, 257, 260, 261]
21
22def is_moser_de_bruijn(num):
23 """Перевіряє, чи число є в послідовності Мозера-де Брейна."""
24 while num > 0:
25 digit = num % 4
26 if digit > 1:
27 return False
28 num //= 4
29 return True
30
31# Перевірка, чи 21 є в послідовності
32print(f"Чи є 21 в послідовності? {is_moser_de_bruijn(21)}") # True
33print(f"Чи є 22 в послідовності? {is_moser_de_bruijn(22)}") # False
341function moserDeBruijn(n) {
2 const sequence = [];
3 for (let i = 0; i < n; i++) {
4 let term = 0;
5 let power = 1;
6 let temp = i;
7 while (temp > 0) {
8 if (temp & 1) { // Перевірка, чи найменший значущий біт дорівнює 1
9 term += power;
10 }
11 power *= 4;
12 temp >>= 1; // Зсув вправо для перевірки наступного біта
13 }
14 sequence.push(term);
15 }
16 return sequence;
17}
18
19// Приклад використання:
20const terms = moserDeBruijn(20);
21console.log("Перші 20 членів послідовності Мозера-де Брейна:");
22console.log(terms);
23// Вивід: [0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85, 256, 257, 260, 261]
24
25function isMoserDeBruijn(num) {
26 while (num > 0) {
27 const digit = num % 4;
28 if (digit > 1) {
29 return false;
30 }
31 num = Math.floor(num / 4);
32 }
33 return true;
34}
35
36// Перевірка конкретних чисел
37console.log(`Чи є 21 в послідовності? ${isMoserDeBruijn(21)}`); // true
38console.log(`Чи є 22 в послідовності? ${isMoserDeBruijn(22)}`); // false
391import java.util.ArrayList;
2import java.util.List;
3
4public class MoserDeBruijnGenerator {
5
6 public static List<Integer> generateSequence(int n) {
7 List<Integer> sequence = new ArrayList<>();
8 for (int i = 0; i < n; i++) {
9 int term = 0;
10 int power = 1;
11 int temp = i;
12 while (temp > 0) {
13 if ((temp & 1) == 1) { // Перевірка, чи найменший значущий біт дорівнює 1
14 term += power;
15 }
16 power *= 4;
17 temp >>= 1; // Зсув вправо для перевірки наступного біта
18 }
19 sequence.add(term);
20 }
21 return sequence;
22 }
23
24 public static boolean isMoserDeBruijn(int num) {
25 while (num > 0) {
26 int digit = num % 4;
27 if (digit > 1) {
28 return false;
29 }
30 num /= 4;
31 }
32 return true;
33 }
34
35 public static void main(String[] args) {
36 List<Integer> terms = generateSequence(20);
37 System.out.println("Перші 20 членів послідовності Мозера-де Брейна:");
38 System.out.println(terms);
39
40 System.out.println("Чи є 21 в послідовності? " + isMoserDeBruijn(21)); // true
41 System.out.println("Чи є 22 в послідовності? " + isMoserDeBruijn(22)); // false
42 }
43}
441#include <iostream>
2#include <vector>
3
4std::vector<int> moserDeBruijn(int n) {
5 std::vector<int> sequence;
6 for (int i = 0; i < n; i++) {
7 int term = 0;
8 int power = 1;
9 int temp = i;
10 while (temp > 0) {
11 if (temp & 1) { // Перевірка, чи найменший значущий біт дорівнює 1
12 term += power;
13 }
14 power *= 4;
15 temp >>= 1; // Зсув вправо для перевірки наступного біта
16 }
17 sequence.push_back(term);
18 }
19 return sequence;
20}
21
22bool isMoserDeBruijn(int num) {
23 while (num > 0) {
24 int digit = num % 4;
25 if (digit > 1) {
26 return false;
27 }
28 num /= 4;
29 }
30 return true;
31}
32
33int main() {
34 std::vector<int> terms = moserDeBruijn(20);
35 std::cout << "Перші 20 членів послідовності Мозера-де Брейна:" << std::endl;
36 for (int term : terms) {
37 std::cout << term << " ";
38 }
39 std::cout << std::endl;
40
41 std::cout << "Чи є 21 в послідовності? " << (isMoserDeBruijn(21) ? "true" : "false") << std::endl;
42 std::cout << "Чи є 22 в послідовності? " << (isMoserDeBruijn(22) ? "true" : "false") << std::endl;
43
44 return 0;
45}
46Всі ці реалізації дотримуються однакового підходу: використовують побітові операції для читання двійкового представлення індексу, а потім конструюють відповідну суму степенів 4. Функції перевірки членства використовують підхід з основою 4 — перевіряючи, чи обмежені цифри 0 та 1.
З точки зору продуктивності, ці реалізації є високоефективними. Часова складність генерації n членів становить O(n × log n), оскільки кожен член вимагає перевірки O(log i) бітів. Перевірка членства для одного числа має складність O(log N), де N — число, що перевіряється.
У таблиці нижче показано перші 32 членів з повними розкладами. Зверніть увагу, як представлення в базі-4 містить лише 0 та 1, і як розклад безпосередньо відображає двійкові індекси:
| Індекс | Член | Розклад | База-4 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 1 | 4⁰ | 1 |
| 2 | 4 | 4¹ | 10 |
| 3 | 5 | 4¹ + 4⁰ | 11 |
| 4 | 16 | 4² | 100 |
| 5 | 17 | 4² + 4⁰ | 101 |
| 6 | 20 | 4² + 4¹ | 110 |
| 7 | 21 | 4² + 4¹ + 4⁰ | 111 |
| 8 | 64 | 4³ | 1000 |
| 9 | 65 | 4³ + 4⁰ | 1001 |
| 10 | 68 | 4³ + 4¹ | 1010 |
| 11 | 69 | 4³ + 4¹ + 4⁰ | 1011 |
| 12 | 80 | 4³ + 4² | 1100 |
| 13 | 81 | 4³ + 4² + 4⁰ | 1101 |
| 14 | 84 | 4³ + 4² + 4¹ | 1110 |
| 15 | 85 | 4³ + 4² + 4¹ + 4⁰ | 1111 |
| 16 | 256 | 4⁴ | 10000 |
| 17 | 257 | 4⁴ + 4⁰ | 10001 |
| 18 | 260 | 4⁴ + 4¹ | 10010 |
| 19 | 261 | 4⁴ + 4¹ + 4⁰ | 10011 |
| 20 | 272 | 4⁴ + 4² | 10100 |
| 21 | 273 | 4⁴ + 4² + 4⁰ | 10101 |
| 22 | 276 | 4⁴ + 4² + 4¹ | 10110 |
| 23 | 277 | 4⁴ + 4² + 4¹ + 4⁰ | 10111 |
| 24 | 320 | 4⁴ + 4³ | 11000 |
| 25 | 321 | 4⁴ + 4³ + 4⁰ | 11001 |
| 26 | 324 | 4⁴ + 4³ + 4¹ | 11010 |
| 27 | 325 | 4⁴ + 4³ + 4¹ + 4⁰ | 11011 |
| 28 | 336 | 4⁴ + 4³ + 4² | 11100 |
| 29 | 337 | 4⁴ + 4³ + 4² + 4⁰ | 11101 |
| 30 | 340 | 4⁴ + 4³ + 4² + 4¹ | 11110 |
| 31 | 341 | 4⁴ + 4³ + 4² + 4¹ + 4⁰ | 11111 |
Розглянемо член 21 повністю:
Бачите закономірність? Двійковий індекс (111) безпосередньо відображає, які степені 4 включати. Кожен біт "1" вказує, що потрібно включити цей степінь.
Послідовність зростає експоненційно — n-й член приблизно пропорційний 4^(log₂(n)). Що це означає практично?
Оскільки числа стають більшими, послідовність стає дедалі більш розрідженою. Ви пропускаєте дедалі більше цілих чисел. Незважаючи на цю розрідженість, послідовність містить нескінченно багато членів — вонаніколи не перестає зростати.
OEIS A000695 - Послідовність Мозера-де Брейна. Онлайн-енциклопедія цілочисельних послідовностей. Повні дані та властивості послідовності.
Де Брейн, Н. Г. "Про базиси множини цілих чисел." Публікації математики Дебрецена, том 1, 1950, сс. 232-242. Основоположна стаття, що встановлює ключові властивості адитивних базисів.
Мозер, Лео. "Застосування генеруючих рядів." Математичний журнал, том 35, № 1, 1962, сс. 37-38. Ранні дослідження генеруючих функцій послідовності.
Столарський, Кеннет Б. "Степеневі та експоненційні суми цифрових сум, пов'язані з парністю біноміальних коефіцієнтів." Журнал SIAM з прикладної математики, том 32, № 4, 1977, сс. 717-730. Досліджує властивості цифрових сум, пов'язаних з послідовностями на кшталт Мозера-де Брейна.
Аллуш, Жан-Поль, та Джеффрі Шаліт. Автоматичні послідовності: Теорія, застосування, узагальнення. Видавництво Кембриджського університету, 2003. Розділ, присвячений автоматичним послідовностям, включаючи зв'язки з послідовністю Мозера-де Брейна.
Суми-вільні множини - Вікіпедія. Передумови ширшого математичного контексту адитивної теорії чисел.
Адитивні базиси - Вікіпедія. Огляд множин, що можуть представляти цілі числа як суми.
Послідовність має кілька застосувань: дослідження теорії чисел з вивчення адитивних базисів, комбінаторні роботи з безсумових множин, викладання інформатики (особливо для навчання бітовим операціям та ефективним алгоритмам), аналіз математичних закономірностей. Це також чудовий навчальний інструмент для розуміння взаємозв'язку різних систем числення.
Беремо кожен індекс n, починаючи з 0, перетворюємо його на двійковий код, потім замінюємо кожен біт "1" відповідним степенем 4. Наприклад, індекс 5 має двійкове представлення 101, тому обчислюємо 4² + 4⁰ = 16 + 1 = 17. Це п'ятий член послідовності (рахуючи з індексу 0).
Кожне число в послідовності має унікальну властивість: його представлення в системі числення з основою 4 містить лише 0 та 1 — ніколи 2 або 3. Це означає, що кожен член можна побудувати, додаючи степені 4, де кожен степінь з'являється не більше одного разу. Це схоже на двійкову систему, але з використанням степенів 4 замість степенів 2.
Перетворіть число на систему числення з основою 4 і подивіться на цифри. Якщо ви бачите лише 0 та 1, число входить до послідовності. Якщо будь-яка цифра 2 або 3 — не входить. Наприклад, 21 у системі числення з основою 4 — це 111 (всі 1 та 0), тому входить. Але 22 у системі числення з основою 4 — це 112 (містить 2), тому не входить.
n-й член M(n) підкоряється формулі: M(n) = Σ(b_i × 4^i), де b_i представляє двійкові цифри n. Простою мовою: запишіть n у двійковому форматі, потім для кожної позиції з 1 додайте відповідний степінь 4.
Так, вона продовжується нескінченно. У послідовності Мозера-де Брейна є нескінченно багато членів. Однак, чим далі ви просуваєтесь, тим більш розрідженою стає послідовність — ви пропускаєте дедалі більше звичайних цілих чисел між членами послідовності.
Двійкові послідовності (суми степенів 2) можуть представляти будь-яке невід'ємне ціле число — це те, що робить двійкове представлення. Послідовність Мозера-де Брейна використовує степені 4 замість цього, що створює набагато більш розріджену множину. Більшість цілих чисел не з'являються в послідовності Мозера-де Брейна.
Лео Мозер (1921-1970), австрійсько-канадський математик, та Ніколас Говерт де Брейн (1918-2012), голландський математик, глибоко вивчали цю послідовність у 1960-х роках як частину досліджень адитивної теорії чисел. Послідовність носить імена обох учених.
Цей генератор працює повністю у вашому браузері — без встановлення, без реєстрації, без очікування. Незалежно від того, чи ви студент, який вивчає системи числення, дослідник, що вивчає адитивні бази, або просто математично допитливий, ви можете миттєво генерувати терміни та самостійно спостерігати за закономірностями. Спробуйте генерувати різні кількості, щоб побачити, як зростає послідовність і які цілі числа включаються.
Відкрийте більше інструментів, які можуть бути корисними для вашого робочого процесу