# Enigmatic Code

Programming Enigma Puzzles

## Enigma 316: The min-factor game

From New Scientist #1464, 11th July 1985 [link]

This is a game between you and the Devil. It starts with the natural numbers from 1 to N written in a row. You and the Devil play alternately, you first. The rules are simple:

(a) You take any number you choose (subject to rule (d) below) from those remaining in the row and delete it from the row.
(b) He then deletes from the numbers remaining in the row all those which are factors of the number you just took.
(c) Go to (a).
(d) You can never take a number which has no factor remaining in the row; that is, your take must permit the Devil in his turn to delete at least one number.

The game stops when you can legally take no more numbers, and you want the sum S of all the numbers you have taken to be as small as possible.

The picture records a game with N=7 and S=6. You did very well. Now try with N=30.

How small can you make S?

[enigma316]

### 5 responses to “Enigma 316: The min-factor game”

1. Jim Randell 23 October 2015 at 9:52 am

This is similar to Enigma 295.

This program recursively chooses a number to delete, but prunes away branches that can’t beat the current minimum. It runs in 41.6s.

```from enigma import irange, diff, Accumulator, printf

import sys
N = (30 if len(sys.argv) < 2 else int(sys.argv[1]))

# ns - numbers remaining
# ss - numbers taken
# m - accumulator for min score
def play(ns, ss, m):
# find remaining numbers with divisors
fs = list()
for (i, n) in enumerate(ns):
f = list(x for x in ns[:i] if n % x == 0)
if f:
fs.append(f + [n])
# if there are no further plays
s = sum(ss)
if not fs:
m.accumulate_data(s, ss)
if s == m.value:
printf("[{s} @ {ss}]")
else:
for f in fs:
if s + f[-1] < m.value:
play(diff(ns, f), ss + [f[-1]], m)

m = Accumulator(fn=min, value=N * N)
play(list(irange(1, N)), [], m)
printf("[N={N}] min score = {m.value} @ {m.data}")
```

Solution: The minimum score for N=30 is 103.

One possible sequence is (13, 9, 15, 10, 8, 12, 14, 22).

2. Julian Gray 23 October 2015 at 4:47 pm

Jim, I think that taking 13 is an illegal move because the Devil can’t respond. Instead 26 can removed any time after 10 and 2. That makes N = 116.

• Jim Randell 23 October 2015 at 4:55 pm

On the first move the Devil will always remove 1, so it’s your only opportunity to get rid of a prime. In fact, the only illegal first move would be to choose 1 itself.

3. Brian Gladman 23 October 2015 at 8:56 pm

Essentially the same approach.

```from sys import argv

N = (30 if len(argv) < 2 else int(argv[1]))
# the numbers to be considered
nbrs = set(range(1, N + 1))
# for the current minimum sum of the numbers taken
s_min = N * (N + 1) // 2
# pre-compute the divisors of each of the numbers
div = {n:set(x for x in range(1, n + 1) if n % x == 0) for n in nbrs}

# play a round in the game with the numbers remaining in 'nbrs',
# the numbers picked so far in 'taken' and a dictionary of the
# divisors of all the numbers in 'div'
def round(nbrs, taken):
global s_min, div
# find numbers in 'nbrs' with more than one divisor in 'nbrs'
p = [n for n in nbrs if len(div[n] & nbrs) > 1]
# the game finishes if there are none
if not p:
yield taken
else:
# only consider numbers that can give a minimum sum less
# than the lowest minimum so far found
n_max = s_min - sum(taken)
# select a number to take
for n in p:
if n < n_max:
# continue to the next round
yield from round(nbrs - div[n], taken + [n])

# find solutions for the game
for taken in round(nbrs, []):
s = sum(taken)
# do we have a new minimum?
if s < s_min:
# if so output the sum and the values taken
s_min = s
print(s, taken)
```