Problem 43

Sub-string Divisibility

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d₁ be the 1^st digit, d₂ be the 2^nd digit, and so on. In this way, we note the following:

• d₂d₃d₄ is divisible by 2
• d₃d₄d₅ is divisible by 3
• d₄d₅d₆ is divisible by 5
• d₅d₆d₇ is divisible by 7
• d₆d₇d₈ is divisible by 11
• d₇d₈d₉ is divisible by 13
• d₈d₉d₁₀ is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

子串的可整除性

1406357289 是一个 0 至 9 全数字数，因为它由 0 到 9 这十个数字排列而成；但除此之外，它还有一个有趣的性质：子串的可整除性。

记 d₁ 是它的第 1个数字，d₂ 是第 2个数字，依此类推，注意到：

• d₂d₃d₄ 能被 2 整除
• d₃d₄d₅ 能被 3 整除
• d₄d₅d₆ 能被 5 整除
• d₅d₆d₇ 能被 7 整除
• d₆d₇d₈ 能被 11 整除
• d₇d₈d₉ 能被 13 整除
• d₈d₉d₁₀ 能被 17 整除

找出所有满足同样性质的 0 至 9 全数字数，并求它们的和。

由于子串之间的强约束性（相邻的两个字串有两个相同的数字），我们可以考虑从头部或尾部字串作为起始推得其他字串的可行值，比如 1000 以下能被 17 整除的仅有 58 个数字，筛去含有相同数字的则仅有以下这些：

(defun eu43-num2ls (n)
  (let ((res '())
	(tmp n))
    (while (/= n 0)
      (push (% n 10) res)
      (setq n (/ n 10)))
    (when (< tmp 100)
      (push 0 res))
    res))

(defun eu43-check (ls)
  (and (= (length ls) 3)
       (= (length (delete-dups ls)) 3)))

(setq eu43-ini
      (cl-remove-if-not
       'eu43-check
       (mapcar 'eu43-num2ls
	       (cl-loop for i from 1 to 1000
			if (zerop (% i 17))
			collect i))))

(length eu43-ini) => 44

接下来一遍一遍筛就行了：

(let ((divs '(13 11 7 5 3 2))
      (facs '(0 1 2 3 4 5 6 7 8 9))
      (nums eu43-ini))
  (while divs
    (setq nums
	  (cl-loop
	   for a in nums append
	   (cl-loop
	    for b in (cl-set-difference facs a)
	    with a1 = (nth 0 a)
	    with a2 = (nth 1 a)
	    for newnum = (eu43-ls2num (list b a1 a2))
	    if (zerop (% newnum (car divs)))
	    collect (cons b a))))
    (setq divs (cdr divs)))
  (mapcar (lambda (x) (cons (car (cl-set-difference facs x))
			    x))
	  nums))
=> ((4 1 6 0 3 5 7 2 8 9) (1 4 6 0 3 5 7 2 8 9)
    (4 1 0 6 3 5 7 2 8 9) (1 4 0 6 3 5 7 2 8 9)
    (4 1 3 0 9 5 2 8 6 7) (1 4 3 0 9 5 2 8 6 7))


(cl-reduce (lambda (a b) (+ a (eu43-ls2num b)))
	   '((4 1 6 0 3 5 7 2 8 9) (1 4 6 0 3 5 7 2 8 9)
	     (4 1 0 6 3 5 7 2 8 9) (1 4 0 6 3 5 7 2 8 9)
	     (4 1 3 0 9 5 2 8 6 7) (1 4 3 0 9 5 2 8 6 7))
	   :initial-value 0)
=> 16695334890