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