extra/project-euler/074/074.factor

   1 ! Copyright (c) 2009 Guillaume Nargeot.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: hash-sets kernel math.ranges project-euler.common
   4 sequences sets ;
   5 IN: project-euler.074
   6
   7 ! http://projecteuler.net/index.php?section=problems&id=074
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  12 ! The number 145 is well known for the property that the sum of the factorial
  13 ! of its digits is equal to 145:
  14
  15 ! 1! + 4! + 5! = 1 + 24 + 120 = 145
  16
  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
  19 ! loops that exist:
  20
  21 ! 169 → 363601 → 1454 → 169
  22 ! 871 → 45361 → 871
  23 ! 872 → 45362 → 872
  24
  25 ! It is not difficult to prove that EVERY starting number will eventually get
  26 ! stuck in a loop. For example,
  27
  28 ! 69 → 363600 → 1454 → 169 → 363601 (→ 1454)
  29 ! 78 → 45360 → 871 → 45361 (→ 871)
  30 ! 540 → 145 (→ 145)
  31
  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
  34 ! terms.
  35
  36 ! How many chains, with a starting number below one million, contain exactly
  37 ! sixty non-repeating terms?
  38
  39
  40 ! SOLUTION
  41 ! --------
  42
  43 ! Brute force
  44
  45 <PRIVATE
  46
  47 : digit-factorial ( n -- n! )
  48     { 1 1 2 6 24 120 720 5040 40320 362880 } nth ;
  49
  50 : digits-factorial-sum ( n -- n )
  51     number>digits [ digit-factorial ] map-sum ;
  52
  53 : chain-length ( n -- n )
  54     61 <hash-set> [ 2dup ?adjoin ] [
  55         [ digits-factorial-sum ] dip
  56     ] while nip cardinality ;
  57
  58 PRIVATE>
  59
  60 : euler074 ( -- answer )
  61     1,000,000 [1..b] [ chain-length 60 = ] count ;
  62
  63 ! [ euler074 ] 10 ave-time
  64 ! 25134 ms ave run time - 31.96 SD (10 trials)
  65
  66 SOLUTION: euler074