ホーム - 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つの素数の集合の和の中で最小のものを求めよ.

(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)