Wednesday, May 12, 2010

nine-digit polydivisible number with 1 to 9 exactly once: 381654729

Arrange the digits 1 to 9 in order so that the first two digits form a multiple of 2, the first three digits form a multiple of 3, the first four digits form a multiple of 4 etc. and finally the entire number is a multiple of 9. It contains the digits 1 to 9 exactly once each. [Polydivisible number]

There are 9^9 9-digit numbers; 9^9 = 387420489. There are only 9! numbers with 1-9 appearing only once; 9! = 362880 (1000 times smaller set). So, the trick is to find those 9! first (using permutations or otherwise) and then check for polydivisiblity. 381654729 is the only number.

#checks if a number is polydivisible
#polydivCheck(381654729)
def polydivCheck(n, digts):
    for i in range(digts, 0, -1):
        if (n % i != 0):
            return False
        n = int(n / 10)
    return True

#checks if a number is polydivisible
#polydivCheck(381654729)
def polydivCheck(n, digts):
    for i in range(digts, 0, -1):
        if (n % i != 0):
            return False
        n = int(n / 10)
    return True

#finds permutation for array 'input' and puts the numbers in list 'nums'
def permute(digits, input, output, flags, depth, nums):
    if depth == len(input):
        num = 0
        factor = 1
        for i in range(digits, 0, -1):
            num = num + output[i - 1] * factor
            factor *= 10
        nums.append(num)
    
    for i in range(len(input)):
        if flags[i] == True:
           continue

        flags[i] = True
        output[depth] = input[i]
        
        permute(digits, input, output, flags, depth + 1, nums)
        
        flags[i] = False

#wrapper function to call the recursive 'permute' function
def permute_wrapper(digits):
    input = [i for i in range(1, digits+1)]
    output = [0 for x in range(len(input))]
    flags = [False for x in range(len(input))]
    depth = 0
    nums = []
    
    permute(digits, input, output, flags, depth, nums);
    
    return nums

#calls 'permute_wrapper' and for each number checks for polydivisibility
def getPolydivNums(digits):
    nums = permute_wrapper(digits)
    numbers=[]
    for num in nums:
        if polydivCheck(num, digits):
            numbers.append(num)
    return numbers

#start(9)
def start(digits):
    nums = getPolydivNums(digits)
    for n in nums:
        print(n)

It is quicker to bust out once the buffer is not polydivisible while building it.
get-polydivisible():
    digits = [1,2,3,4,5,6,7,8,9]
    out = new
    used = new
    buffer = new
    depth = 0
    process(digits, out, used, buffer, depth)
    return out

process(in, out, used, buffer, depth):
    if depth > 0 && !is-divisible(buffer.tostring()):
        return
    if depth == in.length:
        out.add(int.parse(s))
        return
    for i=0, < in.length:
        if used[i]:
            continue
        used[i] = true
        buffer.append(in[i])
        process(in, out, used, buffer, depth +1)
        buffer.length--
        used[i] = false

is-divisible(s):
    return int.parse(s) % s.length == 0

[Hat tip to JF]

1 comment: