Seeking 5 primes such that concatenating any two of them produces another prime
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 (&gt;= (length acc) 3) acc '())
          (if (prime? (list-&gt;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)) -&gt; '(((4) (6 7)) ((4 6) (7)))
(decompose '(2)) -&gt; '()
(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-&gt;number (car x)))
                                  (prime? (list-&gt;number (cadr x)))
                                  (prime? (list-&gt;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.