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 On-Line Encyclopedia of Integer Sequences it is catalogued as A000695.

A number belongs to the sequence exactly when its base-4 digits are only 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 starts at 20. If it is cleared, no terms are shown until a new value is entered.
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. Values outside that range, decimals, and non-numeric entries show a validation message. 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-born Canadian mathematician who worked in number theory. Nicolaas Govert de Bruijn (1918–2012) was a Dutch mathematician who worked in analysis, number theory, combinatorics, and logic. The OEIS entry lists a 1962 paper by Moser in Mathematics Magazine and a 1964 paper by de Bruijn in Mathematics of Computation among its references. A key property is that every non-negative integer n can be written in exactly one way as M(k) + 2·M(l), with both M(k) and M(l) taken from the sequence.

Frequently Asked Questions

What is the Moser-de Bruijn sequence used for?

It comes up in additive number theory, because every non-negative integer splits uniquely into one term plus twice another term. The same bit-spreading idea underlies Morton (Z-order) layouts, which interleave the bits of two coordinates. It is also a simple exercise in base conversion and bitwise operations.

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.

References

1. The OEIS Foundation. A000695: Moser-de Bruijn sequence: sums of distinct powers of 4. OEIS A000695 — sequence terms, base-4 digits only 0 and 1, unique form a(k) + 2·a(l), Moser (1962) and de Bruijn (1964) references.
2. The OEIS Foundation. A000079: Powers of 2. OEIS A000079 — powers of 2.
3. The OEIS Foundation. A005836: Numbers whose base-3 representation contains no 2. OEIS A005836 — sums of distinct powers of 3.
4. The OEIS Foundation. A003714: Fibbinary numbers. OEIS A003714 — binary numbers with no two adjacent 1s.
5. MacTutor History of Mathematics, University of St Andrews. Leo Moser (1921–1970). Leo Moser biography — life dates, Austrian-born Canadian, number theory.
6. MacTutor History of Mathematics, University of St Andrews. Nicolaas de Bruijn (1918–2012). Nicolaas de Bruijn biography — life dates, Dutch, fields of work.