Project Euler

[ホーム](https://redmine.noppi.jp) - [[Wiki|Project Euler]]

# [[Problem 60]]

## Prime Pair Sets

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.

## 素数ペア集合

素数3, 7, 109, 673は非凡な性質を持っている. 任意の2つの素数を任意の順で繋げると, また素数になっている. 例えば, 7と109を用いると, 7109と1097の両方が素数である. これら4つの素数の和は792である. これは, このような性質をもつ4つの素数の集合の和の中で最小である.

任意の2つの素数を繋げたときに別の素数が生成される, 5つの素数の集合の和の中で最小のものを求めよ.

```scheme

(import (scheme base)

        (gauche base)

        (scheme inexact)

        (scheme list))

(define (prime? num)

  (assume (exact-integer? num))

  (assume (positive? num))

  (cond

    [(= num 1) #f]

    [(= num 2) #t]

    [(even? num) #f]

    [(= num 3) #t]

    [(zero? (mod num 3)) #f]

    [else

      (let loop ([n6-1 5])

        (let ([n6+1 (+ n6-1 2)])

          (cond

            [(< num

                (* n6-1 n6-1))

             #t]

            [(zero? (mod num n6-1))

             #f]

            [(< num

                (* n6+1 n6+1))

             #t]

            [(zero? (mod num n6+1))

             #f]

            [else

              (loop (+ n6+1 4))])))]))

(define prime-generator

  (let ([current-primes '(2 3 5 7)]

        [inc 4]

        [prime? (^[num current-primes]

                  (assume (exact-integer? num))

                  (assume (< 7 num))

                  (let loop ([rest-primes current-primes])

                    (let ([rest (car rest-primes)])

                      (cond

                        [(< num

                            (* rest rest))

                         #t]

                        [(zero? (mod num rest))

                         #f]

                        [else

                          (loop (cdr rest-primes))]))))])

    (lambda ()

      (let loop ([next-prime (+ (last current-primes)

                                inc)]

                 [next-inc (if (= inc 2)

                             4

                             2)])

        (cond

          [(prime? next-prime current-primes)

           (set! current-primes (append current-primes `(,next-prime)))

           (set! inc next-inc)

           next-prime]

          [else

            (loop (+ next-prime next-inc)

                  (if (= next-inc 2)

                    4

                    2))])))))

(define prime-list (generator->lseq 3 7

                                    prime-generator))

(define (digit-num num)

  (+ (floor->exact (log num 10))

     1))

(define (perm-number lis num)

  (let loop ([rest lis] [result '()])

    (if (null? rest)

      result

      (let* ([current (car rest)]

             [num1 (+ (* num (expt 10 (digit-num current)))

                      current)]

             [num2 (+ (* current (expt 10 (digit-num num)))

                      num)])

        (loop (cdr rest) (cons* num1 num2 result))))))

(define (perm-number-all-prime? lis num)

  (every prime? (perm-number lis num)))

(define (perm-prime-list num)

  (let ([target-prime-list (take-while (cut < <> num)

                                       prime-list)])

    (let loop ([rest-primes target-prime-list]

               [candidate '()])

      (cond

        [(null? rest-primes) #f]

        [(<= 5 (length candidate))

         candidate]

        [else

          (let ([next-candidate-list (filter (^[lis]

                                               (if (null? (cdr lis))

                                                 #t

                                                 (perm-number-all-prime? (cdr lis) (car lis))))

                                             (map (^n (cons n candidate))

                                                  rest-primes))])

            (any (^[lis]

                   (loop (delete (car lis) rest-primes)

                         (cons (car lis) candidate)))

                 next-candidate-list))]))))

(define answer-60

  (apply + (perm-prime-list 10000)))

(format #t "60: ~d~%" answer-60)

```