Free Rudin-Shapiro Sequence Generator Online

Rudin-Shapiro Sequence Generator

The Rudin-Shapiro sequence (also known as the Golay-Rudin-Shapiro sequence) is a classical binary sequence in combinatorics and harmonic analysis. Each term depends solely on the number of (possibly overlapping) occurrences of the bit-pair "11" in the binary representation of its index. This tool lets you generate as many terms as you need in either the binary (0, 1) or signed (±1) form, with full control over separator, starting index, and index labels.

Definition and Formula

For a non-negative integer n, write n in binary. Count the number of times the pattern "11" appears (possibly overlapping). Call this count c(n).

In the binary form: b(n) = 0 if c(n) is even; b(n) = 1 if c(n) is odd.
In the signed form: r(n) = +1 if c(n) is even; r(n) = −1 if c(n) is odd.

The first 16 values of the binary form are: 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0 (starting at n = 0).

Key Mathematical Properties

Bounded partial sums: One of the most remarkable properties is that the absolute value of the partial sums $\sum_{n=0}^{N-1} r(n) e^{i\theta n}$ is bounded by $\sqrt{2(N+1)}$ for all real $\theta$, making it a flat polynomial on the unit circle.
Almost perfect balance: The proportion of +1s approaches 50% as $N \to \infty$. More precisely, the number of +1s up to index $N$ is $N/2 + O(\sqrt{N})$.
Self-similarity: The sequence satisfies the recursion: $r(2n) = r(n)$ and $r(2n+1) = (-1)^n r(n)$.
Automaton: The sequence is 2-automatic — it can be produced by a 3-state deterministic finite automaton reading the binary digits of $n$ from left to right.

How to Use This Tool

Enter the number of terms you want to generate (up to 10,000).
Set the start index if you want a subsequence starting from an offset.
Choose between binary (0/1) or signed (±1) output.
Pick a separator (comma, space, newline, etc.) for the output.
Optionally enable index labels to see which term index each value belongs to.
Click Generate Sequence (or simply change any parameter — the output updates automatically).

Applications

The Rudin-Shapiro sequence has applications in coding theory, digital signal processing, and harmonic analysis. It was independently discovered by Marcel Golay (1951), Walter Rudin (1959), and Harold Shapiro (1952) in different contexts. Shapiro discovered it while looking for polynomials with bounded $L^\infty$ norms on the unit circle. Rudin used it to construct a bounded analytic function. Golay noticed it as a pattern of complementary pairs in coding theory.

Frequently Asked Questions

What is the Rudin-Shapiro sequence?

The Rudin-Shapiro sequence is an infinite binary sequence where the $n$-th term is determined by the parity of the number of (possibly overlapping) occurrences of the pattern "11" in the binary representation of $n$. If the count is even the term is 0 (or +1); if odd, it is 1 (or −1).

Why is it called the Golay-Rudin-Shapiro sequence?

The sequence was independently discovered by three researchers: Marcel Golay in 1951 in the context of complementary codes, Harold Shapiro in 1952 in his senior thesis on polynomials on the unit circle, and Walter Rudin in 1959 in harmonic analysis. All three names are used in the literature.

What is the difference between the binary and signed forms?

The binary form outputs 0 and 1: 0 when an even number of "11" patterns are found, 1 otherwise. The signed form outputs +1 and −1, which is more natural for Fourier analysis and harmonic analysis applications. The signed form is just $(-1)^{b(n)}$ where $b(n)$ is the binary form.

Is the sequence balanced (equal numbers of 0s and 1s)?

Yes, asymptotically. The density of 0s and 1s both approach 50% as the number of terms grows. More precisely, for large $N$, the number of 0s among the first $N$ terms differs from $N/2$ by at most $O(\sqrt{N})$. This balance makes it valuable in signal processing and coding theory.

Can I compute a specific term r(n) directly?

Yes. Write $n$ in binary, then count the number of times the two adjacent bits "11" appear (including overlapping matches). If this count is even, r(n) = 0 (or +1); if odd, r(n) = 1 (or −1). You can also use this tool by setting the start index to $n$ and the count to 1.

What is the recursion formula for the Rudin-Shapiro sequence?

In the signed form, the sequence satisfies: $r(0) = 1$, $r(2n) = r(n)$, and $r(2n+1) = (-1)^n \cdot r(n)$. This recursive structure means the sequence is 2-automatic — computable by a finite automaton reading the binary digits of $n$.