[seqfan] Re: Binary Complement Sequences

[Tom Duff]

I ran all starting numbers from 0 to 42569 with cycle-checking turned on.
Every one descended to zero. For the 425720 run, I turned cycle checking
off, because the program runs much quicker without it (Floyd's algorithm --
Brent hadn't devised his until long after I was out of school and no longer
paying attention to that sort of thing, so I hadn't heard of it) and I
thought the chance of hitting a non-zero cycle was pretty small. In any
case, I also record the length of the numbers every million iterations and
I think the resulting graph will likely make it obvious whether there's a
chance it's fallen into a cycle.

On Mon, Dec 19, 2022 at 9:50 PM Tim Peters <tim.peters at gmail.com> wrote:

> [Tom Duff]
> > ...
> > The number of steps for 425720 is at least 16,943,000,000 -- still
> running
> > after 32 hours of CPU time on my M1 Mac Mini.
>
> I gave up after 14 billion, because the size of integers in play
> stopped obviously climbing after about 11 billion steps (I have trace
> output showing this after every million steps).
>
> So I have to consider the possibility that it fell into a cycle - in
> which case my program would never end.
>
> So I added simple code for cycle detection (Brent's method - much as
> in his variation of Pollard's "rho" factorization method), and started
> over.
>
> Nothing yet to report, and possibly never.
>
> Does your code detect a cycle if one occurs? Or does anyone have an
> argument for why a cycle can't occur? (As Allen noted, every reachable
> value has an infinite number of preimages, which intuitively seems to
> me to boost the likelihood of a cycle.)
>
> 425720 is ... puzzling :-)
>