Moser-de Bruijn Sequence Generator | Powers of 4 Calculator

What Is the Moser-de Bruijn Sequence?

The Moser-de Bruijn sequence is a list of whole numbers that can each be written as a sum of distinct powers of 4. It begins 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85, and continues without end. It is named after mathematicians Leo Moser and Nicolaas Govert de Bruijn. In the Online Encyclopedia of Integer Sequences it is catalogued as A000695.

A number belongs to the sequence exactly when its base-4 representation uses only the digits 0 and 1, never 2 or 3. For example, 21 in base 4 is written 111, so it belongs. The number 22 in base 4 is written 112, so it does not.

Moser-de Bruijn Sequence Formula

The sequence can be defined in three equivalent ways.

Sum of distinct powers of 4

A number n is in the sequence if it can be written as

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

for some set S of non-negative integers, where each power of 4 is used at most once.

Base-4 digit test

Write the number in base 4. If every digit is 0 or 1, the number is in the sequence. If any digit is 2 or 3, it is not.

Binary-to-base-4 substitution

Counting terms from n = 0, the term at index n is

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

where the $b_i$ are the binary digits of n. In words: write n in binary, then read each binary digit as a base-4 digit in the same position. This is the method the generator uses, since it only needs to check bits and add numbers.

How to Calculate the Nth Term

To find M(n), the generator does the following for each index n, starting at n = 0:

1. Look at the binary form of n.
2. For every bit equal to 1, at position j, add 4^j to a running total.
3. Skip bits equal to 0.
4. The running total is M(n).

Worked example: M(5)

• 5 in binary is 101.
• Bit 0 (rightmost) is 1, so add 4⁰ = 1.
• Bit 1 is 0, so add nothing.
• Bit 2 is 1, so add 4² = 16.
• Total: 1 + 16 = 17.

So M(5) = 17. It is the sixth value the generator produces, since counting starts at M(0).

Example: First 32 Terms

How to Check If a Number Is in the Sequence

Convert the number to base 4 and read its digits.

• 85: in base 4, 85 is 1111 (64 + 16 + 4 + 1). Only 0s and 1s appear, so 85 is in the sequence.
• 90: in base 4, 90 is 1122. It contains a 2, so 90 is not in the sequence.

Growth Rate

The sequence grows quickly, because each extra bit in the index can roughly quadruple the value it adds. M(19) is 261. M(99) is 5,125. M(999), the largest term this generator can produce, is 349,205. Terms spread further and further apart as the index grows, which makes the sequence sparse: most whole numbers never appear in it, even though it has infinitely many terms.

How to Use the Moser-de Bruijn Sequence Generator

1. Enter the number of terms to generate. The field defaults to 20 if left blank.
2. The list of terms updates automatically, starting from M(0).
3. Copy the full list with the Copy Result button.

The tool accepts whole numbers from 1 to 1000. Decimals, negative numbers, and non-numeric entries are rejected. Requesting 20 terms returns M(0) through M(19); the last value shown is 261. All calculation happens in the browser, so results appear immediately and no data is sent to a server.

Related Sequences

• Powers of 2 (OEIS A000079): 1, 2, 4, 8, 16, 32, and so on. These are the building blocks of ordinary binary numbers.
• Sums of distinct powers of 3 (OEIS A005836): 0, 1, 3, 4, 9, 10, 12, 13, and so on. The same idea as the Moser-de Bruijn sequence, built from base 3 instead of base 4.
• Fibbinary numbers (OEIS A003714): 0, 1, 2, 4, 5, 8, 9, 10, and so on. Numbers whose binary form has no two consecutive 1s.

History

Leo Moser (1921-1970) was an Austrian-Canadian mathematician who worked in number theory, combinatorics, and geometry. Nicolaas Govert de Bruijn (1918-2012) was a Dutch mathematician known for work in combinatorics, graph theory, and computer science; his unrelated de Bruijn sequences are widely used in coding theory. Both studied additive bases: sets of integers, such as the powers of 4, from which every representable number has exactly one sum representation. The sequence that carries their names is one example of such a base.

Frequently asked questions

What is the Moser-de Bruijn sequence used for?

It comes up in additive number theory and combinatorics, particularly in the study of sum-free sets and additive bases. It is also used to teach base conversion and bitwise operations in computer science.

How do you generate the Moser-de Bruijn sequence?

Write the index n in binary, then read each binary digit as a base-4 digit in the same position. For n = 5 (binary 101), that gives 4² + 4⁰ = 17.

How can I check if a number is in the sequence?

Convert it to base 4. If every digit is 0 or 1, the number is in the sequence. If any digit is 2 or 3, it is not.

What is the formula for the nth term?

M(n) = the sum, over all i, of $b_i \cdot 4^i$, where the $b_i$ are the binary digits of n.

Is the sequence infinite?

Yes. It has infinitely many terms, though they become more spread out as n grows.

How is this different from binary?

Binary, meaning sums of distinct powers of 2, can represent every non-negative integer. The Moser-de Bruijn sequence uses powers of 4 instead, so most integers are left out.