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
4 sequences project-euler.common math.bitwise ;
7 ! http://projecteuler.net/index.php?section=problems&id=46
12 ! It was proposed by Christian Goldbach that every odd composite number can be
13 ! written as the sum of a prime and twice a square.
22 ! It turns out that the conjecture was false.
24 ! What is the smallest odd composite that cannot be written as the sum of a
25 ! prime and twice a square?
33 : perfect-squares ( n -- seq )
34 2 /i sqrt >integer [1,b] [ sq ] map ;
36 : fits-conjecture? ( n -- ? )
37 dup perfect-squares [ 2 * - ] with map [ prime? ] any? ;
39 : next-odd-composite ( n -- m )
40 dup odd? [ 2 + ] [ 1 + ] if dup prime? [ next-odd-composite ] when ;
42 : disprove-conjecture ( n -- m )
43 dup fits-conjecture? [ next-odd-composite disprove-conjecture ] when ;
47 : euler046 ( -- answer )
48 9 disprove-conjecture ;
50 ! [ euler046 ] 100 ave-time
51 ! 37 ms ave run time - 3.39 SD (100 trials)