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