Optimal strategy for choosing a number

In this game, you and your opponent takes turn to choose a number between 2 and 40. After a number is chosen, any number that shares a common divisor (excluding 1) with this number cannot be chosen. If a player has no number to choose from in his turn, he loses.

Suppose you get to choose a number first. What is your optimal strategy? What is your opponent optimal strategy? Who is guaranteed to win this game?

• Please edit to include your efforts. For clarity, I assume that you mean "a common divisor $>1$".
– lulu
Commented Sep 4, 2022 at 20:14
• Yes. I have updated the post. Commented Sep 4, 2022 at 20:20
• Well. If the first player choses $2\cdot 3\cdot 5 =30$ then the only numbers left will be the multiples of primes at least $7$. that are not divisible by any prime less than $7$. As $7^2 > 40$ that means only the primes are left. Picking a prime will only reduce by one number so no it's a matter of counting the number of primes and figuring who will pick the last prime. If it's the first player (i.e. there is an even number of primes) this is the best strategy for the first player. Otherwise this is the worst strategy for the first player if there is an odd number of primes Commented Sep 5, 2022 at 1:39

The prime numbers between $$2$$ and $$40$$ are precisely:

$$2,3,5,7,11,13,17,19,23,29,31,37$$

At the first step choose the number $$2$$. In this case your opponent will not be able to choose a number which is divisible by $$3$$ distinct primes, because such a number doesn't exist. (he can't choose $$30=2\cdot 3\cdot 5$$ anymore) He'll have to choose a number which is either divisible by $$1$$ odd prime or by $$2$$ odd primes.

Assume your opponent chose a number divisible by exactly one prime. Then in the next step you choose the product of the $$2$$ smallest remaining primes. (which will be either $$3$$ times something, or $$5\cdot 7=35$$) From now on numbers divisible by $$3$$ and $$5$$ are also forbidden, and so in the next turns both of you will just have to choose one of the remaining primes, no other options. The number of remaining primes is even, and this sequence of turns started from your opponent, so your opponent will be the first one who will run out of numbers. So you win.

Similarly, assume that in the second turn your opponent chose a number divisible by $$2$$ exactly distinct odd primes. One of these primes must be either $$3$$ or $$5$$. If the number he chose is divisible by both of them, you choose $$7$$ in the next step. Otherwise, choose the remaining prime between $$3$$ and $$5$$. Now again, from this point both of you will have to choose one of the remaining prime numbers (since you can't use numbers divisible by $$2$$, $$3$$, $$5$$ anymore), and you end up winning like in the previous case.

Beginner any even number times large prime, so 38, than second 3 * 13, then 5 * 7 , 1: 38 2:39 1:5 * 7=35 from now on you have only the remaining primes 11,17,23,29,31, 37 so you win The same if you start with 235 , so only the primes rest and by counting them you win also. but this depends of stopping at 40, stopping at 41 you loos with this strategy

First note choosing a number that is a multiple of a power of a prime will have the exact same effect as choosing a number that is a multiple of of any other power of the prime. (If you pick $$p^k$$ then $$p|p^k$$ so all multiples of $$p$$ are off the table). So there is no reason to pick a multiple of a power of a prime when picking a multiple of a prime will do.

The number that has the most prime factors will be $$2\cdot 3\cdot 5=30$$. ($$\frac {40}7 < 6$$ so any number that has a prime factor $$p \ge 7$$ can only equal $$kp$$ where $$k < 6$$ which has at most a single prime so $$30 = 2\cdot 3 \cdot 5$$ is the only number with with $$3$$ prime factors.)

If the first player picks $$2,3,5$$ this will rule out multiples of $$2,3,5$$ leaving only multiples of $$7,11,13,17,23,29,31,37$$. As $$7^2 > 40$$ this leaves only the $$8$$ remaining primes.

So if the first player plays $$30$$ then the only moves left will be for each player to pick a prime. As there will be exactly $$8$$ primes left this means there will be exactly $$8$$ more moves and player 2 will play the first, third, fifth and seventh of the remaining moves, and player 1 will play the eighth and last of the moves and be guaranteed a win.

There isn't any strategy better than one that assures a win.