[seqfan] Re: Binary Complement Sequences

[Tim Peters]

[Allan Wechsler <acwacw at gmail.com>]
> These convergences are reassuring. They make me think that we can catch a
> lot of Methuselahs early, by keeping a table of, say, the billionth
> iterates of long-lasting seeds, and when we start an unknown seed, keep
> scanning for those iterates. This idea is only half-baked, I concede.

Here's one that's mostly baked, since I've been using it ;-)

Say the largest value we're going to use as a seed is N. In context,
we're interested in all seeds <= N.

Initialize a 0-based vector i2s to all zeroes, of length N+1. i2s[i]
will become the number of steps needed for i to reach 0.

In the routine that's passed an initial seed i:

    s = 0
    pending = []
    while i:
        if i <= N:
            if saved := i2s[i]:
                s += saved
                break
            pending.append((i, s))
        i = step(i) # computes the complement of 3*i
        s += 1
    for i, s2 in pending:
        i2s[i] = s - s2
    return s

The caller sets i2s[original_value_of_i_passed] = the return value of
that function. then moves on to another seed (in any order it likes).

On all iterations where 0 < i <= N, we can do something useful to
accelerate the overall process. If we've already computed the value
for,i., i2s[i] is non-zero, and we break out of the loop at once.

Else if we haven't yet computed the result for i, we remember i, and
the current step count, in a list (`pending`). At the end, we fill in
the correct i2s results for those iterates.

Suppose, say, at the very start i and j are both seeds in range, and
step^5(i) = j. Without loss of generality, assume i < j. If we do `i`
first, then 5 steps in `(j, 5)` will be appended to `pending`, and the
loop at the end will set i2s[j] to 5 less than the final step count
for `i`.

If we do `j` first instead, it won't know anything about i`, but when
we _later_ start with seed `i`, 5 steps in it will see that i2s[j] is
already set, and get out early, returning 5 more than j's step count.

For N = a million this is a minor memory burden. The i2s values can
reach into the billions, but only rarely. And restricting entries to
values <= N doesn't appear to have any downside in practice so far: in
every case I've seen - and in all cases where the number of steps
exceeds a billion - overlapping sequences have an iterate <= N in
common, and less than a thousand steps into the sequences.

So, e.g., since step(425750) = 819991, we can compute either first,
and it will take a week, but then computing the other will complete
"immediately".

But I'm probably addressing yesterday's problems here - looks like the
burning question ("does it reach 0?") has been answered for all seeds
through a million, and nobody (certainly not this guy) seems to have
much appetite for more brute force here.