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

Python, 33 bytes

lambda n:int(bin(n&n*2),13)%2*2-1

Try it online!

Based on Command Master's solution, but using the base-13 trick. We can tie with 1|~int(bin(n&n*2),13)%-2, or 1|(n&n*2).bit_count()%-2 in Python 3.10.

Python 2, 32 bytes

f=lambda n:n<1or n%4/3*-2^f(n/2)

Try it online!

Outputs True for 1 for n=0. 34 bytes in Python 3 due to // twice. Weirdly, it seems shorter to switch between 1 and -1 and back by (conditionally) xor-ing -2 rather than multiplying by -1. It feels like there should be a way to use space after the or.

Answer 2

Python, 36 bytes

lambda n:(-1)**bin(n&n*2).count('1')

Attempt This Online!

Python 3.10+, 34 bytes, thanks to @xnor

lambda n:(-1)**(n&n*2).bit_count()

Attempt This Online!

Answer 3

Jelly, 6 bytes

BẠƝS-*

A monadic Link that accepts a non-negative integer and yields the Rudin-Shapiro value.

Try it online!

How?

BẠƝS-* - Link: non-negative integer, N
B      - convert N to binary
  Ɲ    - for neighbouring pairs:
 Ạ     -   all? -> 1 if [1,1] else 0
   S   - sum these
    -  - literal -1
     * - exponentiate

Answer 4

x86-64 machine code, 13 bytes

B0 01 D1 E1 73 04 79 02 F6 D8 75 F6 C3

Try it online!

Following the fastcall calling convention, this takes a 32-bit integer n in ECX and returns an 8-bit integer in AL.

In assembly:

f:  mov al, 1       # Set AL to 1.
r:  shl ecx, 1      # Left shift ECX by 1.
    jnc e           # Jump if CF is 0. CF is the bit shifted off the top.
    jns e           # Jump if SF is 0. SF is the top bit after the shift.
    neg al          # (If neither was true: both bits were 1) Negate AL.
e:  jnz r           # Jump back, to repeat, if the last calculated value
                    #  (which may be ECX or AL) is nonzero.
    ret             # Return.

---

Another solution, 15 bytes

8D 04 09 21 C1 F3 0F B8 C1 D1 E8 D6 0C 01 C3

Try it online!

In assembly:

f:  lea eax, [ecx + ecx]    # Set EAX to 2n.
    and ecx, eax    # Bitwise AND of n and 2n; this has a 1 for each 11 in n.
    popcnt eax, ecx # Set EAX to the number of 1 bits in that value.
    shr eax, 1      # Right shift by 1. The low bit goes into CF.
    .byte 0xD6      # Undocumented SALC instruction -- set AL to -CF.
    or al, 1        # Bitwise OR with 1: 0 becomes 1, -1 remains -1.
    ret             # Return.

Answer 5

05AB1E, 7 bytes

b11¢®sm

Takes \$n\$ as input, and outputs the \$n^{th}\$ term.

Try it online or verify the infinite sequence.

Here an equal-bytes alternative:

bü*OÈ·<

Try it online or verify the infinite sequence.

Explanation:

b        # Convert the (implicit) input-integer to a binary-string
 11¢     # Pop and count the amount of "11" substrings
    ®    # Push -1
     s   # Swap
      m  # Pop both, and push -1 to the power `binary(input).count("11")`
         # (after which the resulting 1 or -1 is output implicitly)

b        # Convert the (implicit) input-integer to a binary-string
 ü       # Pop it, and for each overlapping pair of bits:
  *      #  Multiply them together
         #  (1 if [1,1]; 0 if [0,0],[0,1],[1,0])
   O     # Take the sum of this list
    È    # Check if this sum is even (1 if even; 0 if odd)
     ·   # Double it (2 if even; 0 if odd)
      <  # Decrease it by 1 (1 if even; -1 if odd)
         # (after which the resulting 1 or -1 is output implicitly)

Answer 6

Uiua, 13 bytes

ⁿ:¯1/+⬚0⌕1_1⋯

Try it!

ⁿ:¯1/+⬚0⌕1_1⋯
            ⋯  # bits
        ⌕1_1   # search for [1 1]
      ⬚0       # filling tiny arrays with excess zeros
    /+         # sum (count occurrences)
ⁿ:¯1           # raise negative one to this

Answer 7

J, 12 bytes

_1^1#.2*/\#:

Try it online!

Answer 8

Java, 26 25 bytes

n->1|-n.bitCount(n&n*2)%2

-1 byte thanks to @Neil.

Takes \$n\$ as input, and outputs the \$n^{th}\$ term.

Try it online.

Explanation:

