Re: Growing ordered set

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

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.