Problem 38

Problem 38

28 February 2003

Take the number 192 and multiply it by each of 1, 2, and 3:

192 1 = 192
192 2 = 384
192 3 = 576

By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n 1?

def isOk38(num):
    i    = 1#被乘数的位数
    isOk = True
    while i < 5:
        isOk  = True
        a     = int(num[0:i])#被乘数
        index = i
        mult  = 2#乘数
        while index < 9:
            t = a*mult
            s = str(t)
            if (index+len(s) <= len(num)) and s == num[index:index+len(s)]:
                index += len(s)
                mult  += 1
            else:
                isOk = False
                break
        if isOk:
            return True
        else:
            i += 1
    return isOk
       

def fun38():
    aList = range(1, 10)
    aList.reverse()
    for i in permutation(aList, 9):
        num = "".join(map(str, i))
        if isOk38(num):
            return num

倒过来遍历9-1的排列
answer is 932718654
time:1.34400010109