When is the "Taxman Game" winnable?

Question

I recently came across the "Taxman Game" the rules are in the link, but I'll repeat them here:

We start with a pile of integers, from 1 to some number that you choose [$n$]. You take one, and I get all the others that divide it evenly. We repeat until there's nothing left. BUT (big but!) I have to get something on each turn. So when none of the numbers in the list have any divisors that have not been taken, I take them all. Your score is the sum of all the numbers you took, while my score is the sum of all the numbers I took.

The 'you' and 'I' is a bit confusing, there is only one player here - the 'you' - as the 'taxman' ('I') side is entirely deterministic.

The question I have is this: for what $n$ is the game winnable? I think that it is winnable for all $n>3$ but I'm not sure how to go about proving this. At $n=3$, the best strategy is a draw (pick 3, taxman get 1 and 2), while for $n=1$, the player has no winning move so the lowest bound on winnable $n$ must be $n>3$ but is there a higher $n$ that is unwinnable?

I'd also be interested in whether there is a 'best' strategy guaranteed to give a win where it is possible and the largest possible winning margin when doing so.

Answer 1

Some observations on the game:

• The $1$ will always go to P2 on turn 1
• $P1$ can pick only one of the primes, so should pick the largest on turn 1 (by the Bertrand-Chebyshev theorem we know that for $n \ge 4$ there is always a prime exceeding $n/2$, so the largest prime $\le n$ has no multiples in $\{1,2,3,...,n\}$)
• all other primes will go to $P2$
• picking a power of $2,3,5,...$ will result in the elimination of all lower powers of $2,3,5,...$
• it never makes sense to pick the second largest power of $2$
• if the only selectable numbers left are powers of a prime $p$, it is best to pick in alternating powers of $p$ ending at the highest power, for example, choosing $4,16,64$ for $p=2, 64 \le n < 128$
• if $n = p$ where $p \ge 5$ is prime, there is a largest prime $q \in \{1,2,3,...,p-1\}$ such that $\dfrac{p+1}{2} < q < p$. Then if P1's best score differential for $n=p-1$ is $S(p-1)$ we have $S(p) = S(p-1) + p - 2q$ (since the only action P1 should change is his choice of largest prime) and also $S(p-1) - p < S(p) < S(p-1) - 1$
• if $n$ is not prime, then $S(n) = S(n-1) - n$ unless P1 chooses $n$ at some point in the game. If P1 can obtain a better score by choosing $n$ he should; otherwise, he should not.

Answer 2

Robert Moniot's "greedy heuristic" seems like a good candidate for a winning strategy. He computed the optimal strategy for all n up to 49, but he did not find a simple rule to describe it for arbitrary n.

There's an interesting discussion thread on /r/mathriddles about the taxman game. No proofs of optimality, but I thought I'd share the link since there's a number of suggested strategies on there.