Mini-Challenge: Rudin-Shapiro Sequence

[John Keith]

(12-17-2022 02:30 AM)ttw Wrote:  The Thue-Morse sequence isn't that hard (it's very fast on the Hp50g as one can compute en masse with X = {0 1} and follow up with X = X + (1 - X). The Nth element is the parity of the number of bits set in the binary representation of N. The anti-Thue sequence (I don't know an accepted name) is the sequence that counts the number of 0's in the number N.

The sequence that counts the number of 0's in binary n is A023416. The parity of the number of 0's is A059448. I don't know if there are special names for either sequence. Both can be computed by similar small, fast programs.

This was actually the reason behind my posting of this challenge. I have observed that nearly all sequences describing properties of binary numbers have a fractal pattern, that is they are self-similar at different scales. This self-similarity leads to fast and simple algorithms as you noted for the Thue-Morse sequence.