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

def helpfunc1(x,y):

    return 10*x+y

def helpfunc2(lst):

    return reduce(helpfunc1,lst)

def Descriminent(k,value):

    if k==3:

        if value%17==0:

            return True

        else:

            return False

    if k==4:

        if value%13==0:

            return True

        else:

            return False

    if k==5:

        if value%11==0:

            return True

        else:

            return False

    if k==6:

        if value%7==0:

            return True

        else:

            return False

    if k==7:

        if value%5==0:

            return True

        else:

            return False

    if k==8:

        if value%3==0 and (value//10)%2==0:

            return True

        else:

            return False

    return True

def func(result,charlist):

    total=0

    length=len(result)

    if length>2 and length<9:

        if Descriminent(length,helpfunc2(result[0:3]))==False:

            return 0

    if 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 total

charlist=[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 = 1

while j*17 < 1000:

    N = j*17

    Nstr = str(N)

    if len(set(Nstr)) == len(Nstr):

        if N < 100: res.append('0' + str(N))

        else: res.append(str(N))

    j += 1

for div in 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 = res1

    res1 = []

tot = 0

for Nstr in res:

    print(Nstr)

    tot += int(Nstr)

print(tot)