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