1 ! Copyright (c) 2008 Aaron Schaefer.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: kernel math math.ranges project-euler.common sequences sets sorting assocs fry ;
6 ! http://projecteuler.net/index.php?section=problems&id=23
11 ! A perfect number is a number for which the sum of its proper divisors is
12 ! exactly equal to the number. For example, the sum of the proper divisors of
13 ! 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.
15 ! A number whose proper divisors are less than the number is called deficient
16 ! and a number whose proper divisors exceed the number is called abundant.
18 ! As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest
19 ! number that can be written as the sum of two abundant numbers is 24. By
20 ! mathematical analysis, it can be shown that all integers greater than 28123
21 ! can be written as the sum of two abundant numbers. However, this upper limit
22 ! cannot be reduced any further by analysis even though it is known that the
23 ! greatest number that cannot be expressed as the sum of two abundant numbers
24 ! is less than this limit.
26 ! Find the sum of all the positive integers which cannot be written as the sum
27 ! of two abundant numbers.
33 ! The upper limit can be dropped to 20161 which reduces our search space
34 ! and every even number > 46 can be expressed as a sum of two abundants
38 : source-023 ( -- seq )
39 46 [1,b] 47 20161 2 <range> append ;
41 : abundants-upto ( n -- seq )
42 [1,b] [ abundant? ] filter ;
44 : possible-sums ( seq -- seq )
46 [ dupd '[ _ [ + _ conjoin ] with each ] each ]
51 : euler023 ( -- answer )
53 20161 abundants-upto possible-sums diff sum ;