12
$\begingroup$

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 such that $n-p \notin \{n'|n', 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?

  • 2
    Every time I find a losing position $l$, $p+l$ is a winning position for all prime $p$ (play $p$).2012-10-31

2 Answers 2