# Enigmatic Code

Programming Enigma Puzzles

## Enigma 295: The max-multiple game

From New Scientist #1443, 14th February 1985 [link]

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

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

The games stops when you can legally take no more numbers, and you want the sum S of all the numbers you have take to be as large as possible. The picture records a game with N=9 and S=8. You could have done better. Now try with N=35. How large can you make S?

Also, today is (Spoiler Alert!) Cheryl’s Birthday!

[enigma295]

### 4 responses to “Enigma 295: The max-multiple game”

1. Jim Randell 16 July 2015 at 9:19 am

This isn’t the fastest program, but it is short and it does find the maximum score. It plays the game recursively, eliminating choices that cannot beat the current maximum. For N=35 it takes 6m14s to run to completion (although it does find the maximum score after a few seconds). It should be possible to write a more sophisticated program that has shorter run times.

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

import sys
N = (35 if len(sys.argv) < 2 else int(sys.argv))

# ns - numbers remaining
# ss - numbers taken
# s - sum(ss)
# m - accumulator for max score
def play(ns, ss, s, m):

# are we done?
if not ns:
m.accumulate_data(s, ss)
if s == m.value: printf("[{s} @ {ss}]")
return

# record multiples
ms = dict((n, list(x for x in ns if x % n == 0)) for n in ns)
# keys with more than one multiple
ks = list(k for (k, v) in ms.items() if len(v) > 1)
# can we beat the current value?
if s + sum(ks) > m.value:
# try each key
for k in ks:
play(diff(ns, ms[k]), ss + [k], s + k, m)

# numbers that can be played
ns = list(irange(N, 1, step=-1))

m = Accumulator(fn=max, value=1)
play(ns, [], 0, m)
printf("[N={N}] max score = {m.value} @ {m.data}")
```

Solution: The maximum score for N=35 is 145.

One possible sequence is (17, 16, 15, 14, 13, 12, 10, 6, 9, 4, 2, 11, 3, 7, 5, 1).

Overall there are 75,600 different sequences that produce a maximum score.

2. Jim Randell 16 July 2015 at 10:31 am

This program is much faster. For the N=35 case it runs in 40ms.

It works by looking for a sequence that allows it to play all the numbers available. Clearly 1 must be played last, and we can’t play any number greater than N/2, so the only possible numbers that can be played before 1 are those from 2 to N/2. This program considers subsets of these numbers, in order of decreasing sum until it finds a playable sequence. And this is the maximum achievable total.

```from enigma import irange, printf

# can we find a way to play all the numbers in <ms>?
# ms - map numbers to remaining multiples
# t - count of remaining numbers in the game
# s - sequence played so far
def play(ms, t, s):

# are we done?
if not ms:
return (s if t > 0 else None)

# look at how many remaining multiples each number has
(n1s, ns) = ([], [])
for (k, v) in ms.items():
n = len(v)
if n == 0:
# numbers with no remaining multiples can never be played
return None
elif n == 1:
n1s.append(k)
else:
ns.append(k)
if n1s:
# numbers with only 1 remaining multiple can be played immediately
ns = n1s[0:1]

# play one of the remaining numbers
for n in ns:
ds = ms[n].union([n])
ms2 = dict()
for (k, v) in ms.items():
if k in ds: continue
ms2[k] = v.difference(ds)
# if this works return the sequence
r = play(ms2, t - len(ds), s + [n])
if r:
return r
else:
return None

# decompose <t> into a sequence of increasing numbers from <ns>
def decompose(t, ns, m=0):
if t == 0:
yield []
elif not(m > t):
for n in ns:
if m < n:
for r in decompose(t - n, ns, n):
yield [n] + r

# find sequences which give the best score
def solve(N):
# 1 must be played last, so we don't consider it

# map numbers from 2 to N/2 to higher multiples
ns = list(irange(2, N // 2))
ms0 = dict((n, set(irange(2 * n, N, step=n))) for n in ns)
t0 = sum(ns)

# consider increasing totals of deleted numbers
for t in irange(0, t0):
for ds in decompose(t, ns):
printf("[considering t={t} ds={ds}]")

# remove the deleted numbers
ms = dict((k, v) for (k, v) in ms0.items() if k not in ds)

# try to play all the remaining numbers
r = play(ms, N - 1, [])
if r:
# and then play 1
yield (t0 - t + 1, r + )

import sys
N = (35 if len(sys.argv) < 2 else int(sys.argv))

for (t, s) in solve(N):
printf("[N={N}] max score = {t} {s}")
break
```
3. Brian Gladman 17 July 2015 at 12:56 pm

This one was very interesting and I wonder if Stephen Ainley was being kind to puzzlers since 35 is the largest value for which a simple startegy of minimising the sum of the values removed by the Angel in each step works.

```from sys import argv
from collections import defaultdict

def play(moves, vals, N):
# have we finished?
if not vals:
# if so yield our moves
yield moves
else:
mx = max(vals)
# save the maximum value I can remove for which the
# Angel only removes one value
max_ci, max_cv = None, None
# consider my value, the Angel's values and the sum of
# the Angel's values - map each Angel's sum to my
# values and the Angel's values
d_sm = defaultdict(list)
# for each value I can remove
for i in (x for x in vals if x <= N // 2):
# collect the Angel's values
v = [x for x in range(2 * i, mx + 1, i) if x in vals]
if v:
# find the maximum value to remove for which the Angel
# only removes one value
if len(v) == 1:
if max_ci is None or i > max_ci:
max_ci, max_cv = i, [i] + v
# keep values indexed on whether the Angel removes values
# that I can remove and on the sum of the Angel's values
d_sm[(min(v) <= N // 2), sum(v)] += [(i, [i] + v)]
# first remove values for which the Angel only removes one value
if max_ci:
t = [x for x in vals if x not in max_cv]
yield from play(moves + [max_ci], t, N)
else:
# consider other values sorted to minimise the removal of values that
# that I could remove and then minimise the sum of the Angel's values
for sm, l_iv in sorted(d_sm.items()):
for i, v in l_iv:
yield from play(moves + [i], [x for x in vals if x not in v], N)

N = (35 if len(argv) < 2 else int(argv))
max_sm = None
# look for solutions with a maximum sum
for vals in play([], list(range(1, N + 1)), N):
sm = sum(vals)
if max_sm is None or sm > max_sm:
max_sm = sm
fs = 'N = {}, S = {} (of max {}) {}'
print(fs.format(N, sm, sum(range(1, N // 2 + 1)), vals))
```
4. arthurvause 21 July 2015 at 4:21 pm

Brute force recursion plus memoization:

```def memoize(fn):
stored_results = {}

def memoized(*args):
try:
return stored_results[args]
except KeyError:
result = stored_results[args] = fn(*args)
return result

return memoized

def play(remaining):
if len(remaining)<2:
return 0
best=0
largest = max(remaining)
for x in remaining:
if x <= largest/2:
nextrem = set(remaining)-set(m*x for m in xrange(1,largest/x+1))
if len(nextrem) < len(remaining) - 1:
res = x + play(tuple(sorted(nextrem)))
if res>best:
best=res
return best

play = memoize(play)

for N in xrange(6,40):
print "N =",N, "S = ", play(tuple(range(1,N+1)))

```

This site uses Akismet to reduce spam. Learn how your comment data is processed.