n->                     // Method with Integer parameter and integer return-type
   1|                   //  Return 1 bitwise-OR'ed with:
     -                  //   The negative value of:
      n.bitCount(       //    The amount of bits in:
                 n      //     n
                  &n*2) //     Bitwise-AND'ed with doubled n
     %2                 //   Modulo-2

• The n.bitCount(n&n*2) is ported from @CommandMaster's Python answer, so make sure to upvote that answer as well!
• The 1|-...%2 is shorter than Math.pow(-1,...) in Java.

Answer 9

R, 31 bytes

\(x)(-1)^sum(x%/%2^(0:30)%%4>2)

Attempt This Online!

A function taking an integer and returning -1 or 1. I’ve assumed integers in the range 0 to 2^31 - 1, since that is the range for non-negative integers in R.

Answer 10

Japt, 7 bytes

Jp¢ä* x

Try it or run it on each n from 0 to 20

Explanation:

J        -1
 p       to the power of
  ¢        the input in binary
   ä       each pair of digits reduced by
    *        multiplication
      x    sum

Answer 11

CP-1610 machine code, 12 DECLEs¹ = 15 bytes

_{1. CP-1610 instructions are encoded with 10-bit values (0x000 to 0x3FF), known as DECLEs. Although the Intellivision is also able to work on 16-bit data, programs were really stored in 10-bit ROM back then.}

A routine taking the input in R0 and returning the result in R1.

                            ROMW  10        ; use 10-bit ROM
                            ORG   $4800     ; map our code at $4800
                      
4800  02B8 01CD             MVII  #461, R0  ; example call with n = 461
4802  0004 0148 0006        CALL  func
4805  0017                  DECR  R7        ; loop forever
                      
                            ;; Our routine
                            ;; We start with R1 = 1.
                            ;; We negate R1 for each bit set in R0 AND (R0 >> 1).
                      func  PROC
                      
4806  02B9 0001             MVII  #1,   R1  ; R1 = output, initialized to 1
4808  0082                  MOVR  R0,   R2  ; copy R0 to R2
4809  0062                  SLR   R2        ; right-shift R2
480A  0182                  ANDR  R0,   R2  ; bitwise AND of R0 and R2
                      
480B  007A            @loop SARC  R2        ; right-shift R2 into carry
480C  0209 0001             BNC   @next     ; skip NEGR if the carry is not set
480E  0021                  NEGR  R1        ; negate R1
480F  022C 0005       @next BNEQ  @loop     ; loop if the last result is non-zero
                                            ; (always true if NEGR was processed,
                                            ; otherwise based on SARC R2)
                      
4811  00AF                  MOVR  R5,   R7  ; return
                      
                            ENDP

Output

Returned from JSR at $4802.
 01CD FFFF 0000 0000 01FE 4805 02F1 4805 ------i-  DECR R7
      \__/
     R1 = -1

Answer 12

Vyxal 3, 5 bytes

bᵃ×∑Ṃ

Try it Online! (link is to literate version)

Vyxal 3 doesn't currently have the -1 ** and push -1 built-ins v2 has. It does now. Can't believe I forgot them.

Explained (old)

bᵃ+2C1_$*­⁡​‎‎⁡⁠⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏⁠‎⁡⁠⁣‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏‏​⁡⁠⁡‌­
b          # ‎⁡Convert to list of digits in binary representation
 ᵃ+        # ‎⁢Reduce each overlapping pair by addition
   2C      # ‎⁣Count the number of 2s in that list
     1_$*  # ‎⁤-1 ** that
💎

Created with the help of Luminespire.

Answer 13

Vyxal, 45 bits^v2, 5.625 bytes

bzvΠ∑Ǎ

Try it Online!

Bitstring:

011100100001001101011110010110110000010001101

Answer 14

Python 3, 35 bytes

