extra/project-euler/023/023.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: hashtables kernel math math.ranges project-euler.common sequences
   4     sorting sets ;
   5 IN: project-euler.023
   6
   7 ! http://projecteuler.net/index.php?section=problems&id=23
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  12 ! A perfect number is a number for which the sum of its proper divisors is
  13 ! exactly equal to the number. For example, the sum of the proper divisors of
  14 ! 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.
  15
  16 ! A number whose proper divisors are less than the number is called deficient
  17 ! and a number whose proper divisors exceed the number is called abundant.
  18
  19 ! As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest
  20 ! number that can be written as the sum of two abundant numbers is 24. By
  21 ! mathematical analysis, it can be shown that all integers greater than 28123
  22 ! can be written as the sum of two abundant numbers. However, this upper limit
  23 ! cannot be reduced any further by analysis even though it is known that the
  24 ! greatest number that cannot be expressed as the sum of two abundant numbers
  25 ! is less than this limit.
  26
  27 ! Find the sum of all the positive integers which cannot be written as the sum
  28 ! of two abundant numbers.
  29
  30
  31 ! SOLUTION
  32 ! --------
  33
  34 ! The upper limit can be dropped to 20161 which reduces our search space
  35 ! and every even number > 46 can be expressed as a sum of two abundants
  36
  37 <PRIVATE
  38
  39 : source-023 ( -- seq )
  40     46 [1,b] 47 20161 2 <range> append ;
  41
  42 : abundants-upto ( n -- seq )
  43     [1,b] [ abundant? ] filter ;
  44
  45 : possible-sums ( seq -- seq )
  46     dup { } -rot [
  47         dupd [ + ] curry map
  48         rot append prune swap rest
  49     ] each drop natural-sort ;
  50
  51 PRIVATE>
  52
  53 : euler023 ( -- answer )
  54     source-023
  55     20161 abundants-upto possible-sums diff sum ;
  56
  57 ! TODO: solution is still too slow, although it takes under 1 minute
  58
  59 ! [ euler023 ] time
  60 ! 52780 ms run / 3839 ms GC
  61
  62 MAIN: euler023