Rudin-Shapiro sequence

Question

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

Task

Generate the Rudin-Shapiro sequence.

As with standard sequence 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 code-golf, 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

Answer 1

Vyxal, 5 bytes

d⋏b∑Ǎ

Try it Online!

Uses Command Master's trick.

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

Answer 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.

ctz, popcnt

-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))

Answer 3

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

Answer 4

Scala 3, 57 55 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!

Answer 5

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\$.

Answer 6

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.

Answer 7

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.

Answer 8

PARI/GP, 38 bytes

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

Attempt This Online!

Answer 9

Swift 5.9, 63 38 bytes

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