[seqfan] Re: Binary Complement Sequences

[Tim Peters]

[Arthur O'Dwyer <arthur.j.odwyer at gmail.com>]
> ...
> - When we say "N reaches zero," we mean "N reaches anything less than N,"
> right?

In this discussion, no, we mean "N reaches zero".

> I mean, if you're searching the number line in increasing order, you
> know that as soon as N reaches a number you've seen before, you're done
> (because all the numbers you've ever seen, converge; and you've already
> seen all numbers less than N).

Yes, but turns out it appears counterproductive in this problem.  It's
one way in which "intuition" informed by playing with the Collatz
sequence appears to backfire in this problem.

"Stopping time" (# of steps before the iterate falls below the
starting seed) in Collatz pays because "long" chains that reach "very
large" integers are empirically quite rare. Indeed, start with any
even integer, and the stopping time in Collatz is 1.

But long chains are more common here, and reaching very much larger
iterates very much more common. The stopping time for about a third of
seeds is 1, but that can be checked once at the start (and that does
pay overall). Putting the "less than the starting seed?" test _in_ the
loop costs more than it saves overall, because it's not all that rare
for that test to fail millions of times in a row.

"Stopping time" for this "binary complement" map could be another
sequence added to OEIS.

> - This relates to Allan's suggestion that "we can catch a lot of
> Methuselahs early, by keeping a table of, say, the billionth iterates of
> long-lasting seeds."  That's a technique known as rainbow tables
> <https://en.wikipedia.org/wiki/Rainbow_table>, and sounds like a good idea
> to me.

Last night I posted pseudo code for a method I actually use, which
doesn't depend on the order in which seeds are tried, and can exploit
hitting any iterate <= N, where N is the largest initial seed we're
interested in. This is regardless of whether such an iterate is
smaller or larger than the initial seed. And it computes the number of
steps to reach 0. To do this, it needs to maintain a table, mapping
each possible starting seed (1 .. N) to its step count (or 0 if it's
not yet known).

It's effective in practice for N=1,000,000, but I can't prove that
this extends to higher N. The "bad cases" I can conceive of just don't
happen for N so small.