043. 子串可整除性(sub-string divisibility)

数字1406357289由0至9的各位数构成,因此是一个0至9的全数字,除此之外,它还有一个有趣的子串可整除性质。设\(d_1\)表示第一位数,\(d_2\)表示第二位数等等,我们可以发现:

  • \(d_2d_3d_4=406\)可以被\(2\)整除
  • \(d_3d_4d_5=063\)可以被\(3\)整除
  • \(d_4d_5d_6=635\)可以被\(5\)整除
  • \(d_5d_6d_7=357\)可以被\(7\)整除
  • \(d_6d_7d_8=572\)可以被\(11\)整除
  • \(d_7d_8d_9=728\)可以被\(13\)整除
  • \(d_8d_9d_{10}=289\)可以被\(17\)整除

求所有满足这个性质的0至9的全数字之和。

分析:这道题有两种解法,第一种解法利用题中所列素数的整除性质,并遍历所有0至9全数字的组合寻找满足要求数字并累加求和。第二种方法则需要在整除性质的基础上,对各个数位的出现数字的可能性加以分析,迭代解出满足要求的数字,使用这种方法可以直接笔算出相应结果,不需要编程。相对来说,第一种方法更好理解,但效率较低;第二种方法效率更高,但理解起来要麻烦一些。这里我同时介绍两种方法。

首先看第一种方法,根据题目条件分析各个数位应该满足的性质:

根据以上条件,我们可对所有\(10!=3628880\)个全数字进行筛选,并将最后筛选剩下的数字加总,即为所求。这个方法在我的电脑上耗时5.3秒。

第二种方法也需要用到各位数的整除性质,我们首先看\(d_6\),通过上面的分析,我们知道\(d_6\)只能取0或5。假设\(d_6=0\),则\(d_6d_7d_8\)要被11整除,则只能是\(022,033,044\cdots\)这样的形式,这显然和全数字的要求违背,所以\(d_6\)只能等于5。在已知\(d_6=5\)的情况下,满足\(d_6d_7d_8\)被11整除的数只有八个,分别是506,517,528,539,561,572,583,594。以这八个数为起点,考虑\(d_7d_8d_9\)需要被13整除,则可以进一步把满足要求的数缩减至四个,分别是5286,5390,5728,5832。以这四个数为基础,考虑\(d_8d_9d_{10}\)需要被17整除,则满足要求的数缩减至三个,分别52867,53901,57289,这是全数字最后五个数的可能选择。让我们回过头往前看,\(d_5d_6d_7\)被7整除,其中\(d_6d_7\)只有52、53和57三个选择,经过尝试发现只有952和357两个数字满足条件,则目前只剩下952867和357289两个选择。接下来\(d_3d_4d_5\)必须被3整除,同时\(d_4\)是一个偶数,\(d_5\)只有3和9两个选择,最后筛选的结果是只有三个数字满足条件,分别是30952867、 60357289和06357289。剩余前两位数,只有1和4两个选择,共有两种组合,这两种组合加上三个可能数字,对应最终的六个解,分别为1430952867、1460357289、1406357289、4130952867、4160357289 和 4106357289。

from itertools import permutations

def main():
    res,ans = [],0
    for i in permutations(range(10),10):
        d_by_three = (i[2]+i[3]+i[4])%3==0
        d_by_seven = (10*i[4]+i[5]-i[6]*2)%7==0
        d_by_eleven = (i[5]-i[6]+i[7])%11==0
        d_by_thirteen = (100*i[6]+10*i[7]+i[8])%13==0
        d_by_seventeen = (100*i[7]+10*i[8]+i[9])%17==0
        cond = d_by_three and d_by_seven and d_by_eleven and d_by_thirteen and d_by_seventeen
        if i[0]!=0 and i[5]==5 and i[3]%2==0 and cond:
            ans += sum([x*10**y for x,y in zip(i,range(9,-1,-1))])
    return ans