# Rudin-Shapiro sequence

The Rudin-Shapiro sequence is a sequence of $$\1\$$s and $$\-1\$$s defined as follows: $$\r_n = (-1)^{u_n}\$$, where $$\u_n\$$ is the number of occurrences of (possibly overlapping) $$\11\$$ in the binary representation of $$\n\$$.

For example, $$\r_{461} = -1\$$, because $$\461\$$ in binary is $$\111001101\$$, which contains $$\3\$$ occurrences of $$\11\$$: $$\\color{red}{\underline{11}}1001101\$$, $$\1\color{red}{\underline{11}}001101\$$, $$\11100\color{red}{\underline{11}}01\$$.

This is sequence A020985 in the OEIS.

The first few terms of the sequence are:

1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, -1, -1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, -1, -1, -1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, -1, -1, 1, -1, -1, -1, -1, 1, -1, -1, 1, -1, 1, 1, 1, -1, -1, -1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, -1, -1, 1, -1, 1


Generate the Rudin-Shapiro sequence.

As with standard challenges, you may choose to:

• Take an integer $$\n\$$ as input and output the $$\n\$$th term of the sequence.
• Take an integer $$\n\$$ as input and output the first $$\n\$$ terms of the sequence.
• Take no input and output the sequence indefinitely.

This is , so the shortest code in bytes in each language wins.

## Test cases

0 -> 1
1 -> 1
2 -> 1
3 -> -1
4 -> 1
5 -> 1
6 -> -1
7 -> 1
8 -> 1
9 -> 1
10 -> 1
11 -> -1
12 -> -1
13 -> -1
14 -> 1
15 -> -1
16 -> 1
17 -> 1
18 -> 1
19 -> -1

• Is there a maximum n that the program is required to handle?
– Tbw
Nov 23, 2023 at 3:19
• @Tbw No. It depends on your language's integer type. If your language uses a floating-point type (e.g. JavaScript), floating-point inaccuracies are allowed. Nov 23, 2023 at 3:36
• It may be too late to ask, but could we output 2 distinct and consistent values instead of $-1$ and $1$? Nov 23, 2023 at 8:45
• @Arnauld No. The Rudin-Shapiro sequence is by definition a sequence of 1s and −1s. Nov 23, 2023 at 9:20

# Vyxal, 5 bytes

d⋏b∑Ǎ


Try it Online!

Uses Command Master's trick.

    Ǎ # -1 **
∑  # Sum of
b   # binary of
⋏    # n &
d     # n * 2


# WebAssembly (text), 131 130 bytes

(func(param i32)(result i32)i32.const 1
i32.const -1
local.get 0
local.get 0
i32.const 2
i32.mul
i32.or
i32.popcnt
i32.ctz
select)


A WebAssembly function that, given n as a 32-bit integer, returns the nth term of the sequence.

-1 byte thanks to @m90

Equivalent to the pseudocode ctz(popcnt(n | n*2)) ? 1 : -1, which is equivalent to ctz(popcnt(n & n*2)) ? 1 : -1. If the result of popcnt is odd, then ctz will return 0. Else (if the result of popcnt is even), ctz will return a non-zero value. Therefore, it is also equivalent to the pseudocode popcnt(n & n*2) & 1 ? -1 : 1.

Line endings are counted as a single byte (\n).

For a fully valid WebAssembly text module (which does not export the function), 139 138 bytes:

(module(func(param i32)(result i32)i32.const 1
i32.const -1
local.get 0
local.get 0
i32.const 2
i32.mul
i32.or
i32.popcnt
i32.ctz
select))


For a fully valid WebAssembly text module, where the function f can be accessed by the (JavaScript) code that loads the module, 151 150 bytes:

(module(func(export "f")(param i32)(result i32)i32.const 1
i32.const -1
local.get 0
local.get 0
i32.const 2
i32.mul
i32.or
i32.popcnt
i32.ctz
select))

• Welcome to Code Golf, and nice answer! Nov 25, 2023 at 20:44
• Improvement: change and to or. Compared to the and result, the or result has an extra 1 bit for every 01 or 10 bit pair in the bits of the original number with 0 bits added at the start and end. The number of 01 pairs is necessarily equal to the number of 10 pairs, thus the number of extra 1 bits in the or result is even.
– m90
Nov 29, 2023 at 17:01
• @m90 thanks! post has been updated Dec 1, 2023 at 5:45

# ARM64 machine code, 24 bytes

This function takes a 64-bit integer in x0 and returns the result in x0 as well, following usual calling conventions.

8a000401
d2800020
ab010021
da803400
54ffffc1
d65f03c0


Assembly source:

        .global rudin_shapiro
.text
.balign 4
rudin_shapiro:
and     x1, x0, x0, lsl #1
// Now x1 has a 1 bit for each 11 in the input.  It remains to
// compute its parity.
mov     x0, #1
next_bit:
adds    x1, x1, x1      // shift left into carry flag
cneg    x0, x0, cs      // negate x0 if a 1 was shifted out
b.ne    next_bit        // continue if result of adds was not zero

ret


# Scala 3, 5755 52 bytes

Saved 2 bytes thanks to @m90

Saved 3 bytes thanks to @ceilingcat

n=>1-Integer.parseInt((n&n*2).toBinaryString,13)%2*2


Attempt This Online!

• Improvement: remove the parentheses around n*2. (This works the same way because * has higher precedence than &.)
– m90
Nov 29, 2023 at 17:04

# Octave, 30 bytes

@(n)hadamard(2^n*2)(n+1,2*n+1)


Try it online!

This sequence are the entries $$\W_{n+1,\ 2n+1}\$$ of the infinite Walsh matrix $$\W\$$.

# Wolfram Language (Mathematica), 48 12 bytes

-36 bytes thanks to @alephalpha

RudinShapiro


Takes $$\n\$$ as the input and outputs the $$\n\$$-th term of the Rudin-Shapiro sequence.

• RudinShapiro is already a valid answer. You don't need to add [n]. Dec 9, 2023 at 0:27
• @alephalpha How would the byte count be calculated then? ByteCount[RudinShapiro] just returns 0 in Wolfram Cloud. Dec 11, 2023 at 14:28
• There are 12 ASCII chars, so 12 bytes. Dec 11, 2023 at 15:46

# Haskell + hgl, 19 bytes

pw(-1)<sm<pa ml<bs2


Attempt This Online!

## Explanation

• bs2 convert to binary (integer values)
• pa ml multiply consecutive values
• sm sum
• pw(-1) raise -1 to the power of the result

# 19 bytes

pw(-1)<l<fa[T,T]<bi


Attempt This Online!

## Explanation

• bi convert to binary (boolean values)
• fa[T,T] find all occurrences of [T,T] (11)
• l get the number of such occurrences
• pw(-1) raise -1 to the power of the result.

# 19 bytes

pw(-1)<cnT<pa mp<bi


Attempt This Online!

## Explanation

• bi convert to binary (boolean values)
• pa mp combine consecutive values with and
• cnT count the number of Trues
• pw(-1) raise -1 to the power of the result

# Reflection

• Here I expressed a need for a shortcut to (-1). I still have not implemented that.
• pw(-1) on it's own is probably worth having a built in.
• Having a shortcut for pa mp would be useful.
• There should be a function to take from a certain base to an integer.
• There should be a built in that combines l and fa to count the number of occurrences of a substring.

# PARI/GP, 38 bytes

f(n)=(-1)^hammingweight(bitand(n,n*2))


Attempt This Online!

# Swift 5.9, 63 38 bytes

let f={-($0*2&$0).nonzeroBitCount%2|1}