Mini-Challenge: Rudin-Shapiro Sequence

[C.Ret]

For HP-28S,one algorithm, three submissions.

Version with extra \(u_k\) computations:

Uk:
« 0 SWAP BIN R→B →STR OVER
  WHILE 1 + 999 SUB DUP "11" POS DUP
  REPEAT ROT 1 + ROT ROT END
  DROP2 »

Usage:375775 Uk returns 10.

Rk:
« -1 SWAP Uk ^ »

LST1000:
« 0 999 FOR k k Rk NEXT
  1E3 →LIST
  960 .1 BEEP »

The list of the first 1000 terms of the Rudin-Shapiro sequence obtained in about 2'46".


Version without extra \(u_k\):
Rk:
« 1 SWAP BIN R→B →STR 2
  WHILE 1 + 999 SUB DUP "11" POS DUP
  REPEAT ROT NEG ROT ROT END
  DROP2 »

Usage:375775 Rk returns 1.

LST1000:
« 0 999 FOR k k Rk NEXT
  1E3 →LIST
  960 .1 BEEP »

The list of the first 1000 terms of the Rudin-Shapiro sequence obtained in about 2'26".


Stand alone version:
LST1000:
« 0 999 FOR k
    1 k BIN R→B →STR 2
    WHILE 1 + 999 SUB DUP "11" POS DUP
    REPEAT ROT NEG ROT ROT END
    DROP2 NEXT
  1E3 →LIST
  960 .1 BEEP »

The list of the first 1000 terms of the Rudin-Shapiro sequence obtained in about 2'18".


Next challenge, trying to improuve speed efficiency of the list build-up by using the recursive algorithm.

P.S.: All system settings expected to be default values, especially binary words size at 64 bits.