f=lambda n:n<3or(3>n&3or-1)*f(n//2)

Try it online!

Answer 15

Python 3, 36 bytes

f=lambda x:x<1or(1-x%4//3*2)*f(x>>1)

Try it online!

Answer 16

Retina, 37 bytes

.+
*
+`(_+)\1
$1;
vC`_;_
.+
*
__

$
1

Try it online!

Given \$ n \$ yields \$ r_{n} \$. The header in the link allows it to be run on many values at once. Uses _ as the negative sign.

Explanation

.+
*

Convert decimal to unary.

+`(_+)\1
$1;

Convert unary to binary (sort of).

vC`_;_
.+
*

Count overlapping "1"s in the binary representation, and then convert that to unary.

__

$
1

Remove pairs of digits in unary to delete even numbers and leave one digit for odd numbers. Then add a 1 to the end of the output. Because the digits are underscores, we get the desired expression.

Answer 17

Charcoal, 11 bytes

﹪Ｌ⌕Ａ⍘Ｎ²11²1

Try it online! Link is to verbose version of code. Outputs the nth term. Explanation:

     Ｎ      Input number
    ⍘ ²     Convert to base `2` as a string
  ⌕Ａ   11   Find all overlapping matches of `11`
 Ｌ          Count them
﹪        ²  Reduce modulo `2`
            Implicitly print that many `-`s
          1 Append a literal `1`

The naïve approach of raising -1 to the power of the count of overlapping matches actually ends up longer as an additional byte is required to cast the result to a string.

Answer 18

Retina 0.8.2, 39 bytes

.+
$*_
+`(_+)\1
$1;
(_);\b|.
$1
__

$
1

Try it online! Takes n as input but link is to test suite that generates all the results from 0..n inclusive. Explanation: Based on @FryAmTheEggman's Retina 1 answer, with the following changes:

• Retina 0.8.2 uses M& where Retina 1 uses vC.
• Retina 0.8.2's character repetition operator $* is already a byte longer than Retina 1's string repetition operator *, plus it defaults to the character 1 which is unhelpful, so an explicit character is needed. Fortunately the latter only makes a difference on the last use.
• I then golfed a byte off by replacing the count and subsequent unary conversion stage with a replace stage. (This would also work in the Retina 1 answer, but there it wouldn't affect the byte count.)

Answer 19

JavaScript (ES6), 26 bytes

Returns the \$n\$-th term of the sequence. Relies on arithmetic underflow to stop the recursion.

f=n=>n?(-n%4/3|1)*f(n/2):1

Try it online!

Commented

f = n =>   // f is a recursive function taking the input n
n ?        // if n is not zero:
  (        //
    -n % 4 //   the sign of n % m is the sign of n in JS,
           //   so this gives a value in ]-4, 0]
    / 3    //   we turn this into a value in ]-4/3, 0]
           //   this is ≤ -1 if the 2 least significant bits
           //   of the integer part of n are set
    | 1    //   a bitwise OR with 1 gives either:
           //     -1 for ]-4/3, -1]
           //      1 for ]-1, 0]
  )        //
  *        //   we multiply by the result of ...
  f(n / 2) //   ... a recursive call with n / 2
           //   once we have n < 1, the final result is not
           //   changed anymore; and once n is small enough,
           //   n / 2 will eventually be evaluated to 0
:          // else:
  1        //   stop the recursion

Answer 20

Perl 5 -p, 35 bytes

$_=(-1)**unpack"%b*",pack N,$_&2*$_

Try it online!

Answer 21

TI-BASIC, 25 bytes

prod(1-2seq(3=4fPart(int(Ans/2^I)/4),I,0,Ans

Takes input in Ans.

Answer 22

Google Sheets / Microsoft Excel, 47 46 bytes

=-1^len(substitute(base(bitor(A1,2*A1),2),0,))

Put \$n\$ in cell A1 and the formula in B1.

Using the method in Command Master's Python answer, with -1 byte thanks to m90.

In spreadsheets, operator precedence is sometimes different from what one would expect. The unary minus will get evaluated before exponentiation, so -1^2 === (-1)^2 === 1 rather than -1.

Answer 23

AWK, 37 bytes

{for(;$1>1;$1/=2)a+=$1%4>=3}$0=(-1)^a

Attempt This Online! or try more test cases.

Takes n from stdin and prints the nth term to stdout. Multiple-case version has a replaced with $2 so that it works across test cases.

Awk numbers are floating-point numbers. The for loop observes the 0th and 1st bits while the given number is shifted to the right. Both bits are 1 if and only if the current number modulo 4 (floating-point) is at least 3.

Answer 24

APL (Dyalog Classic), 17 15 bytes

×/¯1*2∧/⊢⊤⍨2⍴⍨!

Try it online!

Written as a tacit function. While this would technically work for all n, it will run out of memory very quickly, as it computes n as a binary number with n! digits. This is simply to avoid the edge case of n=0, so the following code works equivalently and much more efficiently for positive n (only using n digits).

×/¯1*2∧/⊢⊤⍨2⍴⍨⊢

Would be interested if there were a workaround to this issue that doesn't increase byte count.

EDIT: I swapped the Power and the Reduce and changed from a Plus reduction to a Times reduction to remove parentheses.

Answer 25

APL+WIN, 26 bytes

Prompts for integer:

¯1*+/2=2+/((⌈2⍟2⌈n)⍴2)⊤n←⎕

Try it online! Thanks to Dyalog Classic

Answer 26

Vyxal 3L, 28 bytes

2to-base count: */+-1swap **

Try it Online!

I know the byte counter says "10 literate bytes", but that's going to be changed in the future to properly accommodate literate mode golfing.

Anyhow, I thought this might be a fun opportunity to try out literate mode golfing and see how it plays out. And it's definitely interesting - I started with 32 bytes using the exact SBCS method, but found that adding some extra commands made it shorter. Aliases!

The 3L stands for Vyxal 3 Literate Mode. It's different to Vyxal 3 l flag, as 3L (in theory) has a dedicated executable. I say in theory because I may or may not have forgotten to actually make it a release binary - it can still be run from mill though.

Explained

2to-base count: */+-1swap **­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏⁠‎⁡⁠⁤⁢‏⁠‎⁡⁠⁤⁣‏⁠‎⁡⁠⁤⁤‏⁠‎⁡⁠⁢⁡⁡‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁡⁢‏⁠‎⁡⁠⁢⁡⁣‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁡⁤‏⁠‎⁡⁠⁢⁢⁡‏⁠‎⁡⁠⁢⁢⁢‏⁠‎⁡⁠⁢⁢⁣‏⁠‎⁡⁠⁢⁢⁤‏⁠‎⁡⁠⁢⁣⁡‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁣⁣‏⁠‎⁡⁠⁢⁣⁤‏‏​⁡⁠⁡‌­
2to-base                      # ‎⁡Convert input to base 2. Shorter than `to-binary`
         count: *             # ‎⁢Reduce overlaps by multiplication. The space is needed so that the "*" is recognised as an individual word.
                 /+           # ‎⁣Reduce that by addition. `/+` beats `sum` by a byte
                   -1swap     # ‎⁤Push -1 under that value
                          **  # ‎⁢⁡And exponentate
💎

Created with the help of Luminespire.

Answer 27

GolfScript, 18 bytes

~..+&2base{},,-1\?

Try it online! or try numbers 0 to 30.

-1 raised to the power (\?) of the number of truthy items ({},,) of the binary representation (2base) of the bitwise AND (&) of the input (~) and it doubled (..+).

Here’s a solution that doesn’t use bitwise operations:

GolfScript, 27 bytes

~2base.);\(;+2/{{*}*},,/-1\?

Try it online! or try numbers 0 to 30.

Full program.

Explanation coming soon to a theater near you has arrived at a codeblock near you!

~     # Eval the input (reading it as a number)
2base # Concert it to a list of binary digits
.     # Duplicate
);    # Remove the last of the copy
\(;   # Remove the first of the original
+     # Concatenate them
2/    # Split into groups of size two
{    },, # Number of pairs where following is true:
 {*}*    #   Reduce by multiplication
-1\?  # Raise -1 to this power

No builtin for overlapping pairs, so this instead makes two copies - one with the first digit removed and one with the last removed - concatenates them, and splits into nonoverlapping pairs.

Answer 28

Desmos, 48 44 43 bytes

-4 bytes building off of a suggestion made by @Yousername!

-1 more byte also from @Yousername building off of my 44 byte golf

f(k)=∏_{n=0}^ksgn(5-2mod(floor(k/2^n),4))

Try It On Desmos!

Try It On Desmos! - Prettified

Answer 29

C (gcc), ⁴² 28 bytes

f(n){n=n?f(n/2)^n%4/3*-2:1;}

Try it online!

Port of xnor's Python 2 answer

Saved a whopping 14 bytes thanks to att!!!

Answer 30

AWK, 67 65 59 58 56 bytes

{d=and($1,$1*2);for(b=z;d/=2;)b=d%2b}$1=(-1)^gsub(1,1,b)

Try it online!

• -2 bytes, didn't use the regex indicator in gsub(), just passed 1 as first arg
• -6 bytes, removed int() function, then used d/=2 instead of d=d/2
• -1 byte, moved the divisor of d in the conditional statement
• -2 bytes, moved the $1 assignment

This works for multiple record input. If your file would only have a single record you could save 3 4 bytes by replacing the initialization of b in the for() loop with the initialization of d.

---

AWK, 53 52 bytes

{for(d=and($1,$1*2);d/=2;)b=d%2b}$1=(-1)^gsub(1,1,b)

Try it online!

• -1 byte, moved the $1 assignment

I'm not completely familiar with each and every rules allowed for golfing. So in this case I moved the initialization of b in the header. This allow having multiple record read in one go. Secondary I moved the 1 at the end of the line to the footer. We already have our value stored in the current record, adding 1 at the end of the line trigger the default awk block {print $0} so it's only useful for printing.

Any insight of the rule on both of these subjects are more than welcome !