[seqfan] Re: Binary Complement Sequences

[hv at crypt.org]

I can't check right now what Floyd's and Brent's algorithms are, but
one trick I've used in the past is to simultaneously calculate the same
sequence at half the speed: if it cycles, at some point the n'th and
2n'th iterations will give the same value.

Hugo

Tom Duff <eigenvectors at gmail.com> wrote:
: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 :-)
:>
:
:--
:Seqfan Mailing list - http://list.seqfan.eu/