Mini-Challenge: Rudin-Shapiro Sequence

[John Keith]

As promised, here are my solutions to this challenge.

First, a 97 byte program for any RPL calculator. This is a simple implementation of the recurrence from the Wikipedia article. Given a number n on the stack, returns 2n+1 terms. An input of 500 returns 1001 terms in 3.25 seconds on my 50g.

Code:


\<< \-> n
  \<< 1 1 1 n
    FOR k k PICK DUP k 2 MOD
     \<< NEG
     \>> IFT
    NEXT n 2 * 2 + \->LIST
  \>>
\>>

Next, a larger but faster version which avoids the 2 MOD test but requires extra code to avoid problems with odd number inputs. 121 bytes. An input of 500 returns 1000 terms in 1.94 seconds on my 50g.

Code:


\<< DUP DUP 2 MOD + \-> n m
  \<< 1 1 1 m
    FOR k k PICK DUP NEG k 1. + PICK DUP 2
    STEP m 2 * 2 + \->LIST 1 n 2 * SUB
  \>>
\>>

Next, a completely different sort of program which requires the 48G or newer because it uses the listability of functions (called "automatic list processing" in the manuals). Given a number n on the stack, returns 2^n terms. For example an input of 10 will return 1024 terms in 1.22 seconds on my 50g. 55 bytes.

Code:


\<< { 1 } DUP ROT 2 SWAP   @ Do n-1 iterations
  START DUP2 + ROT ROT     @ Concatenate and move to top
    0 SWAP - +             @ Negate second part and concatenate
  NEXT +                   @ Concatenate last two lists
\>>

Finally, a similar program for u(n) aka A014081. Also returns 2^n terms, 55.5 bytes. An input of 10 returns 1024 terms in 1.19 seconds.

Code:


\<< { 0 } DUP ROT 2 SWAP
  START DUP2 + ROT ROT 1 ADD +
  NEXT +
\>>