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

Question

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.

• Martin R: Here the problem is solved without using a computer (search for "Unique Pandigital").

Answer 1

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

• whereswalden: A comment on PEP8: know when to ignore it

Answer 2

Another way of approaching this problem would be to iterate over numbers instead of over divisors. It might result in a speed improvement or it might not, but it's worth trying at the very least:

for num in all_nums:
 if all(int(num[0:i])%i==0 for i in range(10,1,-1)):
 print "Solution: " + num

all will exit as soon as it finds a failed case, so for example with 123456789 using 7-2 as divisors would not be checked.

I'm not sure what effect this would have on speed, but it's generally better practice to iterate over an iterator, rather than saving a list to memory and iterating over it:

base_number = ['1','2','3','4','5','6','7','8','9','0']
for strnum in itertools.permutations(base_number):
 num = int(''.join(strnum))
 #do stuff

You could also iterate over a generator expression that did the join, or use map in Python3. In Python2, map returns a list which rather defeats the point.

Finally, as far as I can tell, there was no need for slicing item on this line:

all_nums = [''.join(item[0:10]) for item in perms]

It would work just as well (and run a little faster) to do this:

all_nums = [''.join(item) for item in perms]

In fact, this is exactly what map is for (though I'm not sure how it compares in performance):

all_nums = map(''.join, perms)

There's nothing wrong with using a list comprehension there however, it's just a matter of preference.

• Luke Shillabeer: Thanks, I should really consider running all my code through a PEP8 checker before posting it. I've read that Guido considers map/lambda/reduce non-pythonic and that list-comprehensions are preferable, but I (naively) can see two sides to the argument.
• SylvainD: "At present, your algorithm checks numbers that have already failed another test.". That's not how I understand OP's code. Numbers gets filtered as you we go through the different values of i.
• whereswalden: @Jonsay: whoops, missed the all_nums=legits line.