extra/project-euler/046/046.factor

   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
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=46
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  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.
  13
  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
  20
  21 ! It turns out that the conjecture was false.
  22
  23 ! What is the smallest odd composite that cannot be written as the sum of a
  24 ! prime and twice a square?
  25
  26
  27 ! SOLUTION
  28 ! --------
  29
  30 <PRIVATE
  31
  32 : perfect-squares ( n -- seq )
  33     2 /i sqrt >integer [1,b] [ sq ] map ;
  34
  35 : fits-conjecture? ( n -- ? )
  36     dup perfect-squares [ 2 * - ] with map [ prime? ] any? ;
  37
  38 : next-odd-composite ( n -- m )
  39     dup odd? [ 2 + ] [ 1+ ] if dup prime? [ next-odd-composite ] when ;
  40
  41 : disprove-conjecture ( n -- m )
  42     dup fits-conjecture? [ next-odd-composite disprove-conjecture ] when ;
  43
  44 PRIVATE>
  45
  46 : euler046 ( -- answer )
  47     9 disprove-conjecture ;
  48
  49 ! [ euler046 ] 100 ave-time
  50 ! 37 ms ave run time - 3.39 SD (100 trials)
  51
  52 MAIN: euler046