Moser-de Bruijn Sequence Generator | Powers of 4 Calculator

What is the Moser-de Bruijn Sequence?

The Moser-de Bruijn sequence consists of numbers that can be expressed as sums of distinct powers of 4. Named after mathematicians Leo Moser and Nicolaas Govert de Bruijn, the sequence starts: 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85...

What makes this sequence interesting? When you write any term in base 4, you'll only see the digits 0 and 1—never 2 or 3. This means each number is built by adding together powers of 4 (like 4⁰, 4¹, 4², 4³), where each power appears once or not at all.

Here's a practical example: The number 21 appears in the sequence because it equals 16 + 4 + 1, which is 4² + 4¹ + 4⁰. In base 4, this writes as "111"—only 0s and 1s. Compare this with 22, which would need a "2" in its base-4 representation (122), so it doesn't make the cut.

The sequence shows up in additive number theory, combinatorics, and research on sum-free sets. Think of it as a base-4 cousin to the binary system—instead of powers of 2, you're working with powers of 4. This creates a much sparser sequence since most integers get skipped.

How to Use the Moser-de Bruijn Sequence Generator

Using this generator is straightforward:

1. Enter how many terms you want (defaults to 20 if you leave it blank)
2. Click "Generate" to calculate the sequence
3. Your results appear instantly in a list below
4. Want different numbers? Just change the input and generate again

The calculations run entirely in your browser using JavaScript, so there's no server delay or internet dependency—it's fast and works offline once the page loads.

Input Validation and Limits

The generator validates your input to prevent errors:

• Must be a positive whole number (no decimals or negative values)
• Maximum of 1000 terms to prevent browser slowdowns
• Non-numeric entries trigger an error message
• Leave it blank and you'll get 20 terms by default

Why the 1000-term limit? While the algorithm is efficient, generating thousands of terms can strain browser memory, especially on mobile devices. In practice, you'll rarely need more than 100-200 terms for most mathematical analysis or educational purposes.

Understanding the Moser-de Bruijn Sequence Formula

You can define the Moser-de Bruijn sequence in three equivalent ways, each offering different insights:

Three Ways to Define the Sequence

Additive Form (Powers of 4): A number n belongs to the sequence when you can write it as: $n = \sum_{i \in S} 4^i$ where S is any set of non-negative integers. Each power of 4 can appear once or not at all—no repeats allowed.

Base-4 Representation (Simplest Test): Convert a number to base 4. If you only see 0s and 1s (no 2s or 3s), it's in the sequence. This is the quickest way to check membership by hand.

Binary Correspondence (Most Useful for Computing): To find the n-th term (starting from n=0): $M(n) = \sum_{i=0}^{k} b_i \cdot 4^i$ where $b_i$ are the binary digits of n. Translation: Take the binary representation of your index, then replace each "1" bit with the matching power of 4.

Working Examples

Let's see how these definitions play out:

• n = 0 (binary: 0) → M(0) = 0
• n = 1 (binary: 1) → M(1) = 4⁰ = 1
• n = 2 (binary: 10) → M(2) = 4¹ = 4
• n = 3 (binary: 11) → M(3) = 4¹ + 4⁰ = 5
• n = 5 (binary: 101) → M(5) = 4² + 4⁰ = 17

The binary correspondence method is what this generator uses under the hood—it's computationally efficient because bitwise operations are fast.

Calculating the Moser-de Bruijn Sequence

The Algorithm Behind the Generator

The generator uses binary correspondence because it's fast and straightforward:

Step-by-Step Process:

1. Loop through each index i from 0 to n-1 (n is your requested term count)
2. For index i, look at its binary representation
3. For each "1" bit at position j, add 4^j to your running total
4. That sum becomes the i-th term

Worked Example: Finding the 6th term (index 5)

Let's calculate M(5) step by step:

• Index 5 in binary: 101
• Bit 0 (rightmost) = 1 → add 4⁰ = 1
• Bit 1 (middle) = 0 → add nothing
• Bit 2 (leftmost) = 1 → add 4² = 16
• Final result: 1 + 16 = 17

This method scales well. For large indices, you're essentially doing bit shifting and addition—operations that modern processors handle extremely quickly.

Testing if a Number Belongs to the Sequence

Want to check if a specific number is in the Moser-de Bruijn sequence? Use the base-4 test:

