Bill Allombert on Thu, 20 Nov 2014 20:27:27 +0100

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Growing ordered set

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}.