[seqfan] Re: Binary Complement Sequences

[Tim Peters]

[Allan Wechsler]
>> As long as the iterates remain large, the low-order bits quickly enter
>> cycles, in which they remain until the number shrinks to the corresponding
>> order of magnitude. The low-order bit alternates between 1 and 0; the two
>> low-order bits read [0, 3, 2, 1] and repeat, and the low three bits read
>> [0, 7, 2, 1, 4, 3, 6, 5]. I don't know if there is always a single cycle of
>> length 2^n, but this is an obvious early question.

[Christian Sievers]
> There is always one cycle of full length.
>
> Looking at the last n bits and assuming that the complement flips all
> bits because there is enough going on at higher bits amounts to
> considering the residues modulo 2^n of the values of the iterations of
> the function
>   f(x) = -3*x-1.
> ...
> [and a possible proof]

Offline, I mentioned to Allan that iterating the mapping has the form
of a linear congruential pseudorandom number generator, and so the
cycle length could perhaps be determined by appealing to the world of
theory developed for those.

"The problem" is that, in that theory, the multiplier (-3) and
additive constant (-1) are always assumed to be non-negative.

But, modulo 2^n, -3 acts the same as 2^n-3, and -1 as 2^n-1. And then
it  follows essentially immediately (for n >= 2) from the Hull–Dobell
theorem that there's a single full-length (2^n) cycle:

https://en.wikipedia.org/wiki/Linear_congruential_generator#c_%E2%89%A0_0