18
\$\begingroup\$

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 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
\$\endgroup\$
4
  • \$\begingroup\$ Is there a maximum n that the program is required to handle? \$\endgroup\$
    – Tbw
    Nov 23, 2023 at 3:19
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – alephalpha
    Nov 23, 2023 at 3:36
  • \$\begingroup\$ It may be too late to ask, but could we output 2 distinct and consistent values instead of \$-1\$ and \$1\$? \$\endgroup\$
    – Arnauld
    Nov 23, 2023 at 8:45
  • \$\begingroup\$ @Arnauld No. The Rudin-Shapiro sequence is by definition a sequence of 1s and −1s. \$\endgroup\$
    – alephalpha
    Nov 23, 2023 at 9:20

39 Answers 39

1
2
3
\$\begingroup\$

Vyxal, 5 bytes

d⋏b∑Ǎ

Try it Online!

Uses Command Master's trick.

    Ǎ # -1 **
   ∑  # Sum of
  b   # binary of
 ⋏    # n &
d     # n * 2
\$\endgroup\$
3
\$\begingroup\$

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))
\$\endgroup\$
3
  • \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Nov 25, 2023 at 20:44
  • \$\begingroup\$ 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. \$\endgroup\$
    – m90
    Nov 29, 2023 at 17:01
  • \$\begingroup\$ @m90 thanks! post has been updated \$\endgroup\$ Dec 1, 2023 at 5:45
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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!

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

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

\$\endgroup\$
1
\$\begingroup\$

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.

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

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.
\$\endgroup\$
1
\$\begingroup\$

PARI/GP, 38 bytes

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

Attempt This Online!

\$\endgroup\$
1
\$\begingroup\$

Swift 5.9, 63 38 bytes

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.