[seqfan] Re: Binary Complement Sequences

[Allan Wechsler]

While we wait breathlessly to learn the fate of 425720, I have started
wondering if there is some way of accelerating the computation. I don't
have any big insights to report, but I would like to mention that one
doesn't need to know *all *the bits of one term of the trajectory in order
to *begin* calculating the next.

For example, if we know that the most significant bits of one term are
11101, then we can be sure that the next term starts 10, and that the first
bit has index one greater than the first bit of the previous term.

So if we had a term with 400,000 bits, and accidentally lost the least
significant bit, we would still be able to predict the binary order of
magnitude of the next couple of hundred thousand terms before our
ignorance swallowed up everything we knew about the numbers. This doesn't
actually put a real dent in the problem, but it's fun to think about, and
maybe there might be more profound accelerations to be had if we thought
harder about it.

On Wed, Dec 21, 2022 at 2:02 AM Christian Sievers <seqfan at duvers.de> wrote:

> 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
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>