1 ! Copyright (c) 2009 Guillaume Nargeot.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: assocs hashtables kernel math math.ranges
4 project-euler.common sequences sets ;
7 ! http://projecteuler.net/index.php?section=problems&id=074
12 ! The number 145 is well known for the property that the sum of the factorial
13 ! of its digits is equal to 145:
15 ! 1! + 4! + 5! = 1 + 24 + 120 = 145
17 ! Perhaps less well known is 169, in that it produces the longest chain of
18 ! numbers that link back to 169; it turns out that there are only three such
21 ! 169 → 363601 → 1454 → 169
25 ! It is not difficult to prove that EVERY starting number will eventually get
26 ! stuck in a loop. For example,
28 ! 69 → 363600 → 1454 → 169 → 363601 (→ 1454)
29 ! 78 → 45360 → 871 → 45361 (→ 871)
32 ! Starting with 69 produces a chain of five non-repeating terms, but the
33 ! longest non-repeating chain with a starting number below one million is sixty
36 ! How many chains, with a starting number below one million, contain exactly
37 ! sixty non-repeating terms?
47 : digit-factorial ( n -- n! )
48 { 1 1 2 6 24 120 720 5040 40320 362880 } nth ;
50 : digits-factorial-sum ( n -- n )
51 number>digits [ digit-factorial ] map-sum ;
53 : chain-length ( n -- n )
56 [ [ conjoin ] [ [ digits-factorial-sum ] dip ] 2bi ]
57 while nip assoc-size ;
61 : euler074 ( -- answer )
62 1000000 [1,b] [ chain-length 60 = ] count ;
64 ! [ euler074 ] 10 ave-time
65 ! 25134 ms ave run time - 31.96 SD (10 trials)