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

### Like this:

Like Loading...

*Related*

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.

Solution:The minimum score for N=30 is 103.One possible sequence is (13, 9, 15, 10, 8, 12, 14, 22).

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.

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.

Oh well! You’re right of course. Why didn’t I think of that?

Essentially the same approach.