extra/project-euler/060/060.factor

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