# How does this game work? (Number game: subtract prime)

Problem

Alice and Bob play the following game.They choose a number N to play with.The runs are as follows :
1.Bob plays first and the two players alternate.
2.In his/her turn ,a player can subtract from $N$ any prime number less than $N$ or the number 1. The result thus obtained is the new $N$.
3.The person who cannot make a move in his/her turn loses the game.

Assuming both play optimally, who wins the game?

The answer is if $N \equiv 1 \pmod{4}$, then "Alice" will win, otherwise Bob. But I couldn't prove it mathematically correct. The way I obtain this answer is just bruteforce for some particular $N$. I noticed several rules but I just can't find a way to deduce from there. Here is what I have:

If $N = P + 1$, where $P$ is prime, then whoever take this turn will win.
If $N = 5$, then whoever takes this turn will lose.

The biggest problem I'm facing is primes because there is no general rule to generate one. I wonder could anyone shed me some light on this problem? Any suggestion would be greatly appreciated.

-
Why is Alice's name in quotation marks but Bob's isn't? – Qiaochu Yuan Jul 23 '12 at 2:11
Just emphasize he has only 1 chance compared to Bob (3). – Chan Jul 23 '12 at 2:14

It sounds like the key point is that you can subtract $1$, $2$, or $3$, but nothing equivalent to $0$ mod 4. (In other words, the primes are a distraction.)
Thus, if $N \not\equiv 1$ (mod 4), Bob can subtract either $1$, $2$, or $3$ from $N$ so that $N' \equiv 1$ (mod 4), where $N'$ is the new $N$. However, if $N \equiv 1$ (mod 4), then Bob is forced to make $N' \not\equiv 1$, and Alice can reply by making the next number equivalent to 1 (mod 4).
(I'm assuming that the endgame is such that if you start with $N = 1$, you lose.)
The Sprague-Grundy theorem tells us that $N=4n+k$ is a nim-heap of $k-1 \pmod 4$. You are right that all primes above $3$ don't matter in this game. – Ross Millikan Jul 23 '12 at 2:37