Project Euler

[ホーム](https://redmine.noppi.jp) - [[Wiki|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を切り詰め可能な素数とは考えない.

```scheme

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

```