## January 2004

<<December
**January**
February>>

Solution:

This technique is known as Pollard's rho method; it was developed by John Pollard as a tool for integer factorization.

Let f(x) be the location of the array at address x.

a := f(f(n))

b := f(n)

do while not (a=b)

a:=f(f(a))

b:=f(b)

end

/* Now a=b can be reached at either 2k or k steps from n, */

/* where k is some integer between 1 and n. */

a:=n

do while not (a=b)

a:=f(a)

b:=f(b)

end

print a

The pattern that you get, starting from n and repeatedly applying f (doing the table lookup), is a string of some length L>0 leading to a cycle of some length M, with L+M<n. (L is nonzero because n is outside the range of f.)

It is shaped like the Greek letter rho, hence its name. Our stopping count k is the least multiple of M greater than or equal to L, so that L \leq k < L+M < n.

*If you have any problems you think we might enjoy, please send them in. All replies should be sent to:* ponder@il.ibm.com