# A prime number random walk

This question came to my mind thanks to this question which I found really interesting (and beautiful! Like the mathematician Philippe Caldero said in his book Histoires Hédonistes de Groupes et de Géométries (roughly translated) "Let us stop for a moment to contemplate the beauty of mathematics, that is after all the point of figures".).

It is also related to this other question.

The idea is to perform a walk following the following rules:

• Initialisation: You start on the point $(0,0)$ which correspond to the integer $n=0$, and you will walk from one point of $\mathbb Z^2$ to another. You start by walking on the right.

• Each horizontal step you take increases the integer $n$ by $1$.

• When $n$ is equal to a prime number, you take one step up, and you change the direction you were going to (if you were walking from left to right you will walk from right to left, and reciprocally).

To illustrate the rules, a drawing will perhaps be more explicit:

$$\begin{matrix} & 7 & 8 & 9 & 10\\ & 7 & 6 & 5 \\ & 3 & 4 & 5 \\ & 3 & 2 & \\ 0&1&2& & \end{matrix}$$

Or with blue lines:

Well now nothing stops us from going a little further, which we will do until $n=100$, and then until $n=1\,000$. It seems that the walk is almost always on the right side of the $y$-axis. Though the walk is crossing the axis a few times.

Let us walk until $n=10\,000$. Then we realise that we have completely changing the side of the axis we were walking on.

Which rises some questions:

• Will we cross the $y$-axis infinitely many times?

• Will we be walking as much on each side of the plane? In the sense that if we denote by $L_n$ the set of integers less or equals to $n$ on the left side of the plane and $R_n$ the set of integers less or equals to $n$ on the left side of the plane:

$$\lim_{n\to\infty} \frac {L_n}n=\lim_{n\to\infty} \frac {R_n}n=\frac 12.$$

• Will we walk out of any fixed vertical band centred on the $y$-axis?

Though any other result, or drawing (I did not succeed in drawing it for $n=10^5$), references about this walk would be of great interest.

• Last question is easy: yes. There are infinitely many primes. Dec 28, 2016 at 14:43
• @ajotatxe Yes, but this does not imply that we will get as far off the $y$-axis as we want because we are constantly changing direction. Dec 28, 2016 at 14:45
• Perhaps I didn't understand the question. Whenever $n$ is prime, we go up one unit and change direction. Since there are infinitely many primes, we go up infinitely many times. Dec 28, 2016 at 14:47
• @ajotatxe Yes, but going up does not take us away of the $y$-axis. Going left or right does. Dec 28, 2016 at 14:50
• If the question doesn't get a satisfactory answer here before the bounty expires, I'd recommend posting it to mathoverflow (making sure to link each post to the other). Jan 21, 2017 at 23:15

Will we walk arbitrarily far off the y-axis?

Yes, because there are arbitrarily long gaps between consecutive primes.

For every gap $n\in\mathbb{N}$, there is a sequence of $n-1$ consecutive numbers, none of which is prime:

$$n!+2,n!+3,\dots,n!+n$$

In other words, there is no finite bound on the gap between two consecutive primes.

Hence there is no limit as to how far off the y-axis your illustration goes...

• Indeed, the path cannot remain in a fixed size vertical band (in particular not in one centred at the $y$-axis. But you cannot tell whether ones goes off without bound to the left or to the right, or to both (which would imply crossing the $y$-axis infinitely often). Dec 28, 2016 at 15:00
• Woah, this is really cool. Great proof. Dec 29, 2016 at 19:32
• @MarcvanLeeuwen You are not negate prove given by barakmanos, aren't you? Jan 15, 2017 at 14:43
• "Indeed" means I agree. Jan 15, 2017 at 21:18

Some more graphs:

Up to $n=100000 = 10^5$: Up to $n=1000000 = 10^6$: Up to $n=10000000 = 10^7$: Up to $n=100000000 = 10^8$: And finally, up to $n=1000000000 = 10^9$: Will we cross the $y$-axis infinitely many times?

Firstly, Let's lay out the assumptions related to this.

• There are infinitely many primes.
• The spacing between primes is Arbitrary.

Given that both of these are true, the answer is Yes for any point along the $x$ axis.

Given infinite time, and an infinite random walk left or right, any walk will eventually pass through any point.

EDIT:

Any walk which exists in a single axis, in this case, the $x$, will pass through any value of $x$ an infinite amount of times, given infinite time.

Assume the target $x=0$, where the walk is currently at $x=1$. The walk, has a $1/2$ chance to either, cross the $x=0$ within the next move.

But we need the chance that $x$ will ever cross $0$ again.

The percent chance for $x=2$ to reach $0$, within two turns, is $1/4$, which means that $x=1$ has, at least, a $1/2+1/4=3/4$ chance to successfully cross the $0$ in 3 turns.

As such, the chances that $x$ will be $0$ in exactly $x$ turns are $1/2^x$

This means that $x\to\inf$, $p\to0$ where $p$ is the chance that $x$ will equal $0$ in exactly $x$ moves.

$x$ cannot be $\inf$, so $p>0$. There is always a chance, and there are infinite tries. Even after failing,there's a 50% chance that your odds increase.

Thus, a Random Walk, given infinite time, will cross $x=0$, infinite times.

This Applies to Prime Gaps.

In this case, the Prime Gaps are just a random walk which changes direction at a Prime.

Below is a diagram showing how the Prime Walk (Blue) and Random Walk (Red) compare for values up to $y=500$. Even though the Prime walk is strongly biased towards smaller numbers, there is no known maximum distance between prime gaps which means there is a chance, albeit an even smaller than normal, yet a non-zero chance that the next prime is far enough away to $x\le0$.

Of course, this proof is destroyed if Primes are either Proven non-infinite, against current proofs, or predictable.

• I am not convinced, since even if gaps are huge, you could have walked far off the $y$-axis, so you will not necessarily cross it with a huge gap. Jan 23, 2017 at 8:28
• @E.Joseph I hope to have explained my reasoning well enough. Otherwise, I'm sorry, I'm still fairly new at this. Jan 24, 2017 at 1:51
• Nice explanations! I am not convinced this is a rigorous proof, because we don't know that for the prime walk going left or right is equiprobable. Nice illustration though, I love it! Jan 24, 2017 at 12:26