HOME SUMMARY

Problem 41

1. Problem

Pandigital Prime

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

全数字素数

如果一个 n 位数恰好使用了 1 至 n 每个数字各一次,则称为全数字数。例如,2143 就是一个 4 位全数字数,同时它也是一个素数。

最大的全数字素数是多少?

2. Solution

一般来说题目给出的例子不会是最大的结果,因此我们可以从五位数开始。由于五位数的各位和为 15(三的倍数)故不可,六位数为 15 + 6 = 21 同样不行,七位数为 28,八位数为 36 不行,九位数为 45 不行。

综上,唯一可能的数字只有七位数了。对整个 1000000 到 9999999 遍历也用不了多少时间,不过既然还能优化最好还是不要这样做,如果这个数字为素数的话它的结尾只能是 1,3,7。这样我们需要检测的数字只有 3 * 6! = 2160 个了。

(defun eu41-gen (ls tail)
  (cond
   ((null ls) `((,tail)))
   (t (cl-loop
       for a in ls append
       (let ((res (eu41-gen (remove a ls) tail)))
         (cl-loop
          for b in res collect
          (cons a b)))))))

(defun eu41-list2num (ls)
  (cl-reduce (lambda (s a) (+ (* s 10) a)) ls))

(setq eu41-nums
      (mapcar 'eu41-list2num
              (append (eu41-gen '(1 2 3 4 5 6) 7)
                      (eu41-gen '(2 3 4 5 6 7) 1)
                      (eu41-gen '(1 2 4 5 6 7) 3))))

接着使用朴素素数判断方法即可:

(defun eu7-isprime (n)
  (cond
   ((<= n 1) nil)
   ((< n 4) t)
   ((zerop (% n 2)) nil)
   ((< n 9) t)
   ((zerop (% n 3)) nil)
   (t (let ((bound (floor (sqrt n))))
        (named-let f ((i 5))
          (cond
           ((> i bound) t)
           ((zerop (% n i)) nil)
           ((zerop (% n (+ i 2))) nil)
           (t (f (+ i 6)))))))))

(nth 0 (sort (cl-remove-if-not 'eu7-isprime eu41-nums) '>))
=> 7652413