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}. Cheers, Bill.