Merge branch 'master' of git://factorcode.org/git/factor
[factor/jcg.git] / extra / project-euler / 046 / 046.factor
blob7f5ad9e0d845d1f2ae1312bc57d25ad71f52f2d9
1 ! Copyright (c) 2008 Aaron Schaefer.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: kernel math math.functions math.primes math.ranges sequences ;
4 IN: project-euler.046
6 ! http://projecteuler.net/index.php?section=problems&id=46
8 ! DESCRIPTION
9 ! -----------
11 ! It was proposed by Christian Goldbach that every odd composite number can be
12 ! written as the sum of a prime and twice a square.
14 !     9  =  7 + 2 * 1^2
15 !     15 =  7 + 2 * 2^2
16 !     21 =  3 + 2 * 3^2
17 !     25 =  7 + 2 * 3^2
18 !     27 = 19 + 2 * 2^2
19 !     33 = 31 + 2 * 1^2
21 ! It turns out that the conjecture was false.
23 ! What is the smallest odd composite that cannot be written as the sum of a
24 ! prime and twice a square?
27 ! SOLUTION
28 ! --------
30 <PRIVATE
32 : perfect-squares ( n -- seq )
33     2 /i sqrt >integer [1,b] [ sq ] map ;
35 : fits-conjecture? ( n -- ? )
36     dup perfect-squares [ 2 * - ] with map [ prime? ] contains? ;
38 : next-odd-composite ( n -- m )
39     dup odd? [ 2 + ] [ 1+ ] if dup prime? [ next-odd-composite ] when ;
41 : disprove-conjecture ( n -- m )
42     dup fits-conjecture? [ next-odd-composite disprove-conjecture ] when ;
44 PRIVATE>
46 : euler046 ( -- answer )
47     9 disprove-conjecture ;
49 ! [ euler046 ] 100 ave-time
50 ! 37 ms ave run time - 3.39 SD (100 trials)
52 MAIN: euler046