extra/project-euler/060/060.factor

   1 ! Copyright (C) 2018 John Benediktsson
   2 ! See http://factorcode.org/license.txt for BSD license
   3
   4 USING: backtrack backtrack.private combinators.short-circuit
   5 kernel math math.functions math.primes
   6 project-euler.common sequences ;
   7
   8 IN: project-euler.060
   9
  10 ! http://projecteuler.net/problem=60
  11
  12 ! DESCRIPTION
  13 ! -----------
  14
  15 ! The primes 3, 7, 109, and 673, are quite remarkable. By taking
  16 ! any two primes and concatenating them in any order the result
  17 ! will always be prime. For example, taking 7 and 109, both 7109
  18 ! and 1097 are prime. The sum of these four primes, 792,
  19 ! represents the lowest sum for a set of four primes with this
  20 ! property.
  21
  22 ! Find the lowest sum for a set of five primes for which any two
  23 ! primes concatenate to produce another prime.
  24
  25
  26 ! SOLUTION
  27 ! --------
  28
  29 : join-numbers ( m n -- x )
  30     over log10 ceiling >integer 10^ * + ;
  31
  32 : prime-pair? ( m n -- ? )
  33     {
  34         [ join-numbers prime? ]
  35         [ swap join-numbers prime? ]
  36     } 2&& ;
  37
  38 :: (euler060) ( -- primes )
  39     [
  40         1/0. :> result!
  41         10000 primes-upto :> primes1
  42
  43         primes1 amb-integer :> i
  44         i primes1 nth :> a
  45         primes1 i 1 + tail-slice [
  46             { [ 4 * a + result < ] [ a prime-pair? ] } 1&&
  47         ] filter :> primes2
  48
  49         primes2 amb-integer :> j
  50         j primes2 nth :> b
  51         primes2 j 1 + tail-slice [
  52             { [ 3 * a b + + result < ] [ b prime-pair? ] } 1&&
  53         ] filter :> primes3
  54
  55         primes3 amb-integer :> k
  56         k primes3 nth :> c
  57         primes3 k 1 + tail-slice [
  58             { [ 2 * a b c + + + result < ] [ c prime-pair? ] } 1&&
  59         ] filter :> primes4
  60
  61         primes4 amb-integer :> l
  62         l primes4 nth :> d
  63         primes4 l 1 + tail-slice [
  64             { [ a b c d + + + + result < ] [ d prime-pair? ] } 1&&
  65         ] filter :> primes5
  66
  67         primes5 amb-lazy :> e
  68
  69         { a b c d e } dup sum result!
  70     ] bag-of last ;
  71
  72 : euler060 ( -- answer )
  73     (euler060) sum ;
  74
  75 SOLUTION: euler060