Sub-string divisibility Problem 43 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 d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:
d2d3d4=406 is divisible by 2 d3d4d5=063 is divisible by 3 d4d5d6=635 is divisible by 5 d5d6d7=357 is divisible by 7 d6d7d8=572 is divisible by 11 d7d8d9=728 is divisible by 13 d8d9d10=289 is divisible by 17 Find the sum of all 0 to 9 pandigital numbers with this property.
Answer: 16695334890 python code:
from functools import reduce:return 10*x+y:return reduce(helpfunc1,lst):if k==3:if value%17==0::k==4:if value%13==0::k==5:if value%11==0::k==6:if value%7==0::k==7:if value%5==0::k==8:if value%3==0 and (value//10)%2==0:::total=0length=len(result)if length>2 and length<9:if Descriminent(length,helpfunc2(result[0:3]))==False:length==10:return helpfunc2(result)if len(charlist)>0:for i in range(0,len(charlist)):resultNext=result.copy()charlistNext=charlist.copy()resultNext.insert(0,charlistNext[i])del charlistNext[i]total+=func(resultNext,charlistNext)return totalcharlist=[0,1,2,3,4,5,6,7,8,9]result=[]print(func(result,charlist))
解题思路：使用递归 提高效率点：从后往前递归 计算时间<1s
因为能够整除2的数比整除17的多的太多了，，其他的一样道理。因此相比于从后往前，从前往后递归的话无用功将成阶乘阶数增加。
EularProject论坛上的一个非递归版本
digits = [‘1′,’2′,’3′,’4′,’5′,’6′,’7′,’8′,’9′,’0’]divisors = [13, 11, 7, 5, 3, 2, 1]res = []res1 = []j = 1while j*17 < 1000:N = j*17Nstr = str(N)if len(set(Nstr)) == len(Nstr):if N < 100: res.append(‘0’ + str(N))else: res.append(str(N))j += divisors:for Nstr in res:for d in digits:if d not in Nstr:Newstr = d + Nstr[:2]if int(Newstr)%div == 0:res1.append(d + Nstr)res = res1res1 = []tot = 0for Nstr in res:print(Nstr)tot += int(Nstr)print(tot)
接受失败等于打破完美的面具，接受失败等于放松自己高压的心理，
