31
$\begingroup$

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$:

enter image description here

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$:

enter image description here

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.

enter image description here

enter image description here

enter image description here

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?

Improve this question
$\endgroup$
  • 6
    $\begingroup$ This is very exciting! Looking forwards to the results. $\endgroup$ – Karl Dec 29 '16 at 19:30
  • 2
    $\begingroup$ In regards to your question in how to formalize your argument for the $n$ even case. If instead you consider all possible paths where you can change direction (either left, right or forward) after two steps, it is not hard to prove rigorously that if $n$ is even then you get a "grid" of all possible steps that misses every second block. But the path defined by the primes is contained in such a subset of the grid after you hit $3$. Hence we get $p(n)=\infty$ in this case. $\endgroup$ – Leon Sot Jan 14 '17 at 11:58
  • 1
    $\begingroup$ I only provided a proof for the $n=2k$ case. It seems to me that the full conjecture implies something non trivial about the gaps between primes, so I think a proof for the full conjecture will be difficult. At least far beyond my grasp of number theory. $\endgroup$ – Leon Sot Jan 16 '17 at 0:44
  • 1
    $\begingroup$ @CarlosToscano-Ochoa I don't really know how to do that, but feel free to do so and to post it as an answer if you try it! $\endgroup$ – E. Joseph Mar 8 '17 at 21:32
  • 1
    $\begingroup$ Roughly eyeballing it, $p(n)$ looks like it grows in the neighborhood of $2x^2log(n)$. It would be interesting to overlay a few such graphs (for example $2x^2log(n), 2.2x^2log(n), 2x^2(log(n) + log(log(n))$) on top of your graphs. $\endgroup$ – Χpẘ Mar 9 '17 at 23:53
3
$\begingroup$

your conjecture is True assuming that : there is a $k$ sequence of consecutive primes that the difference between every two consecutive prime of that sequence produces the sequence $\{n-1,n-1,n-1,n-2,n-2,n-3,n-3,.....,2,2,1,1\} \mod n$ such that $n-1$ element is repeated $3$ time and all the other elements are repeated $2$ times in descending order.

which is $2n-1$ elements or $2n$ consecutive prime.

to explain what i mean, lets take $n=3$ so i am looking for $2*3= 6$ consecutive prime numbers that their consecutive difference produces $\{2,2,2,1,1\} \mod 3$

now if i assume that this will happen for all odd $n$ numbers, then no matter at what cell in the square i was standing or in what direction i was going, i am guaranteed to travel across every cell in the $n*n$ square.

note : as i wrote in the comments, i think that the assumption could be proved by Green-Tao theorem (i am not sure of that).

i hope this give you some idea on how to tackle this problem

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.