[seqfan] Re: Binary Complement Sequences

[Tim Peters]

Alas, I haven't thought of a significant way to accelerate anything
here - just low-level bit-fiddling tricks. People might find the
following helpful, which characterizes which values decrease or
increase across iterations, and incidentally notes that "the first bit
has index one greater" is always the case when an iteration increases:

Let x = 2^n + i, where 2^n is the value of x's leading bit, and i is
the value of x - 2^n (the rest of x's bits).

If i < 2^n / 3, then the next term is 2^n - 3*i - 1. These are the
cases where the next term is smaller.

Else the next term is 2^(n+1) + 3*j - 1 where j = 2^n - i. These are
the cases where the next term is larger (and it's always one bit wider
than x - its leading bit is 2^(n+1), because 3*(2^n-i) = 3*2^n - 3*i
< (because i > 2^n/3 in this case) 3*2^n - 2^n = 2^(n+1)).

For example, the n=2 binade:

4 = 4 + 0 -> 4 - 3*0 - 1 = 3
5 = 4 + 1 -> 4 - 3*1 - 1 = 0 #  and i=1 is the largest integer < 4/3
6 = 4 + 2 -> 8 + 3*(4-2) - 1 = 13
7 = 4 + 3 -> 8 + 3*(4-3) - 1 = 10


On Mon, Dec 26, 2022 at 2:23 AM Allan Wechsler <acwacw at gmail.com> wrote:
>
> 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.