extra/project-euler/046/046.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See https://factorcode.org/license.txt for BSD license.
   3 USING: kernel math math.functions math.primes ranges sequences
   4 project-euler.common ;
   5 IN: project-euler.046
   6
   7 ! https://projecteuler.net/problem=46
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  12 ! It was proposed by Christian Goldbach that every odd composite
  13 ! number can be written as the sum of a prime and twice a
  14 ! square.
  15
  16 !     9  =  7 + 2 * 1^2
  17 !     15 =  7 + 2 * 2^2
  18 !     21 =  3 + 2 * 3^2
  19 !     25 =  7 + 2 * 3^2
  20 !     27 = 19 + 2 * 2^2
  21 !     33 = 31 + 2 * 1^2
  22
  23 ! It turns out that the conjecture was false.
  24
  25 ! What is the smallest odd composite that cannot be written as
  26 ! the sum of a prime and twice a square?
  27
  28
  29 ! SOLUTION
  30 ! --------
  31
  32 <PRIVATE
  33
  34 : perfect-squares ( n -- seq )
  35     2 /i sqrt >integer [1..b] [ sq ] map ;
  36
  37 : fits-conjecture? ( n -- ? )
  38     dup perfect-squares [ 2 * - ] with map [ prime? ] any? ;
  39
  40 : next-odd-composite ( n -- m )
  41     dup odd? [ 2 + ] [ 1 + ] if dup prime? [ next-odd-composite ] when ;
  42
  43 : disprove-conjecture ( n -- m )
  44     dup fits-conjecture? [ next-odd-composite disprove-conjecture ] when ;
  45
  46 PRIVATE>
  47
  48 : euler046 ( -- answer )
  49     9 disprove-conjecture ;
  50
  51 ! [ euler046 ] 100 ave-time
  52 ! 37 ms ave run time - 3.39 SD (100 trials)
  53
  54 SOLUTION: euler046