Re: Growing ordered set

[Charles Greathouse <charles.greathouse@case.edu>]

OK, so rho doesn't need it, but my application does -- it's not iteratively applying a function, so Floyd doesn't apply, and I need a count of the elements not just the presence of a loop.

Charles Greathouse
Analyst/Programmer
Case Western Reserve University

On Thu, Nov 20, 2014 at 2:27 PM, Bill Allombert <Bill.Allombert@math.u-bordeaux.fr> wrote:

On Thu, Nov 20, 2014 at 01:41:36PM -0500, Charles Greathouse wrote:
> Fairly often I have a problem of the type 'generate a number by a given
> process, and repeat until a duplicate is found'. I also have the related
> problem 'generate a number by a given process, and repeat until some limit,
> recording the number of distinct elements at each step'.
>
> My particular inspiration in this case is computing A247140 in the OEIS,
> but this sort of problem is not uncommon. Actually, come to think of it,
> PARI has rho (pollardbrent), which solves a similar problem; I wonder how
> it handles it?

It uses Floyd cycle finding algorithm (which uses O(1) spaces):
Let f be some functions
Set x_{n+1} = f(x_n) and y_{n+1} = f(f(y_n)).

Iterate until x_n = y_n.
So you find the collision x_n = x_{2*n}.

Cheers,
Bill.