Help with a prime number spiral which turns 90 degrees at each prime

Question

I awoke with the following puzzle that I would like to investigate, but the answer may require some programming (it may not either). I have asked on the meta site and believe the question to be suitable and hopefully interesting for the community.

I will try to explain the puzzle as best I can then detail the questions I am interested in after.

Imagine squared paper. In one square write the number $1.$ Continue to write numbers from left to right (as normal) until you reach a prime. The next number after a prime should be written in the square located $90$ degrees clockwise to the last. You then continue writing numbers in that direction. This procedure should be continued indefinitely.

Here is a sample of the grid:

$$\begin{array}{} 7&8&9&10&11&40&41 \\6&1&2&&12&&42\\5&4&3&14&13&44&43\\&&34&&26\\&&33&&27\\&&32&&28\\&&31&30&29\end{array}$$

Note that the square containing 3 also contains 15 (I couldn't put it in without confusing the diagram. In fact some squares contain multiple entries. I would have liked to see an expanded version of the diagram. I originally thought of shading squares that contain at least one number.

Questions Does the square surrounded by $2,3,9,10,11,12,13,14$ ever get shaded? If so, will the whole grid ever be shaded? Is there a maximum number of times a square can be visited? I have got to 4 times but it is easy to make mistakes by hand. Are there any repeated patterns in the gaps? I have other ideas but this is enough for now as I have genuinely no idea how easy or difficult this problem is.

Please forgive me for not taking it any further as it is so easy to make mistakes. I hope this is interesting for the community and look forwards to any results. Thanks.

Any questions I'll do my best to clarify.

Side note: I observed that initially at least the pattern likes to cling to itself but I suspect it doesn't later on.

Answer 1

I'll answer your question about the gap between $2$ and $12$. I'll expand this answer if I find out more things later on.

Note that the gap is in a column that contains only even numbers, so we'll never make a turn at this column. Similarly, the only odd number that contains the row is $1$, and this happens because $2$ is the only even, prime number. So there is no way we can start writing numbers in the same row or column where the gap is, so the gap will never be shaded.

The square where we write the $3$ is important. From this point and later on, we will turn only in squares with an odd number. We can call this cell $(0,0)$, and assign coordinates to other cells accordingly; for example, $14$ is in $(1,0)$ and $2$ is at $(0,1)$.

Now we see that the cells with two even coordinates contain odd numbers. Cells with an even coordinate and the other odd contain even numbers and cells with odd coordinates remain empty, except the starting point.

There are arbitrarily gaps between consecutive numbers, so I think that the scheme will grow up, probably, in the four directions approximately at the same rate. But facts like this seems very hard to show.

Answer 2

You already have an answer, so this should be a comment, but it contains images, the pattern for $n$ up to $1000$ and $10\,000$. The red point, if you can see it, is the starting point.

For $n=10\,000$ there are four squares visited $7$ times.

The images were generated with the following Mathematica code: I used the following Mathematica code:

(*Generate the points*)
m = {{0, 1}, {-1, 0}};(*rotation matrix*)
step = {1, 0};  
last = {0, 0};  
points = {last};  
nmax = 1000;  
Do[
 If[PrimeQ[n], step = m.step];  
 last = last + step;  
 AppendTo[points, last],  
 {n, max}]  
(*Show the points*)
Graphics[{
Point[points],
Red, PointSize[Large], Point[{0, 0}],(*starting point*)
Blue,Point[Last[points]](*last point*)
}]

Answer 3

Just for visual amusement, here are more pictures. In all cases, initial point is a large red dot.

Primes up to $10^5$:

Primes up to $10^6$:

Primes up to $10^6$ starting gaps of length $>6$:

Primes up to $10^7$ starting gaps of length $>10$:

Primes up to $10^8$ starting gaps of length $>60$:

For anyone interested, all the images were generated using Sage and variations of the following code:

d = 1
p = 0
M = []
prim = prime_range(10^8)
diff = []
for i in range(len(prim)-1):
    diff.append(prim[i+1]-prim[i])
for k in diff:
    if k>60:
        M.append(p)
    d = -d*I
    p = p+k*d
save(list_plot(M,aspect_ratio = 1,axes = false,pointsize = 1,figsize = 20)+point((0,0),color = 'red'),'8s.png')

Answer 4

As Karl notes, there are instances of overlaps for some numbers in this sequence. I have thus elected to display a three-dimensional representation of the path, using $n$ stacked cubes to represent the $n$ times a certain point in the grid was visited:

$n=10^3$

$n=10^4$

$n=10^5$

---

For those who want to try it out in Mathematica:

With[{n = 1*^5}, 
     Graphics3D[{EdgeForm[], 
                 Flatten[Table[Cuboid[Append[# - 1/2, k - 1],
                                      Append[# + 1/2, k]], {k, #2}] & @@@ 
                 Tally[AnglePath[-π Boole[PrimeQ[Range[n - 1]]]/2]]]}, 
                Boxed -> False]]

(If your version of Mathematica does not have AnglePath[], use the function in this answer instead.)

Answer 5

Inspired by the outstanding answers I had the idea of building part of the pattern with Legos. I hope it is OK to add for interest.

Each colour is for each layer. Red is the number one and blue for the first layer.

Answer 6

Random thought: you can split the prime gap function into 'even' and 'odd' parts by index; these correspond to the length of vertical and horizontal lines in the graph. The dimensions of the overall graph as $n \to \infty$ are determined by whether the sum of their alternating elements (with every other element multiplied by -1) diverges. I know that the maximum value of the prime gap function is unbounded as $n \to \infty$, but I don't know whether the 'even' and 'odd' parts of it have been similarly characterized.

Answer 7

I seem to remember that a two-dimensional random walk returns to the origin with probability 1 if you just walk for long enough time. As a consequence, each point in the plane will be visited infinitely many times by a two-dimensional random walk. (See http://mathworld.wolfram.com/RandomWalk2-Dimensional.html).

I would think that the same thing might happen if you replaced prime numbers with random odd integers with a distribution similar to that of prime numbers - basically, four consecutive prime numbers send you not to a random neighbouring point, but to a random point nearby. The problem is that the gaps between primes grow. I couldn't say if they grow fast enough to stop the random walk from returning to the origin.

And then of course there is the problem that we don't have a random walk but one based on prime numbers. Prime numbers behave almost but not quite like random numbers. There is the possibility that the gaps between primes number 4n and 4n+1, 4n+1 and 4n+2, 4n+2 and 4n+3, 4n+3 and 4n+4 behave in a non-random way, so that this figure would go in the long term into some specific direction.

So apart from the fact that three quarters of the grid will never be touched, nothing would surprise me. I would think that if every cell (apart from the proven untouchable ones) gets visited, then every of those cells will be visited infinitely many times. I would also think that you have to wait for a very, very lone time for repeat visits to the say the point where you wrote down the number 3 (the point with the number 1 will never be visited again) once you moved away from it for a bit.

I also don't think that occasional large gaps between primes matter much.

Answer 8

Consider a similar process for random numbers distributed similarly to the primes (which is much easier to analyze). The density around $n$ is $1\over \ln n$, so the behaviour is similar to if it went straight for approximately $\ln n$ steps, then randomly changed direction, so letting $a(n)$ be the position after step n (considered as a random variable), $$ \frac {\mathrm d} {{\mathrm d}n} \mathbb E(a(n)^2) \propto \ln n$$ (with many approximations) therefore $$ \mathbb E(a(n)^2) \propto n \ln n$$ As the size of the area in which $a(n)$ is likely to be is proportional to $\mathbb E(\|{a(n)}\|)^2 = \mathbb E(a(n)^2) \gg n$ (for sufficiently large n), the probability that any point will ever be visited tends to 0 as the point gets farther away from the staring point. This accounts for the visual differences from ordinary random walks in the images in other answers, so no strange correlations between the primes are implied.

Answer 9

No, the gap in the square you described will never be filled. This is because every prime gap after the first is even, as all primes after 2 are odd. The only hole in your picture that might be filled is the one between 27 and 33.

Answer 10

I was curious about the behavior of this with an angle other than $-90^\circ$, so I created an animation, shown below, of all the integer degree angles in $[1^\circ, 300^\circ]$ (would go to $359^\circ$ but the gif maker I used only allowed up to 300 images):

Note: the above may be hard to see, depending on monitor and proximity of face to said monitor. Also, it made from jpegs, so the quality is suboptimal.

Also see an album showing the results of all angles in $[1^\circ, 359^\circ)$, with an angle increment of $\frac{1}{16}$ (instead of $1$): https://www.flickr.com/gp/146544238@N02/u3HA72

Note: Careful of the order of the images in the album. They're in alphabetical order, not numerical order. You'll see.

It exhibits curiously (or maybe very unsurprisingly considering we're dealing with primes) chaotic behavior (perhaps a very small angle increment is needed to have continuity), but a few patterns can be observed...

• Angles near $0^\circ$ produce very 'loopy' results, e.g. $\Delta\theta = \frac{19^\circ}{16}=1.1875^\circ\approx 0^\circ$: (This one is also kinda hard to see)

• Certain angles also produce results that have circular shapes in them, but these are more 'spiky', producing lots of incomplete circles, e.g. $\Delta\theta = \frac{2803^\circ}{16}=175.1875^\circ$: Note: $\Delta\theta\approx 180^\circ$. Not sure if this is the reason for the behavior, but I imagine that it is.

$\Delta\theta=\frac{2262^\circ}{16}=141.375^\circ$ was also curious, because it clearly had to go out one way, come back, and go out the other way:

Answer 11

Here's some Python code that plots this prime spiral path for primes less than num, with the grid cell colour determined by the number of times the path has visited it. Unvisited cells are black, visited cells are coloured by cycling through {red, yellow, green, cyan, blue, magenta}. Thus cells that have been visited once are red, cells that have been visited twice are yellow, thrice-visited cells are green, etc. When we get to the end of the colour list we go back to red, so a cell that's been visited 7, 13, ... times is red.

The origin cell (i.e., the cell containing 1) is re-coloured white at the end of the plotting process, but it's not easy to find when num is large.

This code uses the 3rd-party modules Numpy and Pillow to do the plotting. It was written for Python 3, but it will still run correctly on Python 2.

#!/usr/bin/env python3

''' New prime spiral by Karl

    Saves path as a PNG

    See http://math.stackexchange.com/q/2072308/207316

    Written by PM 2Ring 2017.1.1
'''

from collections import defaultdict
from itertools import cycle, islice
from operator import itemgetter

import numpy as np
from PIL import Image

def primes_bool(n):
    ''' Return a boolean list of all primes 0 <= p < n '''
    s = [True] * n
    s[:2] = [False] * 2 
    for i in range(2, int(n**0.5) + 1):
        if s[i]:
            s[i*i : n : i] = [False] * (1 + (n - 1)//i - i)
    return s

def vadd(u, v):
    return u[0] + v[0], u[1] + v[1]

step = cycle([(1, 0), (0, 1), (-1, 0), (0, -1)])
st = next(step)

current = (0, 0)
points = defaultdict(int)
points[current] = 1

# perform steps
num = 1000000
for v in islice(primes_bool(num), 2, None):
    current = vadd(current, st)
    points[current] += 1
    if v:
        st = next(step)

# find bounds, adding a border of 1
keys = points.keys()
ig0, ig1 = itemgetter(0), itemgetter(1)
lox = min(keys, key=ig0)[0] - 1
hix = max(keys, key=ig0)[0] + 1
loy = min(keys, key=ig1)[1] - 1
hiy = max(keys, key=ig1)[1] + 1
width = 1 + hix - lox
height = 1 + hiy - loy

print('x:', lox, hix, width)
print('y:', loy, hiy, height)
print('max crossings:', max(points.values()))

# convert to image grid
#KRYGCBMW
palette = np.array([
    [0, 0, 0],
    [255, 0, 0],
    [255, 255, 0],
    [0, 255, 0],
    [0, 255, 255],
    [0, 0, 255],
    [255, 0, 255],
    [255, 255, 255],
], dtype='uint8')

grid = np.zeros((height, width, 3), dtype='uint8')
for (x, y), v in points.items():
    grid[y - loy, x - lox] = palette[(v - 1) % 6 + 1]

del points
# reset location of 1, i.e.,(0, 0) to white
grid[-loy, -lox] = palette[7]

img = Image.fromarray(grid)
#img.show()
img.save('primespiral.png')

Uncomment the #img.show() line to display the image at full size with an external viewer. This normally uses display from the ImageMagick package on *nix systems; on Windows, it saves the image to a temporary BMP file, and allegedly uses the standard BMP display utility to show it.

Here's the output for num = 1000000:

And here's the output for num = 10000000, scaled by a factor of 1/16:

---

If you'd like to see when the current record number of visits is reached, replace the main path generating loop with this code:

# perform steps
num = 10000000
maxvisits = 1
for i, v in enumerate(islice(primes_bool(num), 2, None), 2):
    current = vadd(current, st)
    points[current] += 1
    if points[current] > maxvisits:
        maxvisits = points[current]
        print('{} visits at {}'.format(maxvisits, i)) 
    if v:
        st = next(step)

Here's what it prints for num = 10000000

2 visits at 15
3 visits at 35
4 visits at 47
5 visits at 81
6 visits at 7087
7 visits at 7399
8 visits at 19865
9 visits at 19913
10 visits at 24087
11 visits at 24279
12 visits at 408257
13 visits at 409303
14 visits at 2042205
15 visits at 5262017
16 visits at 5262089
17 visits at 6189393
18 visits at 6435851
19 visits at 6435983

---

Here's a version that uses turtle graphics, so you can watch the path being drawn. The turtle module is included in most modern Python installations.

#!/usr/bin/env python3

''' New prime spiral by Karl

    See http://math.stackexchange.com/q/2072308/207316
    https://oeis.org/A268463

    Written by PM 2Ring 2017.1.1
    turtle version 2017.1.3
'''

import sys
import turtle

from collections import defaultdict
from itertools import islice
from operator import itemgetter

def primes_bool(n):
    ''' Return a boolean list of all primes 0 <= p < n '''
    s = [True] * n
    s[:2] = [False] * 2 
    for i in range(2, int(n**0.5) + 1):
        if s[i]:
            s[i*i : n : i] = [False] * (1 + (n - 1)//i - i)
    return s

def vadd(u, v):
    return u[0] + v[0], u[1] + v[1]

steps = [(1, 0), (0, 1), (-1, 0), (0, -1)]
step_index = 0
st = steps[step_index]

current = (0, 0)
points = defaultdict(int)
points[current] = 1

# turtle stuff
palette = [
    'black',
    'red',
    'yellow',
    'green',
    'cyan',
    'blue',
    'magenta',
    'white',
]

win_width, win_height = 3000, 3000
pensize = 3

turtle.setup()
turtle.screensize(win_width, win_height, palette[0])

t = turtle.Turtle()
t.hideturtle()
t.speed(0)
t.pensize(pensize)
t.color(palette[-1])
t.forward(pensize)

# perform steps
num = 100000
maxvisits = 1
for i, v in enumerate(islice(primes_bool(num), 2, None), 2):
    print('\r {} '.format(i), end='', file=sys.stderr)
    current = vadd(current, st)
    points[current] += 1
    pc = points[current]
    if pc > maxvisits:
        maxvisits = pc
        print('{} visits at {}'.format(maxvisits, i)) 
    if v:
        step_index = (step_index + 1) % 4
        st = steps[step_index]
        t.right(90)

    t.color(palette[(pc - 1) % 6 + 1])
    t.forward(pensize)

turtle.done()
print()

To change the scale of the drawing just change the pensize variable to another positive integer. Note that the pen is rounded, so the path will have noticeable rounded corners for pensize > 3; this may or may not be desirable. :)

---

You can easily modify this script to draw some alternate prime paths. All primes > 3 are of the form $6n\pm 1$. So we can turn right if prime $i \mod 6 = 1$, or turn left for the other primes.

To do that change the code in the if v: block to

if v:
    dx = 1 if i % 6 == 1 else -1
    step_index = (step_index + dx) % 4
    st = steps[step_index]
    t.right(90 * dx)

All primes > 2 are of the form $4n\pm 1$. This is perhaps more important than the $6n\pm 1$ distinction since primes of the form $4n-1$ are also prime in the Gaussian integers; 2 and primes of the form $4n+1$ can be written as the sum of two squares and can thus be factorised in the Gaussian integers.

So we can make the path turn right for $4n+1$ primes and left for the other primes by changing the modulus in the dx assignment:

    dx = 1 if i % 4 == 1 else -1

---

Here's a live version that runs on the SageMathCell server. If you make num too high the server will abort the job, but you should be able to go up to 10000000 or so.

Answer 12

As @ajotatxe explained, the point between $2$ and $12$ can never be crossed, but as regards your grid, the first time the point between $33$ and $27$ is reached at $6\ 716\ 606$:

Position[AnglePath[-Pi/2 Boole[PrimeQ[Range[10^7]]]],{2,-3}][[1, 1]]

With[{a = AnglePath[-Pi/2 Boole@PrimeQ@Range@6716606]}, Graphics[{Black, [email protected], Point@Last@a, Blue, Line@a, Thick, Red, Line@Take[a, 45]}, ImageSize -> 5000]]

Answer 13

As a point of interest, we over at PPCG decided to try some more diverse renderings of this walk.

Progressively Changing Angles Dynamically Drawn

Smoothly increasing angles

Provided by @Flawr

And my personal favourite,

Isographic 3D Pipes

If you didn't spot it, the pipes are really just the 120 degree turn graph, with some visual trickery.

Answer 14

This question has nerd sniped me yet again, five years later, resulting in an online tool for visualizing these spirals.

The below pictures show primes in $[1, 100000]$ with turn angles of $90^\circ$ then $91^\circ$. The color signifies progress along the path, so that overlapping paths can be differentiated.

$90^\circ$ turn.

$91^\circ$ turn. One degree makes a big difference!

If you're curious about how it works, or want to leave feedback, see the github.