This question is following two similar questions that you can find here and here.
The idea is to walk on a square of length $n\times n$, following some rules. We will identify the opposite sides.
Formally, the square with the opposite sides identified can be modelled by $(\mathbb Z/n\mathbb Z)^2$.
We will walk following the following rules:
We start on the bottom left case, facing north. This correspond to the number $k=1$.
Each time we take a step, we increase $k$ by $1$, and if $k$ happens to be a prime number, we turn $90$ degrees right.
We wall $p(n)$ the smallest number of steps we need to walk on every case of the square.
We will draw the walk for $n=3$ to illustrate the rules, and to be convince that $p(3)=9$:
I am interested in the sequence $p$.
What I think is true is the following result.
Conjecture. We have $p(n)<\infty \iff (n=2 \text{ or }n\text{ is odd})$.
I have computed the first values of $p(n)$ using SageMath:
$$\begin{matrix} n &1 &2 &3 &4 &5 &6 &7 &8 &9 &10\\ p(n) &1 &4 &9 &? &90 &? &256 &? &364 &? \end{matrix}$$
I convinced myself that $p(n)=\infty$ if $n$ was an even number greater than $3$ thanks to the following drawing for $n=4$:
The green circles represent the case that are potentially attainable. The two blue rectangles highlights the fact that only even numbers will be able to go there, which convinced me that some case will not be attainable.
However this is not very formal, so if you know a way to formalise this proof please let me know.
Plus, I don't know how to prove that $p(n)<\infty$ if $n$ is odd. May be this is even false.
If you want to know what $p(n)$ looks like for $n$ odd in $\{1,\ldots, 100\}$,$\{1,\ldots, 200\}$ and $\{1,\ldots, 400\}$ respectively, here are three pictures of the sequence.
My questions are the following:
How could I begin to prove (or disprove) the conjecture? Do you have any references?
What would be the growth rate of $p$? Can we find an equivalent of $p(2n+1)$? (but that would be too beautiful, so the following question is easier but implied by this)
Is there two interesting sequences $\alpha$ and $\beta$ such that for all $n$, $\alpha(n)\leqslant p(n)\leqslant \beta(n)$?
What else can we say about this sequence?