extra/project-euler/034/034.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math.ranges project-euler.common sequences ;
   4 IN: project-euler.034
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=34
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! 145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.
  12
  13 ! Find the sum of all numbers which are equal to the sum of the factorial of
  14 ! their digits.
  15
  16 ! Note: as 1! = 1 and 2! = 2 are not sums they are not included.
  17
  18
  19 ! SOLUTION
  20 ! --------
  21
  22 ! We can reduce the upper bound a little by calculating 7 * 9! = 2540160, and
  23 ! then reducing one of the 9! to 2! (since the 7th digit cannot exceed 2), so we
  24 ! get 2! + 6 * 9! = 2177282 as an upper bound.
  25
  26 ! We can then take that one more step, and notice that the largest factorial
  27 ! sum a 7 digit number starting with 21 or 20 is 2! + 1! + 5 * 9! or 1814403.
  28 ! So there can't be any 7 digit solutions starting with 21 or 20, and therefore
  29 ! our numbers must be less that 2000000.
  30
  31 <PRIVATE
  32
  33 : digit-factorial ( n -- n! )
  34     { 1 1 2 6 24 120 720 5040 40320 362880 } nth ;
  35
  36 : factorion? ( n -- ? )
  37     dup number>digits [ digit-factorial ] sigma = ;
  38
  39 PRIVATE>
  40
  41 : euler034 ( -- answer )
  42     3 2000000 [a,b] [ factorion? ] filter sum ;
  43
  44 ! [ euler034 ] 10 ave-time
  45 ! 5506 ms ave run time - 144.0 SD (10 trials)
  46
  47 MAIN: euler034