# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1643: Divisibility test

From New Scientist #2809, 23rd April 2011 [link]

abcdefghij is a 10-digit number containing one each of the digits 0 to 9 in some order (a ≠ 0). With the exception of the letter which represents zero, a divides abcdefghij, b divides bcdefghij, c divides cdefghij and so on to the end.

What are the largest and smallest 10-digit numbers with this property?

[enigma1643]

### One response to “Enigma 1643: Divisibility test”

1. jimrandell 7 December 2011 at 7:33 pm

Generating all possible permutations and finding the maximum and minimum numbers that satisfy the conditions takes the following Python program around 5.4s:

```from itertools import permutations
from enigma import irange, printf

def check(s):
if s[0] == 0: return 0
n = 0
p = 1
for d in reversed(s):
n += d * p
if d > 0 and n % d > 0: return 0
p *= 10
return n

ns = []
for s in permutations(irange(0, 9), 10):
n = check(s)
if n > 0: ns.append(n)

printf("{n} solutions, max = {max}, min = {min}", n=len(ns), min=min(ns), max=max(ns))
```

We can unroll the loop and do early rejection of numbers that fail the condition in the early digits. That’s a longer program, but runs in 163ms.

However, if we set up the initial list correctly we can use the order that permutations are generated by Python to find only the first solution. Which gives us the maximum and minimum numbers in 31ms.

```from itertools import permutations
from enigma import irange, printf

def check(s):
if s[0] == 0: return 0
n = 0
p = 1
for d in reversed(s):
n += d * p
if d > 0 and n % d > 0: return 0
p *= 10
return n

for s in permutations([1, 0, 2, 3, 4, 5, 6, 7, 8, 9]):
n = check(s)
if n > 0:
printf("min = {n}")
break

for s in permutations([9, 8, 7, 6, 5, 4, 3, 2, 1, 0]):
n = check(s)
if n > 0:
print("max = {n}")
break
```

Solution: The largest such number is 9876351240. The smallest is 1234897560.