Seeking 5 primes such that concatenating any two of them produces another prime

Question

I have a program which solves Project Euler problem 60:

The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

Unfortunately the program is too slow. For finding the result of 792 in the question it takes around 20 seconds. And for five primes it takes 12 hours, which is - although I was very happy that it printed the answer around 20:00 today after I started it 08:00 - too slow.

For the solution I was helped tremendously by the Stack Overflow community. Especially the users Neil Slater, Renzo and Chris Jester-Young who answered questions regarding the algorithm, the creation of a fast prime checker and the generation of prime pairs (see: 1, 2, 3, 4, 5). I find it great that although I know no one in real life who could help me with this I was helped so much anyway. Thanks for that!

Now for the performance: after generating all primes and pairs relatively quickly, the execution spends most of the time in a function get-all-combinations-that-satisfy-constraints. This function takes as input a list of primes and a list of allowed-pairs that consist of possible combinations of primes that combined lead to a new prime.

get-all-combinations-that-satisfy-constraints tries to create sets of primes with satisfy the constraints of the question. It starts a set with a prime in the list of primes and then checks if other primes can be concatenated to the front and back of every prime in the set so far (i.e., the resulting pairs are both in the list of pairs). Once it finds a prime it is added to a resulting set and the search is continued to try add a next prime, if this is not possible the previous prime is discarded and the next prime of the list is tried. This stops once we went through all starting primes. The result is a list of all combinations of 5 primes for which any concatenation of two results in new prime.

Disclaimer: I am not completely sure if the program does what I describe above.

Here is the function:

(define (get-all-combinations-that-satisfy-constraints allowed-pairs primes)

  (define (can-be-added? prime set)
    (cond ((null? set) #t)
          ((and (contains? allowed-pairs (list (car set) prime))
                (contains? allowed-pairs (list prime (car set))))
           (can-be-added? prime (cdr set)))
          (else #f)))

  (define (get-combination start-prime)
    (let loop ((primes (delete start-prime primes))
               (acc (list start-prime)))
      (cond ((null? primes) acc)
            ((can-be-added? (car primes) acc)
             (loop (cdr primes) (cons (car primes) acc)))
            (else (loop (cdr primes) acc)))))
  
  (let loop ((primes primes)
             (result '()))
    (if (null? primes) result
        (let ((combo (get-combination (car primes))))
          (if (= 4 (length combo))
              (loop (cdr primes) (cons combo result))
              (loop (cdr primes) result))))))

The results:

• The program which uses this function and finds the smallest sum of four primes which concatenate to a new prime for each combination takes ~ 20 seconds. It tries combining primes up to 1.000. Full code: 4primes-20seconds.scm.

• The program which uses this function and finds the smallest sum of five primes which concatenate to a new prime for each combination takes ~ 12 hours. It tries combining primes up to 10.000. Full code: 5primes-12hours.scm. (The memory limit needs to be set to 1024 MB.)

Why is the code so slow and is there any way execution time can be improved?

Note: general remarks on my Scheme style are very welcome as well!

Answer 1

I looked at your 4primes-20seconds.scm file and noticed a potential improvement.

    (define (get-prime-pairs lst)
  (define (find-all-prime-pairs prime lst)
    (let loop ((prime prime) 
               (lst lst) 
               (acc '()))
      (if (null? lst) (if (>= (length acc) 3) acc '())
          (if (prime? (list->number (append prime (car lst))))
              (loop prime (cdr lst) (cons (list prime (car lst)) acc))
              (loop prime (cdr lst) acc)))))
  (append-map (lambda (x) (find-all-prime-pairs x lst)) lst))

You may be able to filter quite a bit more out here because you don't just want every combination of primes that can be concatenated, you should only keep your acc if it's more than length three (for 4 prime and 4 for 5 primes)

I notice you map number->list over your primes and check every combination for a match. Just this function is n^2 time proportional to lst

You can improves your time of search from n^2 to N*log(p) (where p is the value of the prime being tested

instead of searching low to high for each possible append of primes, search high to low for each possible decomposition

(decompose '(4 6 7)) -> '(((4) (6 7)) ((4 6) (7)))
(decompose '(2)) -> '()
(define (decompose L) 
 (let loop ((A L) (B '()) (acc '()))
    (cond ((null? A) acc)
          (else (let ((A (cdr A))
                      (B (append B (list (car A)))))
                  (if (null? A) acc
                  (loop A B (cons (list A B) acc))))))))

(define (get-prime-pairs lst)
  (define (find-all-prime-pairs prime)
    (if (or (null? prime) (null? (cdr prime)))
        '()
        (let ((decomps (decompose prime)))
         (filter (lambda (x) (and (prime? (list->number (car x)))
                                  (prime? (list->number (cadr x)))
                                  (prime? (list->number
                                            (apply append x)))))
                 decomps))))
  (append-map (lambda (x) (find-all-prime-pairs x)) lst))

We make sure both decomposed parts are primes and we also make sure the other combination is prime as well. (we don't have to add it to acc as it's already showed up or will show up later in lst)

You have this even worse n^3 thing going in get-all-combinations-that-satisfy-constraints . @hen you recur down the cars of primes in the get-combinations subdefine and then recur does the cars of the set in can-be-added?, and then in contains? you recur down the cars of allowed-pairs.

My suggestion is to change allowed-pairs from a list of pairs to a hash-map where the key is a prime, and the value is a list of valid pairs. For the pair (3 7), the key 3 should have 7 as a member in it's list, and pair (7 3) key 7 should have 3 in it's list. http://sicp.ai.mit.edu/Fall-2004/manuals/scheme-7.5.5/doc/scheme_12.html#SEC105

Then get-combinations and above would compress to log time. In get-combinations loop initialize primes to lookup into the above map.

Therefore can-be-added? uses a much shorter N. Instead of allowed-pairs

  (define (can-be-added? prime set) ;psuedo-code use the hash function of your impentation
(let ((friends (hask-lookup prime allowed-pairs-hash-table))
  (let loop ((set set))
(cond ((null? set) #t)
      (contains? friends (car set))
        (can-be-added? prime (cdr set)))
      (else #f)))

I'm not 100% sure this will find all combos, you may have to have get-combination return a list of combos from trying and not-trying the next prime, but if it worked for this problem last time, not doing it should work this time.