**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]

### Like this:

Like Loading...

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.

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.

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.

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.

Brute force recursion plus memoization: