Prime one heap Nim

I have been working on an interesting problem my lecturer mentioned recently. Prime Nim is a variant of the Nim game where you have a single pile with an arbitrary number $n\in \Bbb N+\{0\}$ of elements and players can take away a prime count of elements every round. Now I want to find a way to decide whether we can ensure victory in a given position (and the winning strategy, of course).

What I did so far:

$0$ and $1$ are clearly lost positions. On the contrary, any prime $n$ and $n+1$ are winning positions. For all other $n$ we can say that if there is no prime $p<n$ such that $n-p \notin \{n'|n'<n \land n' \text{ is lost}\}$, then $n$ is a losing position. The set of losing positions can be more formally expressed recursively based on previous such sets for smaller $n$. (In other words, this is an application of the very basic idea that a position form which we can make no move to a losing position is a losing position). All other positions are winning positions. Very simple and general.

Losing positions can be described as a sequence - http://oeis.org/A025043 (quite interestingly a subsequence of http://oeis.org/A093513). This uses the recursive nature of the problem.

An algorithm starting from the recursion edge case ($0$) and building up the sequence progressively can give us both the answer and the prospective winning strategy generated as a side-product in polynomial time.

My lecturer said the strategy-finding algorithm is probably optimal, but he also suggested there might be a simple formula to decide whether a given position can be won using an optimal strategy.

And I am stuck on it now. I guess the formula can't possibly be that simple, since it has to, in my opinion, include at least primality testing. I tried to determine a simple way to decide whether a number is in the sequence of losing positions, but I had no success so far. Basically, I always encounter the impenetrable problem of generating $n$th prime.

Any ideas on approaching this differently?

Solution 1:

Are you including $1$ as a reasonable move? If so, this game ("Prime Nim" created by CE Shannon) has been solved.

If not, the article above has Martin Gardner claiming an analysis of the strategy would be very difficult.

Solution 2:

The lack of additional info with the OEIS sequence may indicate that the strategy is not "simple". However, here is some heuristics:

From the OEIS data, 10000 numbers up to 67673 are losers, that is more that $\frac17$, and practically all of them are odd (I see only the exceptions $0, 10, 34, 100, 310$). Heuristically, this odd overweight will continue: Assume that there are $a$ odd and $b$ even loser numbers $x_i<N$ with $a\gg b$. Then if $N$ is even, it is a loser if none of the $a$ odd numbers $N-x_i$ is prime. This probability might be expected to be something like $$p_{\text{even}}=\left(1-\frac2{\ln N}\right)^a\approx e^{-\frac{2a}{\ln N}}.$$ On the other hand, if $N$ is odd, it is a loser only if $N-2$ is not a loser (which we will ignore) and none of the $b$ odd numbers $N-x_i$ is prime, which should be something like $$p_{\text{odd}}=\left(1-\frac2{\ln N}\right)^b\approx e^{-\frac{2b}{\ln N}}.$$ From the empirical data, it seems that $b$ is of size comparable to $\ln N$, hence $p_{\text{odd}}$ is of "reasonable" size (not really close to $0$), hence $a\approx p_{\text{odd}} N$ of size comparable to $N\gg\ln N$, which makes $p_{\text{even}}$ almost negligibly small.

I guess a similar argument might indicate that "most" loser numbers are not divisible by 3 or in fact any prime $p\ll N$ (maybe rather $p\ll \ln N$?).

But all this is far from giving a simple definite answer to whether a particulyr $N$ is a loser or a winner ...