[seqfan] Re: Binary Complement Sequences

[Tim Peters]

[Dec 17, 2022 at 6:17 AM Allan Wechsler <acwacw at gmail.com>]
> ... 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.

Python conceptually stores integers in 2's-complement, with an
infinite number of copies of "the sign bit". For example, -1 is
conceptually stored as an infinite string of 1 bits.

>>> -1 & 1 # "last" bit
1
>>> -1 & 3 # last 2 bits
3
>>> -1 & 7 # last 3 bits
7

and so on. Under this view, the bitwise complement of an integer is
the negation of the integer, less 1.

>>> n = 12345 # arbitrary
>>> ~n == -n - 1
True

But, again, the sign bit is infinitely replicated.

>>> ~0
-1

In the problem at hand, the sign bits are thrown away, leaving only
"the last n bits" of the complement (for the right value of n). So,
starting with `i`, one step yields

    the last n bits of -3*i-1

But "the last n bits" of an integer `j` are `j modulo 2**n`, and we
can put off doing a modulus operation until the end of a chain of
operations.

So, e.g.,

> the low three bits read [0, 7, 2, 1, 4, 3, 6, 5].

Apply the above 5 times to the starting value 0 to get:

>>> -3*(-3*(-3*(-3*(-3*0-1)-1)-1)-1)-1
-61
>>> _ % 8 # `%` is modulo
3

That is, 3 is the value 5 steps beyond 0 in your list.

Now for the real point:

    -3*i - 1 = -3*j - 1 (modulo 2**n)

if and only if i is congruent to j modulo 2**n, because 3 and 2**n are
coprime, and

    -3*i - 1 = j (modulo 2**n)

for any j can be solved by adding 1 to j and then multiplying both
sides by the inverse of -3 modulo 2**n. For example, what comes before
4 in your list above?

>>> (4 + 1) * pow(-3, -1, 8) % 8
1

The first implies that, modulo 2**n, the -3*i-1 map is injective, and
the second that it's also surjective. So it's a permutation:
regardless of n, the last n bits fall into a cycle of length 2**n.