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!