Problem 43

Problem 43

09 May 2003

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₄=406 is divisible by 2
• d₃d₄d₅=063 is divisible by 3
• d₄d₅d₆=635 is divisible by 5
• d₅d₆d₇=357 is divisible by 7
• d₆d₇d₈=572 is divisible by 11
• d₇d₈d₉=728 is divisible by 13
• d₈d₉d₁₀=289 is divisible by 17

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

1.最后三位能被17整除

2.第6位只能是0或5

3.第4位只能是偶数

def isOk43(num):
    primes = [2,3,5,7,11,13,17]
    if (num[5] != '0') and (num[5] != '5'):
        return False
    for i in range(1, 8):
        t = int(num[i:i+3])
        if (t%primes[i-1]) != 0:
            return False
    return True
   

def fun43():
    result = 0
    for i in permutation(range(10), 10):
        i = "".join(map(str, i))
        if isOk43(i):
            result += int(i)
            print i
    return result
       
def isUnique(n):
    #判断n中是否有重复的字母
    n = str(n)
    b = set(n)
    return len(b) == len(n)
   
def fun43Quick():
    i      = 6
    result = 0
    h      = {}
    while 1:
        t = 17*i
        if t>100 and t<1000:
            if isUnique(t):
                if h.has_key(t):
                    i += 1
                    continue
                else:
                    h[t] = True
                #print t
                   
                l = range(10)
               
                for j in map(int, str(t)):
                    l.remove(j)
                for k in permutation(l, len(l)):
                    num = "".join(map(str, k))+str(t)
                    if isOk43(num):
                        print num
                        result += int(num)
            else:
                i += 1
                continue
        elif t >= 1000:
                break
    return result

程序中只用到了前两个条件，在fun43()中，我们遍历所有的组合，消耗时间过长141.657000065
在加上前两个条件后，可以将时间缩短为6.1099998951
answer is 16695334890,
符合条件的数有1406357289, 460357289, 4106357289, 4160357289, 1430952867, 4130952867