ホーム - Project Euler

Problem 37¶

Truncatable Primes¶

The number $3797$ has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: $3797$, $797$, $97$, and $7$. Similarly we can work from right to left: $3797$, $379$, $37$, and $3$.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: $2$, $3$, $5$, and $7$ are not considered to be truncatable primes.

切り詰め可能素数¶

3797は面白い性質を持っている. まずそれ自身が素数であり, 左から右に桁を除いたときに全て素数になっている (3797, 797, 97, 7). 同様に右から左に桁を除いたときも全て素数である (3797, 379, 37, 3).

右から切り詰めても左から切り詰めても素数になるような素数は11個しかない. 総和を求めよ.

注: 2, 3, 5, 7を切り詰め可能な素数とは考えない.

(import (scheme base)
        (gauche base)
        (scheme flonum)
        (math prime)
        (scheme list))

(define temp-primes (primes))

(define (number-of-digit n)
  (assume (exact-integer? n))
  (assume (<= 0 n))
  (if (zero? n)
    1
    (+ (floor->exact
         (fllog10 n))
       1)))

(define (left-trancate n)
  (assume (exact-integer? n))
  (assume (<= 10 n))
  (let* ([dn (number-of-digit n)]
         [module-num (expt 10
                           (- dn 1))])
    (mod n module-num)))

(define (right-trancate n)
  (assume (exact-integer? n))
  (assume (<= 10 n))
  (div n 10))

(define (trancates-list n proc)
  (assume (exact-integer? n))
  (assume (<= 0 n))
  (if (< n 10)
    '()
    (let loop ([current n] [result `(,n)])
      (if (< current 10)
        result
        (let ([next (proc current)])
          (loop next
                (cons next result)))))))

(define (prime? n)
  (= (car
       (drop-while (cut < <> n)
                   temp-primes))
     n))

(define all-trancate-nums
  (let loop ([find-count 0] [rest-primes temp-primes] [result '()])
    (if (<= 11 find-count)
      result
      (let ([current-prime (car rest-primes)]
            [rest-primes (cdr rest-primes)])
        (cond
          [(< current-prime 10)
           (loop find-count rest-primes result)]
          [(and (every prime?
                       (trancates-list current-prime left-trancate))
                (every prime?
                       (trancates-list current-prime right-trancate)))
           (loop (+ find-count 1)
                 rest-primes
                 (cons current-prime result))]
          [else (loop find-count rest-primes result)])))))

(define answer-37
  (apply + all-trancate-nums))

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