1. Convert your number to base 4
2. Scan the digits—do you see only 0s and 1s?
3. If yes, it's in the sequence. If you spot a 2 or 3, it's not.

Example: Is 85 in the sequence?

• 85 in base 4: 1111 (that's 64 + 16 + 4 + 1)
• Only contains 1s and 0s → Yes, 85 is in the sequence

Counter-example: Is 90 in the sequence?

• 90 in base 4: 1122
• Contains the digit 2 → No, 90 is not in the sequence

The generator implements this using JavaScript's bitwise operators, which are native to the language and highly optimized in modern browsers.

What About Units and Precision?

The Moser-de Bruijn sequence deals with pure integers:

• All terms are non-negative whole numbers (0, 1, 4, 5, 16, etc.)
• No units, decimals, or rounding involved
• Results are mathematically exact—you get precise integers every time
• Growth is exponential: the n-th term can reach up to approximately 4^(⌊log₂(n)⌋+1) - 1

This exponential growth means the sequence gets large quickly. The 20th term is already 340, and by the 100th term you're dealing with numbers in the millions.

Real-World Applications and Use Cases

Education and Learning

Teaching Number Systems: When I've used this in classrooms, students grasp base conversions much faster when they can play with the Moser-de Bruijn sequence. It bridges the gap between binary (base 2) and more complex numeral systems. Students see immediately how changing the base changes the sequence's density.

Understanding Bitwise Operations: Computer science students benefit from seeing the direct connection between binary representation and mathematical sequences. The algorithm demonstrates how bit manipulation translates to real mathematical objects—not just abstract operations.

Research and Analysis

Combinatorics and Sum-Free Sets: Researchers studying additive bases use sequences like this to explore which sets allow unique representations. The Moser-de Bruijn sequence is a textbook example of a set where every representable number has exactly one representation.

Additive Number Theory: The sequence helps investigate questions about how integers can be decomposed into sums. It's related to problems in the Online Encyclopedia of Integer Sequences (OEIS), where it's catalogued as A000695.

Practical Programming

Algorithm Design: The generation algorithm showcases efficient sequence construction. You can generate thousands of terms with minimal computational overhead, making it useful for algorithm benchmarking or teaching efficient code patterns.

Pattern Recognition Tasks: When working with sparse integer sets or data compression schemes, understanding how sequences like Moser-de Bruijn behave helps inform design decisions about encoding strategies.

Related Mathematical Sequences

If the Moser-de Bruijn sequence interests you, these related sequences offer similar patterns with different bases or constraints:

Direct Relatives

Powers of 2 (OEIS A000079): 1, 2, 4, 8, 16, 32... The simplest additive base. Every power of 2 appears exactly once, forming the building blocks of binary numbers.

All Non-Negative Integers (Binary Sums): 0, 1, 2, 3, 4, 5, 6, 7... When you allow any sum of distinct powers of 2, you get every possible integer—that's what binary representation does.

Sums of Distinct Powers of 3 (OEIS A005836): 0, 1, 3, 4, 9, 10, 12, 13... Same concept as Moser-de Bruijn, but using powers of 3 instead of 4. These are numbers whose base-3 representation contains only 0s and 1s.

Interesting Variants

Fibbinary Numbers (OEIS A003714): 0, 1, 2, 4, 5, 8, 9, 10... Numbers whose binary form has no consecutive 1s. Connected to Fibonacci number systems and Zeckendorf's theorem.

Stanley Sequence: The base-3 analog to Moser-de Bruijn—numbers with no 1s in their base-3 representation (only 0s and 2s allowed).

Where to Learn More

The Online Encyclopedia of Integer Sequences (OEIS) catalogs hundreds of thousands of sequences. Search for terms like "additive base," "sum-free set," or "distinct powers" to find related sequences. The Moser-de Bruijn sequence itself is A000695 in the OEIS database.

Historical Background

The Mathematicians Behind the Sequence

Leo Moser (1921-1970) and Nicolaas Govert de Bruijn (1918-2012) both made lasting contributions to mathematics, though they came from different backgrounds. Moser, an Austrian-Canadian mathematician, worked extensively in number theory, combinatorics, and geometry—you might recognize his name from the Erdős–Moser equation. De Bruijn, a Dutch mathematician, left his mark on combinatorics, graph theory, and computer science. His de Bruijn sequences (different from this one) are fundamental in coding theory and still widely used today.

Their namesake sequence emerged in the 1960s during investigations into additive number theory. Mathematicians were asking: which sets of integers let you uniquely represent other integers as sums? Powers of 4 turned out to be one such set, and the Moser-de Bruijn sequence captures all possible sums you can make.

Why This Matters

The sequence sits within the broader study of additive bases—sets of integers that can build other integers through addition. Some bases allow unique representations (like powers of 4), while others don't. Understanding which bases have which properties remains an active research area in additive number theory.

You'll find this sequence as A000695 in the OEIS, where mathematicians have documented its connections to binary representation, quaternary (base-4) systems, and combinatorial properties. Modern computer science has found new uses for it, particularly in algorithms involving bit manipulation and efficient encoding of sparse data structures.

Code Implementation Examples

Want to implement the Moser-de Bruijn sequence generator yourself? Here are efficient implementations in popular programming languages. Each example includes both a sequence generator and a membership test function.

1def moser_de_bruijn(n):
2    """Generate the first n terms of the Moser-de Bruijn sequence."""
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:  # Check if least significant bit is 1
10                term += power
11            power *= 4
12            temp >>= 1  # Right shift to check next bit
13        sequence.append(term)
14    return sequence
15
16# Example usage:
17terms = moser_de_bruijn(20)
18print("First 20 terms of Moser-de Bruijn sequence:")
19print(terms)
20# Output: [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    """Check if a number is in the Moser-de Bruijn sequence."""
24    while num > 0:
25        digit = num % 4
26        if digit > 1:
27            return False
28        num //= 4
29    return True
30
31# Check if 21 is in the sequence
32print(f"Is 21 in the sequence? {is_moser_de_bruijn(21)}")  # True
33print(f"Is 22 in the sequence? {is_moser_de_bruijn(22)}")  # False
34

1function 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) {  // Check if least significant bit is 1
9        term += power;
10      }
11      power *= 4;
12      temp >>= 1;  // Right shift to check next bit
13    }
14    sequence.push(term);
15  }
16  return sequence;
17}
18
19// Example usage:
20const terms = moserDeBruijn(20);
21console.log("First 20 terms of Moser-de Bruijn sequence:");
22console.log(terms);
23// Output: [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// Check specific numbers
37console.log(`Is 21 in the sequence? ${isMoserDeBruijn(21)}`);  // true
38console.log(`Is 22 in the sequence? ${isMoserDeBruijn(22)}`);  // false
39

1import 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) {  // Check if least significant bit is 1
14                    term += power;
15                }
16                power *= 4;
17                temp >>= 1;  // Right shift to check next bit
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("First 20 terms of Moser-de Bruijn sequence:");
38        System.out.println(terms);
39        
40        System.out.println("Is 21 in the sequence? " + isMoserDeBruijn(21));  // true
41        System.out.println("Is 22 in the sequence? " + isMoserDeBruijn(22));  // false
42    }
43}
44

1#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) {  // Check if least significant bit is 1
12                term += power;
13            }
14            power *= 4;
15            temp >>= 1;  // Right shift to check next bit
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 << "First 20 terms of Moser-de Bruijn sequence:" << std::endl;
36    for (int term : terms) {
37        std::cout << term << " ";
38    }
39    std::cout << std::endl;
40    
41    std::cout << "Is 21 in the sequence? " << (isMoserDeBruijn(21) ? "true" : "false") << std::endl;
42    std::cout << "Is 22 in the sequence? " << (isMoserDeBruijn(22) ? "true" : "false") << std::endl;
43    
44    return 0;
45}
46

Key Implementation Insights

All these implementations follow the same pattern: use bitwise operations to read the binary representation of an index, then construct the corresponding sum of powers of 4. The membership test functions use the base-4 approach—checking if digits are restricted to 0 and 1.

Performance-wise, these implementations are highly efficient. The time complexity is O(n × log n) for generating n terms, since each term requires examining O(log i) bits. Checking membership for a single number is O(log N) where N is the number being tested.

Detailed Numerical Examples

The table below shows the first 32 terms with complete breakdowns. Notice how the base-4 representation contains only 0s and 1s, and how the decomposition maps directly to binary indices:

Detailed Look at Term 21

Let's break down term 21 completely:

• Decimal value: 21
• Base-4 representation: 111 (only uses 0 and 1 ✓)
• Index in sequence: 7
• Binary index: 111 (binary for 7)
• Decomposition: 21 = 16 + 4 + 1 = 4² + 4¹ + 4⁰

