I don't have a complete strategy but there are some things to notice. I made a picture with 1 to 25 in a circle and connected legal moves.
If you pick 1 you will lose because your opponent will pick 13, 17, 19, or 23 (these are winning positions  the one who picks one of these has won.)
Therefore if you can pick 11 you will win because you could only choose that after 22 so your opponent would be forced to choose 1.
Therefore 22 is a losing position.
(This doesn't make 2 a winning position, since 22 is not forced from 2 unless all else is used.)
On my graph 11 is a node with only two edges.
Likewise 25 is a winning position which comes from 5, a losing position.
So there are 17 positions left not labeled as winning or losing.
As the game progresses edges can be removed as nodes are used up. Any node with two remaining edges becomes a winning position as using one of them will force the opponent to choose 1.
For example 9 has three edges (connecting to 1, 3, 18) if player A chooses 18 and B chooses 3 the edge from 9 to 18 is removed. 9 becomes a winning position and A chooses it to win. (B must choose 1, A picks one of the large primes.)
(18 is not necessarily a winning position because B could have chosen 9 instead of 3 then A would pick 3 not 1.)
The point is that winning positions become more and more numerous until eventually someone loses by being forced to give the opponent the opportunity to pick one.

Posted by Jer
on 20131115 16:09:10 