# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1691: Factory parts

From New Scientist #2858, 31st March 2012 [link]

The number 3120 is divisible without remainder by each number in the following set: 3, 312, 12, 120, 2 and 20. Each of these numbers will be called a visible proper divisor (VPD) of 3120 because each is visible either as a single digit or as a group of adjacent digits in 3120. (1 and 3120 have been excluded as being improper, in order that any prime number has no VPDs).

ENIGMA represents an odd six-digit number in which all the digits are different. The set of all VPDs of ENIGMA is E, NI, IG, G, GMA, M, MA, and A. What is ENIGMA?

[enigma1691]

### 6 responses to “Enigma 1691: Factory parts”

1. Jim Randell 28 March 2012 at 7:21 pm

Here’s my first attempt in Python. It runs in 1.7s.

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

ds = set(range(1, 10))
ls = ("ENIGMA", "E", "NI", "IG", "G", "GMA", "M", "MA", "A")

# A must be odd
for A in (1, 3, 5, 7, 9):
l2n = { 'A': A }
# and the other letters must be non-zero
for s in permutations(ds.difference((A,)), 5):
l2n.update(zip("ENIGM", s))
vpds = list(int(concat(*(l2n[i] for i in l))) for l in ls)
ENIGMA = vpds.pop(0)

# check all VPDs divide ENIGMA
if any(ENIGMA % vpd for vpd in vpds): continue

# check that these are the only VPDs
s = str(ENIGMA)
n = len(s)
vs = []
for i in range(n):
for j in range(i+1, n+1):
vpd = int(s[i:j])
if vpd in (1, ENIGMA): continue
if ENIGMA % vpd: continue
vs.append(vpd)
if vs != vpds: continue

printf("ENIGMA={ENIGMA}, VPDs: {vpds}")
```

Solution: ENIGMA = 921375.

• Jim Randell 28 March 2012 at 11:28 pm

As 1 is not allowed as a VPD, we can ignore cases where one of E, G, M, A is 1. This version runs in 794ms (and gives the same answer).

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

ds = set(range(1, 10))
ls = ("ENIGMA", "E", "NI", "IG", "G", "GMA", "M", "MA", "A")

# 1 is not allowed as a VPD, so E, G, M, A cannot be 1

# A must be odd
for A in (3, 5, 7, 9):
l2n = { 'A': A }
for EGM in permutations(ds.difference((A, 1)), 3):
l2n.update(zip("EGM", EGM))
for NI in permutations(ds.difference((A,), EGM), 2):
l2n.update(zip("NI", NI))
vpds = list(int(concat(*(l2n[i] for i in l))) for l in ls)
ENIGMA = vpds.pop(0)

# check all VPDs divide ENIGMA
if any(ENIGMA % vpd for vpd in vpds): continue

# check that these are the only VPDs
s = str(ENIGMA)
n = len(s)
vs = []
for i in range(n):
for j in range(i+1, n+1):
vpd = int(s[i:j])
if vpd in (1, ENIGMA): continue
if ENIGMA % vpd: continue
vs.append(vpd)
if vs != vpds: continue

printf("ENIGMA={ENIGMA}, VPDs: {vpds}")
```
• Jim Randell 29 March 2012 at 7:44 am

Here’s a version that sets up the indices of substrings that are VPDs, and those that aren’t VPDs. It runs in 135ms.

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

# substrings that are VPDs
vpds = ((0, 1), (1, 3), (2, 4), (3, 4), (3, 6), (4, 5), (4, 6), (5, 6))

# substrings that aren't
nvpds = list((i, j) for i in range(7) for j in range(i + 1, 7) if (i, j) not in vpds)
nvpds.remove((0, 6)) # but not the whole string

# 1 is not allowed as a VPD, so E, G, M, A cannot be 1
# A must be odd

ds = set(range(1, 10))
for A in (3, 5, 7, 9):
for E, G, M in permutations(ds.difference((A, 1)), 3):
for N, I in permutations(ds.difference((A, E, G, M)), 2):
s = concat(E, N, I, G, M, A)
ENIGMA = int(s)
# check all VPDs divide ENIGMA
if any(ENIGMA % int(s[i:j]) for i, j in vpds): continue
# check the other substrings aren't VPDs
if any(map(lambda x: x > 1 and ENIGMA % x == 0, (int(s[i:j]) for i, j in nvpds))): continue

printf("ENIGMA={ENIGMA}")
```
2. Brian Gladman 29 March 2012 at 12:37 pm

Here is my version:

```from itertools import permutations

# The units digit of the divisors must all be odd because ENIGMA is odd
# and cannot hence have an even divisor.  But E, G, M and A cannot be 1
# because 1 is excluded as a proper divisor. Hence I must be 1 and N is
# not 0.

vpdw = ( 'E', 'NI', 'IG', 'G', 'GMA', 'M', 'MA', 'A')
d = { 'I':'1' }
for p in permutations('3579', 4):
d.update(zip('AEGM', p))
for n in '2468':
d['N'] = n
enigma = int(''.join(d[c] for c in 'ENIGMA'))
vpd = tuple(int(''.join(d[c] for c in w)) for w in vpdw)
if not any(enigma % x for x in vpd):
print('ENIGMA =', enigma)
```
• Jim Randell 3 April 2012 at 8:42 am

Your analysis massively reduces the search space to only 96 cases, only one of which has all of the required VPDs. Although I think it is still necessary to check that that candidate has no other VPDs to strictly satisfy the conditions of the question.

Here’s my final code. It executes in 37ms.

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

# indices of substrings that are VPDs
vpdw = ( "E", "NI", "IG", "G", "GMA", "M", "MA", "A" )
vpds = list((a, a + b) for a, b in (("ENIGMA".find(w), len(w)) for w in vpdw))

# and indices of substrings that aren't
nvpds = list((i, j) for i in range(7) for j in range(i + 1, 7) if (i, j) not in vpds)
nvpds.remove((0, 6)) # but not the whole string

# E, I, G, M, A must all be odd (as ENIGMA can have no even divisors)
# also 1 is not allowed as a VPD, so E, G, M, A cannot be 1
# hence I = 1, and A, E, G, M are 3, 5, 7, 9 (in some order)
# leaving N to be an even (non-zero) digit

I = 1
for (A, E, G, M) in permutations((3, 5, 7, 9)):
for N in (2, 4, 6, 8):
s = concat(E, N, I, G, M, A)
ENIGMA = int(s)
# check all VPDs divide ENIGMA
if any(ENIGMA % int(s[i:j]) for i, j in vpds): continue
# check the other substrings aren't VPDs
if any(ENIGMA % n == 0 for n in (int(s[i:j]) for i, j in nvpds) if n > 1): continue
printf("ENIGMA={ENIGMA}")
```
3. Brian Gladman 3 April 2012 at 4:27 pm

If I had got more than one solution, I would have done so 🙂