[seqfan] Re: Binary Complement Sequences

[Christian Sievers]

On Fri, Dec 16, 2022 at 04:38:07PM -0500, Allan Wechsler wrote:

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

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.

If we have a cycle of length 2^n in the residues modulo 2^n, then
there are only two possibilities for mod 2^(n+1):
We can start the cycle at 0. Then we know that after 2^n steps the
value is 0 (mod 2^n), so it is 0 or 2^n (mod 2^(n+1)). In the first
case, the cycle repeats after 2^n steps, in the second case it has
length 2^(n+1).

So we have to show that for all n,
   f^{2^n}(0) is divisible by 2^n but not by 2^(n+1).
(Here f^k denotes the composition f \circ f \circ ... \circ f (k times).)

In general, if       g(x)  = a*x+b,
            then   g(g(x)) = a^2*x + ab+b   (*).

Now define sequences a_n and b_n by
   f^{2^n}(x) = a_n * x + b_n.

We have a_0=-3 and b_0=-1.
Using (*) and induction, we see that each a_n is a power of -3,
so 1 (mod 4), so it can be written as 4k+1 for some integer k.

Then by (*),
  b_{n+1} = a_n * b_n + b_n = (4k+1) * b_n + b_n = (2k+1)*2*b_n.

So b_n gains exactly one factor of 2 each time we increase n,
and since b_0 is odd and f^{2^n}(0)=b_n, this shows the divisibility
property we wanted.


All the best
Christian