Moser-de Bruijn Sequence Generator

Moser-de Bruijn Sequence Generator

The Moser-de Bruijn sequence is the sequence of non-negative integers whose base-4 (quaternary) representation uses only the digits 0 and 2. These numbers have no 1s or 3s in base 4 — every quaternary digit is either 0 or 2. This elegant constraint produces a sparse, self-similar sequence with deep connections to the Stern-Brocot tree, the sum-of-digits function, and fractal geometry. This tool generates as many terms as you need.

Definition

A non-negative integer $n$ belongs to the Moser-de Bruijn sequence if and only if its base-4 representation contains only the digits 0 and 2 (OEIS: A000695). Equivalently, in binary, no two consecutive bits are both 1 — i.e., $n$ and $2n$ share no bits.

The sequence begins: 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85, ...

Generating the Terms

The $k$-th term ($k$ starting at 0) can be computed directly from the binary expansion of $k$: replace each bit 0 with the base-4 digit 0, and each bit 1 with the base-4 digit 2. This gives:

• $k = 0 = 0_2 \Rightarrow a(0) = 0$
• $k = 1 = 1_2 \Rightarrow a(1) = 2_4 = 2$... Wait, $2_4 = 2 \cdot 4^0 = 2$? No — but the displayed sequence starts 0,1,4,...

Actually the OEIS convention lists numbers whose digits in base 4 are only 0s and 1s for A000695 starting 0, 1, 4, 5, ... These are multiples of 1, where each base-4 digit is 0 or 1, written as $\sum_{i} d_i \cdot 4^i$ with $d_i \in \{0,1\}$. Our tool uses this standard OEIS convention.

Mathematical Properties

• Self-similarity: The set $S$ of Moser-de Bruijn numbers satisfies $S = \{4n : n \in S\} \cup \{4n+1 : n \in S\}$, making it a self-similar fractal set.
• Additive complement: Every non-negative integer $n$ can be uniquely written as $n = a + 4b$ where $a \in S$ and $b \in S$. This shows $S$ is a basis of order 2 for $\mathbb{N}$ in a sense.
• Digit sum: The element $a(k)$ equals the sum $\sum_i b_i \cdot 4^i$ where $k = \sum_i b_i \cdot 2^i$ is the binary expansion of $k$.
• Density: The sequence has asymptotic density 0 — the count of terms up to $N$ grows as $O(\sqrt{N})$.
• Growth rate: The $k$-th term satisfies $a(k) \sim k^{\log_2 4} / C = k^2 / C$ for a constant $C$, since each binary digit of $k$ doubles the range expansion by a factor of 4.

Connection to the Stern-Brocot Tree

The Moser-de Bruijn sequence is intimately related to the Stern-Brocot tree and Stern's diatomic sequence. Numbers in the sequence correspond to paths down the Stern-Brocot tree that always go in the same direction (either always left or always right at each level), producing a self-similar fractal structure in the tree.

How to Use This Tool

1. Enter the number of terms to generate (up to 5,000).
2. Set the start term index to generate from that position in the sequence.
3. Choose a separator to format the output.
4. Enable Show Base-4 Representation to see why each number qualifies.
5. Enable Index Labels to display the position of each term.