For which $n$ the first player has a strategy so that he wins no matter how the other player plays? The Question
From Junior O-level Tournament of the Towns paper, Fall 2020:

There are $n$ stones in a heap. Two players play the game by
alternatively taking either $1$ stone from the heap or a prime number
of stones which divides the current number of stones in the heap. The
player who takes the last stone wins. For which $n$ the first player has
a strategy so that he wins no matter how the other player plays?

My Understanding
Let player $A$ play first and player $B$ second. Also, let a heap with $n$ stones be an $n$-heap.
My initial observations:

*

*$A$ wins any $p$-heap for a prime number $p$.


*If an $n$-heap is
winning for $B$, then the $(n + 1)$-heap is winning for $A$, since
$A$ can remove $1$ stone and then use $B$'s winning strategy for the
$n$-heap (since for $n$-heap $A$ moves second).
I couldn't think of anything else so I tried finding a pattern with some examples.
\begin{array}{|c|c|c|c|}
\hline
n& \text{winner} \\ \hline
 1 &A \\ \hline
 2  & A\\ \hline
 3  & A\\ \hline
 4 & B\\ \hline
 5  & A\\ \hline
 6  & A\\ \hline
 7 & A\\ \hline
 8  & B\\ \hline
 9  & A\\ \hline
 10  & A\\ \hline
 11 & A\\ \hline
 12  & B\\ \hline
\end{array}
Since it seems $B$ wins exactly when $n = 4k$, I tried to prove this by induction on $k$.
Basis: the claim holds for $k \leq 3$ as shown in the examples.
Inductive hypothesis: Suppose that $B$ wins exactly when $n = 4k$ for arbitrary $k$.
Now I try to prove that $4k + 1$, $4k + 2$, $4k + 3$ have winning strategies for $A$ and that $4k + 4$ has a winning strategy for $B$.
$\textbf{(4k + 1)-heap:}$ $A$ wins by observation 2.
$\textbf{(4k + 2)-heap:}$ $4k + 2 = 2(2k + 1)$ which is even. $A$ can remove 2 stones to get a $4k$-heap which is winning for $A$ since now $B$ moves first.
Now I am stuck for the $(4k + 3)$-heap and $(4k + 4)$-heap. I don't want a complete solution, instead I just want a hint and some confirmation that this is a way to solve this problem. Also if you have an easier way, I would like a hint to discover it!
 A: Yes, you've found a good way of attacking the problem, and you've already got most of the way there.
Hints:

*

*The number of stones that can be removed from a pile of size $\ 4k+4\ $ can only be $\ 1,2\ $ or an odd prime.

*A number of the form $\ 4k+3\ $ must have at least one prime factor $\ p\equiv3\pmod{4}\ $.

A: I have used lonza leggiera's hints to complete my solution.
$4k + 3$ must have a prime factor $p \not = 2$ since $4k + 3$ is odd. Then either

*

*$p \equiv 0 \pmod{4}$, then $p = 4x$ which is not prime,

*$p \equiv 1 \pmod{4}$, then $p = 4x + 1$,

*$p \equiv 2 \pmod{4}$, then $p = 4x + 2$ which implies $p = 2$, but have already established $p \not = 2$,

*$p \equiv 3 \pmod{4}$, then $p = 4x + 3$.

If all prime factors satisfy $p \equiv 1 \pmod{4}$, then $4k + 3$ would satify $4k + 3 \equiv 1 \pmod{4}$ which is false. Hence at least one $p$ must satisfy $p \equiv 3 \pmod{4}$.
$A$ can then remove $4x + 3$ stones from the heap which means the heap has $4k + 3 - (4x + 3) = 4(k - x)$ stones. By the inductive hypothesis a $4(k - x)$-heap is winning for $B$. Hence the $(4k + 3)$-heap is winning for $A$.
Now for the $(4k + 4)$-heap. Again let $p$ be a prime factor of $4(k + 1)$, then either

*

*$p \equiv 0 \pmod{4}$, then $p = 4x$ which is not prime,

*$p \equiv 1 \pmod{4}$, then $p = 4x + 1$,

*$p \equiv 2 \pmod{4}$, then $p = 2$, or

*$p \equiv 3 \pmod{4}$, then $p = 4x + 3$.

If $p = 2$ then $A$ can reduce the heap to a $(4k + 2)$-heap which we have established is always winning for $A$. No good.
If $p = 4x + 1$, then $4k + 4 - (4x + 1) = 4(k - x) + 3$ which we have established is always winning for $A$. No good.
If $p = 4x + 3$, then $4k + 4 - (4x + 3) = 4(k - x) + 1$ which we have established is always winning for $A$, hence $(4k + 4)$-heap is always winning for $B$.
