Finding 10-unique-digit number with i-first-digits divisible by i

I was posed this question by a friend:


I am a natural number written with 10 different digits such that for all \$i ∈ {1, . . ., 10}\$ the number formed by my \$i\$ first digits (from left to right) is divisible by \$i\$. Who am I?

I came up with a brute-force solution over the next hour or so (a few attempts failed) and came eventually finished with this:

# !/usr/bin/python
# -*- coding: utf-8 -*-

# build all possible permutations
import itertools
base_number = ['1','2','3','4','5','6','7','8','9','0']
perms = itertools.permutations(base_number)

# join the permutation lists into single numbers by joining each into a string
all_nums = [''.join(item[0:10]) for item in perms]

''' 
Check whether each item is divisible by i (from 10-->2) for subset of item, 
item[0:i]. For example;

    i = 10, number = 1234567890
    number[0:10]   = 1234567890 

        is this divisible by i(10)? Yes.

    i = 9, number = 1234567890
    number[0:9]   = 123456789

        is this divisible by i(9)? Yes.

    i = 8, number = 1234567890
    number[0:8]   = 12345678

        is this divisible by i(8)? No.

We do not check whether the number is divisible by 1 as all integers are 
divisible by 1.

'''  
for i in range(10,1,-1):
    legits = [x for x in all_nums if int(x[0:i])%i==0]
    all_nums = legits
    print "%-10d # of result can be divided by %d" % (len(legits),i)

print legits

I considered that a recursive algorithm could perform this task much more efficiently but have not considered how to actually code the pseudo-code'ish solution I was shown;

f(1) = {1, 2, 3, 4, 5, 6, 7, 8, 9}
f(2) = for n in f(1):
       find solutions to i for $n * 10 + i = 0 (mod 2)$
       where i isn't a digit of n.

I welcome all feedback, but I'm specifically hoping to hear about my coding-style/practices and the algorithm I developed.

Style (and related tools)

A few things are wrong concerning the style (mostly matter of whitespace). Python has a coding guideline called PEP 8. You can use pep8 (or its online version) to check it automatically and autopep8 to try to fix this automatically. You'll find various other convenient tools to check your code such as pylint, pyflakes or pychecker.

Making things more concise

You can use string.digits to have all digits.

Also, you are using more variables that you actually need.

Finally, you don't need to precise 0 in your string slicing and all your permutations will have 10 characters so you don't have to try to take the fist 10 :

Your code becomes :

# join the permutation lists into single numbers by joining each into a string
nums = [''.join(item) for item in itertools.permutations(string.digits)]

for i in range(10, 1, -1):
    nums = [x for x in nums if int(x[:i]) % i == 0]
    print "%-10d # of result can be divided by %d" % (len(nums), i)

print nums

Solution - algorithm, math, etc

Your solution looks interesting in that sense that you iterate through less and less numbers (also, starting from 10 to remove many solutions from the very beginning is a nice touch). However, the issue is that you have to check all iterations at the very beginning and this is quite costly. Also, you keep a list of them in memory.

Let's try to do things differently.

For a start, we know that the number has to be divisible by 10. Therefore, we know that the 0 will be in last position.

>>> print(len(list(itertools.permutations(['1','2','3','4','5','6','7','8','9','0']))))
3628800
>>> print(len(list(itertools.permutations(['1','2','3','4','5','6','7','8','9']))))
362880

Your first iteration should be 10 times faster and your code is indeed roughly 10 times faster.

# join the permutation lists into single numbers by joining each into a string
nums = [''.join(item) for item in itertools.permutations(['1','2','3','4','5','6','7','8','9'])]

for i in range(9, 1, -1):
    nums = [x for x in nums if int(x[:i]) % i == 0]
    print "%-10d # of result can be divided by %d" % (len(nums), i)

print [n + '0' for n in nums]

Simimarly, the divisibility by 9 does not need to be checked because of the following rule (and the fact that the sum of the first 10 numbers is divisible by 9) : remove that check and you have yet another performance gain.

However, for an actual gain, you could go the other wat round : trying to build number by looking at the different candidates of length 1, 2, and so on.

Here is how I did it and it seems to be really fast :

cand = {0}
for i in range(1, 10):
    cand = { n for n in (10 * c + d for c in cand for d in range(1, 10) if str(d) not in str(c)) if n % i == 0}
print [n * 10 for n in cand]

Also, if you were to do things manually, after notificing that 0 has to be in 10th position so that the number is divisible by 10, you can notice that it leaves only 5 to be in 5th position so that the number is divisible by 5. You have 2, 4, 6, 8 left for 2, 4, 6 and 8th position and 1, 3, 7, 9 for 1, 3, 7 and 9th position. You can do this programmatically for yet another performance optimisation.

cand = {0}
for i in range(1, 10+1):
    r = [0] if i == 10 else \
        [5] if i == 5 else \
        [1, 3, 7, 9] if i % 2 else \
        [2, 4, 6, 8]
    cand = { n for n in (10 * c + d for c in cand for d in r if (str(d) not in str(c))) if n % i == 0}
    print(i, len(cand), cand)
print cand

StackExchange Code Review Q#66556, answer score: 7