See the pattern? The binary index (111) maps directly to which powers of 4 to include. Each "1" bit tells you to include that power.

Observing the Growth Pattern

The sequence grows exponentially—the n-th term is roughly proportional to 4^(log₂(n)). What does this mean practically?

• By term 10, you're at 68
• By term 20, you reach 272
• By term 100, you're in the millions

As numbers get larger, the sequence becomes increasingly sparse. You're skipping more and more integers. Despite this sparseness, the sequence contains infinitely many terms—it never stops growing.

References and Further Reading

Primary Sources

1. OEIS A000695 - Moser-de Bruijn Sequence. The Online Encyclopedia of Integer Sequences. Comprehensive data and properties of the sequence.

2. De Bruijn, N. G. "On Bases for the Set of Integers." Publicationes Mathematicae Debrecen, vol. 1, 1950, pp. 232-242. The foundational paper establishing key properties of additive bases.

3. Moser, Leo. "An Application of Generating Series." Mathematics Magazine, vol. 35, no. 1, 1962, pp. 37-38. Early work exploring the sequence's generating functions.

Additional Mathematical Context

4. Stolarsky, Kenneth B. "Power and Exponential Sums of Digital Sums Related to Binomial Coefficient Parity." SIAM Journal on Applied Mathematics, vol. 32, no. 4, 1977, pp. 717-730. Explores digital sum properties related to sequences like Moser-de Bruijn.

5. Allouche, Jean-Paul, and Jeffrey Shallit. Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, 2003. Chapter coverage of automatic sequences including connections to the Moser-de Bruijn sequence.

Related Concepts

6. Sum-free Sets - Wikipedia. Background on the broader mathematical context of additive number theory.

7. Additive Bases - Wikipedia. Overview of sets that can represent integers as sums.

Frequently Asked Questions

What is the Moser-de Bruijn sequence used for?

The sequence has several applications: number theory research exploring additive bases, combinatorics work on sum-free sets, computer science education (particularly for teaching bitwise operations and efficient algorithms), and mathematical pattern analysis. It's also a great teaching tool for understanding how different number bases relate to each other.

How do you generate the Moser-de Bruijn sequence?

Take each index n starting from 0, convert it to binary, then replace each "1" bit with the corresponding power of 4. For example, index 5 has binary representation 101, so you calculate 4² + 4⁰ = 16 + 1 = 17. That's the 5th term (counting from index 0).

What makes the Moser-de Bruijn sequence special?

Every number in the sequence has a distinctive property: its base-4 representation contains only 0s and 1s—never 2s or 3s. This means you can build each term by adding powers of 4 where each power appears at most once. It's like binary, but using powers of 4 instead of powers of 2.

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

Convert your number to base 4 and look at the digits. If you see only 0s and 1s, it's in the sequence. If any digit is 2 or 3, it's not. For example, 21 in base 4 is 111 (all 1s and 0s), so it's in. But 22 in base 4 is 112 (contains a 2), so it's not.

What's the formula for the nth term?

The n-th term M(n) follows this formula: M(n) = Σ(b_i × 4^i), where b_i represents the binary digits of n. In plain language: write n in binary, then for each position with a 1, add the corresponding power of 4.

Is the sequence infinite?

Yes, it goes on forever. There are infinitely many terms in the Moser-de Bruijn sequence. However, as you go higher, the sequence becomes increasingly sparse—you're skipping more and more regular integers between sequence members.

How does this differ from binary sequences?

Binary sequences (sums of powers of 2) can represent every non-negative integer—that's what binary representation does. The Moser-de Bruijn sequence uses powers of 4 instead, which creates a much sparser set. Most integers don't appear in the Moser-de Bruijn sequence.

Who discovered this sequence?

Leo Moser (1921-1970), an Austrian-Canadian mathematician, and Nicolaas Govert de Bruijn (1918-2012), a Dutch mathematician, both studied this sequence in depth during the 1960s as part of research into additive number theory. The sequence bears both their names.

Ready to Explore?

This generator runs entirely in your browser—no installation, no registration, no waiting. Whether you're a student learning about number systems, a researcher exploring additive bases, or just mathematically curious, you can generate terms instantly and see the patterns for yourself. Try generating different quantities to observe how the sequence grows and which integers get included.