Talk:Euler problems/11 to 20
(Improvement to solution to Collatz problem in ProjectEuler)
Latest revision as of 14:14, 31 January 2010
It seems to me that the solution posted to the Collatz problem is not the most efficient. In order to find integer that gives the longest chain it is not necessary to _find_ that longest chain. So one needs to use a Boolean function that merely checks whether the chain for n is longer than that for m where m is the winner so far.
This does not need to repeatedly calculate the chain for m if we the tuple (m,c,m') where c is the length of the chain from m to m' which we have calculated so far.
As far as I know the longest chain is significantly longer than all the other chains considered so this should save us a lot of time by avoiding computing that chain.