Генератор на последователност на Мозер-де Бройн | Калкулатор на степени на 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. Копирайте целия списък с бутона Copy Result.

Инструментът приема цели числа от 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, затова повечето цели числа не се включват.