How is each term actually computed?

For index n (starting at 0), the tool writes n in binary, then reinterprets that exact same digit string as a base-4 number instead of base-2. For example, n = 5 is "101" in binary; read as base 4, "101" equals 1×16 + 0×4 + 1 = 17.

Why does the term for n = 2 jump to 4?

2 in binary is "10". Read as base 4, "10" equals 1×4 + 0 = 4. Because reinterpreting a base-2 digit string in base 4 grows the value roughly by a factor of 4 for every extra bit, later terms grow much faster than n itself.

Why does the tool use BigInt instead of ordinary numbers?

Because each additional bit in n's binary form roughly quadruples the resulting term, values grow as 4^(bit length of n). For a few thousand terms this comfortably exceeds JavaScript's safe integer range, so the tool accumulates every term with BigInt arithmetic to stay exact.

Is there a limit on how many terms I can generate?

Yes, generation is capped at 10,000 terms to keep the output and the page responsive.

Moser-de Bruijn Sequence Generator - Sums of Distinct Powers of 4

Overview

Introduction

The Moser-de Bruijn sequence is formed by a single, easy-to-state trick: take an index's binary digits and read that same digit pattern back as a base-4 number instead.

This tool generates as many terms as you need with exact BigInt arithmetic, since the values grow quickly enough that ordinary floating-point numbers would lose precision after only a few dozen terms.

What Is Generate Moser-de Bruijn Sequence?

It's the sequence of non-negative integers expressible as a sum of distinct powers of 4 (that is, numbers whose base-4 representation uses only the digits 0 and 1). Equivalently, term(n) is n's binary digit string reread as a base-4 number.

It's named for Leo Moser and Nicolaas Govert de Bruijn, and is notable for the curious identity that every non-negative integer can be written uniquely as a sum or difference of two Moser-de Bruijn numbers.

How Generate Moser-de Bruijn Sequence Works

For each index n starting at 0, the tool converts n to its binary string using standard base-2 conversion.

It then walks that string digit by digit, building up a BigInt value with `value = value * 4 + digit` for each bit, which is exactly the arithmetic of interpreting the same digit string in base 4 instead of base 2.

Because this accumulation uses BigInt the whole way through, terms remain exact no matter how large they grow within the 10,000-term cap.

When To Use Generate Moser-de Bruijn Sequence

Use it to generate exact reference values for verifying a Moser-de Bruijn implementation, or to explore the sequence's sum-of-distinct-powers-of-4 structure.

It's also a clean example for teaching how reinterpreting digits in a different base creates a rapidly growing but exactly computable sequence.

Often used alongside Generate Rudin-Shapiro Sequence and Generate Baum-Sweet Sequence.

Features

Advantages

Uses BigInt throughout, so terms stay exact even once they exceed JavaScript's safe integer range.
Computes every term directly from its index's binary digits, with no dependency on previously computed terms.

Limitations

Term count is capped at 10,000; since values grow as roughly 4^(bit length of n), the very last terms in a large run can become extremely long numbers.
Only the standard 0-indexed convention is offered.

Examples

First 9 terms

Input

Output

0, 1, 4, 5, 16, 17, 20, 21, 64

n = 2 is "10" in binary, read as base 4 that's 1×4 + 0 = 4. n = 3 is "11", read as base 4 that's 1×4 + 1 = 5. n = 8 is "1000", read as base 4 that's 1×64 = 64.

Best Practices & Notes

Best Practices

If you need the sequence's alternate "sum of distinct powers of 4" framing rather than the binary-reinterpretation framing, remember they're equivalent, so either mental model produces the same terms.

Developer Notes

Each term is built by iterating over `n.toString(2)` and folding `value = value * 4n + (bit === "1" ? 1n : 0n)` across the characters, which is arithmetically identical to `BigInt(parseInt(n.toString(2), 4))` but avoids round-tripping through a `parseInt`/`Number` intermediate that would reintroduce floating-point limits for large terms.

Generate Moser-de Bruijn Sequence Use Cases

Generating exact reference values to validate a Moser-de Bruijn implementation in another language
Demonstrating the sum-of-distinct-powers-of-4 identity in a number theory course
Exploring how digit-reinterpretation across bases produces structured integer sequences

Common Mistakes

Computing terms with ordinary floating-point numbers once the term count grows large; the sequence's rapid roughly-4^n growth exceeds safe integer precision well before 10,000 terms, which is why this tool accumulates every term as a BigInt.

Tips

Cross-check small term counts (like the first 9) against OEIS A000695 before trusting a larger run.

Generate Moser-de Bruijn Sequence