Project Euler Problem 74 Solution
The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:
Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169; it turns out that there are only three such loops that exist:
It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,
Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.
How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?
import qualified Data.Set as Set factorial :: Integer -> Integer factorial n = product [1..n] digits :: Integer -> [Integer] digits 0 =  digits n = r : digits q where (q, r) = quotRem n 10 next :: Integer -> Integer next = sum . map factorial . digits chain :: Integer -> Integer chain = inner Set.empty where inner set x | Set.member x set = 0 | otherwise = 1 + inner (Set.insert x set) (next x) main :: IO () main = print $ length $ filter ((== 60) . chain) [1..1000000]
$ ghc -O2 -o factorial-chains factorial-chains.hs $ time ./factorial-chains real 0m27.886s user 0m27.652s sys 0m0.052s
Questions? Comments? Send me an email: email@example.com