# 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
Commented 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. Commented 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$? Commented Nov 23, 2023 at 8:45
• @Arnauld No. The Rudin-Shapiro sequence is by definition a sequence of 1s and −1s. Commented Nov 23, 2023 at 9:20

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

• Why 13?
– l4m2
Commented Nov 23, 2023 at 5:23
• @l4m2 I think any odd base will do in principle, 13 is just the first one that can also digest the b from 0b... in the binary literal. Commented Nov 23, 2023 at 6:20

# 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!

• You can do (n&n*2).bit_count() starting with Python 3.10
– xnor
Commented Nov 23, 2023 at 2:26

# 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


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

• If we want a version that only handles 8-bit inputs, then in your second version, we have the result in the parity flag after and ecx, eax. However it takes some work to materialize it as +/- 1. I can get down to 12 bytes with setpe al / shl eax, 1 / dec eax (in 32-bit mode so we have 1-byte dec). Commented Nov 25, 2023 at 4:25

# 05AB1E, 7 bytes

b11¢®sm


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

Here an equal-bytes alternative:

bü*OÈ·<


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)


# 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


# J, 12 bytes

_1^1#.2*/\#:


Try it online!

# 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.
• n->1|-n.bitCount(n&n*2)%2 seems to work?
– Neil
Commented Nov 23, 2023 at 14:13

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

# Japt, 7 bytes

Jp¢ä* x


Explanation:

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


# CP-1610 machine code, 12 DECLEs1 = 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 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


Returned from JSR at $4802. 01CD FFFF 0000 0000 01FE 4805 02F1 4805 ------i- DECR R7 \__/ R1 = -1  # 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. # Vyxal, 45 bitsv2, 5.625 bytes bzvΠ∑Ǎ  Try it Online! Bitstring: 011100100001001101011110010110110000010001101  • Fun fact: passing the bitstring of the Vyncode representation as input to the program gives a result of -1. Test it Commented Nov 24, 2023 at 1:57 # Python 3, 35 bytes f=lambda n:n<3or(3>n&3or-1)*f(n//2)  Try it online! # Python 3, 36 bytes f=lambda x:x<1or(1-x%4//3*2)*f(x>>1)  Try it online! • @JonathanAllan oops, thanks for the catch – att Commented Nov 23, 2023 at 3:33 # 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. # 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. • A really clever way to output the minus sign. Commented Nov 23, 2023 at 10:57 # 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.)

# 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


$_=(-1)**unpack"%b*",pack N,$_&2*$_  Try it online! # TI-BASIC, 25 bytes prod(1-2seq(3=4fPart(int(Ans/2^I)/4),I,0,Ans  Takes input in Ans. # 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. • Improvement: change bitand to bitor. 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 Commented Nov 29, 2023 at 17:11 • @m90 thanks for the -1 byte. Commented Nov 29, 2023 at 19:39 # AWK, 37 bytes {for(;$1>1;$1/=2)a+=$1%4>=3}$0=(-1)^a  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.

• Nice answer ! You out-golfed me by so much... Otherwise for multiple test case you don't need to use $2 you can set a=0 in the footer. Commented Feb 7 at 9:12 # 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. # APL+WIN, 26 bytes Prompts for integer: ¯1*+/2=2+/((⌈2⍟2⌈n)⍴2)⊤n←⎕  Try it online! Thanks to Dyalog Classic # 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. # GolfScript, 18 bytes ~..+&2base{},,-1\?  -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\?  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. # Desmos, 4844 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 • 46 bytes: f(k)=∏_{n=0}^k(1-0^{3-mod(floor(k/2^n),4)}2) Commented Nov 23, 2023 at 13:39 • @Yousername Thanks for the suggestion! Using product is clever; I found a way to shave two more bytes off building off of your idea! Commented Nov 24, 2023 at 2:33 • 1 byte less based off of your new one: f(k)=∏_{n=0}^ksgn(5-2mod(floor(k/2^n),4)) Commented Nov 24, 2023 at 3:52 • @Yousername Nice! That looks about as short as it can get. Commented Nov 24, 2023 at 10:59 # C (gcc), 42 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!!! • 28 bytes porting xnor's second Python solution – att Commented Nov 24, 2023 at 0:39 • @att Awesome - thanks! :D Commented Nov 24, 2023 at 12:58 # 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 !