HOME SUMMARY

Problem 37

1. Problem

Truncatable Primes

The number 3787 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。

如果一个素数满足,无论从左往右还是从右往左逐一截去数字,剩下的仍然都是素数,则称之为可截素数。已知总共有十一个可截素数,求这些数的和。

注意:2、3、5 和 7 不被视为可截素数。

2. Solution

由于从左往右截断和从右往左截断都要求数字是素数,那么数字中就不可能含有 4, 6, 8,组成数字的只能是 1,2,3,5,7,9(且 1, 2, 5, 9 不能作为尾数)。使用如下代码我们可以求得满足从右向左截断的素数:

(defun eu37-product (a b)
  (apply 'append
         (mapcar (lambda (x)
                   (mapcar
                    (lambda (y)
                      (+ (* x 10) y))
                    b))
                 a)))

(setq eu37-add-right
      (let ((res)
            (ls '(2 3 5 7))
            tmp
            (c '(1 3 5 7 9)))
        (while ls
          (setq tmp (eu37-product ls c))
          (setq ls (cl-remove-if-not
                    'eu7-isprime
                    tmp))
          (cl-loop for a in ls
                   do (push a res)))
        res))

接着,我们从中找出满足从左往右截断素数的数字即可:

(defun eu37-judge (n ls)
  (while (and (> n 10) (eu7-isprime n))
    (let ((e (floor (log n 10))))
      (setq n (% n (expt 10 e)))))
  (and (not (> n 10))
       (/= n 1)
       (/= n 9)))

(cl-loop for a in eu37-add-right
         if (eu37-judge a eu37-add-right)
         collect a)
=> (739397 3797 3137 797 373 317 313 73 53 37 23)
(+ 739397 3797 3137 797 373 317 313 73 53 37 23)
=> 748317