extra/project-euler/030/030.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math math.functions math.ranges project-euler.common sequences ;
   4 IN: project-euler.030
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=30
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! Surprisingly there are only three numbers that can be written as the sum of
  12 ! fourth powers of their digits:
  13
  14 !     1634 = 1^4 + 6^4 + 3^4 + 4^4
  15 !     8208 = 8^4 + 2^4 + 0^4 + 8^4
  16 !     9474 = 9^4 + 4^4 + 7^4 + 4^4
  17
  18 !     As 1 = 1^4 is not a sum it is not included.
  19
  20 ! The sum of these numbers is 1634 + 8208 + 9474 = 19316.
  21
  22 ! Find the sum of all the numbers that can be written as the sum of fifth
  23 ! powers of their digits.
  24
  25
  26 ! SOLUTION
  27 ! --------
  28
  29 ! if n is the number of digits
  30 ! n * 9^5 = 10^n  when n ≈ 5.513
  31 ! 10^5.513 ≈ 325537
  32
  33 <PRIVATE
  34
  35 : sum-fifth-powers ( n -- sum )
  36     number>digits [ 5 ^ ] sigma ;
  37
  38 PRIVATE>
  39
  40 : euler030 ( -- answer )
  41     325537 [0,b) [ dup sum-fifth-powers = ] filter sum 1 - ;
  42
  43 ! [ euler030 ] 100 ave-time
  44 ! 1700 ms ave run time - 64.84 SD (100 trials)
  45
  46 SOLUTION: euler030