extra/project-euler/034/034.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See https://factorcode.org/license.txt for BSD license.
   3 USING: kernel ranges project-euler.common sequences ;
   4 IN: project-euler.034
   5
   6 ! https://projecteuler.net/problem=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
  14 ! factorial of 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! =
  23 ! 2540160, and then reducing one of the 9! to 2! (since the 7th
  24 ! digit cannot exceed 2), so we get 2! + 6 * 9! = 2177282 as an
  25 ! upper bound.
  26
  27 ! We can then take that one more step, and notice that the
  28 ! largest factorial sum a 7 digit number starting with 21 or 20
  29 ! is 2! + 1! + 5 * 9! or 1814403. So there can't be any 7 digit
  30 ! solutions starting with 21 or 20, and therefore our numbers
  31 ! must be less that 2000000.
  32
  33 <PRIVATE
  34
  35 : digit-factorial ( n -- n! )
  36     { 1 1 2 6 24 120 720 5040 40320 362880 } nth ;
  37
  38 : factorion? ( n -- ? )
  39     dup number>digits [ digit-factorial ] map-sum = ;
  40
  41 PRIVATE>
  42
  43 : euler034 ( -- answer )
  44     3 2000000 [a..b] [ factorion? ] filter sum ;
  45
  46 ! [ euler034 ] 10 ave-time
  47 ! 5506 ms ave run time - 144.0 SD (10 trials)
  48
  49 SOLUTION: euler034