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 不被视为可截素数。
由于从左往右截断和从右往左截断都要求数字是素数,那么数字中就不可能含有 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