Charles Greathouse on Thu, 20 Nov 2014 21:02:01 +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}.
Cheers,
Bill.