Voronoi Diagrams of the Ulam Prime Spiral


When exploring the Voronoi Diagram of the Ulam Prime Spiral, I noticed that when the length of the perimeter is an integer, the cell itself is usually a rectangle. I figured that would not always be the case, and decided to find a prime number whose voronoi cell had a different shape, while still being integral in length. If you aren't sure what all this means, perhaps the explanation on the main page on this topic will help.

This page describes how I looked for such a prime number. If you like, you can skip the explanation and jump straight to the result.

The first step in the hunt was to decide what configuration to look for. I chose to hunt for a voronoi cell in the shape of a 3-4-5 right triangle. This would have integral perimeter. Given the special points (x,y), (x-2,y), (x,y-1), and (x+4,x+3), the voronoi cell of (0,0) is a triangle with the correct shape. Unfortunately, in the Ulam prime spiral, odd primes always fall on vertices whose coordinates are both even or both odd. There's no way the numbers (x,y), (x-2,y), (x,y-1), and (x+4,x+3) could all be prime.

That's ok. I decided to just scale everything by a factor of 2 - so I wanted to find an x and a y so that (x,y), (x-4,y), (x,y-2) and (x+8,y+6) are all coordinates of prime numbers. Actually, that's very easy, but unfortunately it's not enough to give the shape I wanted. For example, if the number at (x+1,y+1) is also prime, then I won't have my nice 3-4-5 triangle.

Time for some formulae. If x is bigger than |y|, then the number on cell (x,y) is (2x-1)2+x+y. So I want to find (x,y) so that

  • (2x-1)2+x+y,
  • (2x-9)2+x+y-8,
  • (2x-1)2+x+y-2 and
  • (2x+15)2+x+y+14
are all prime. It's also necessary that
  • (2x+2a-1)2+x+y+a+b
be composite whenever (a,b) is closer to (0,0) than one of the points (-4,0), (0,-2), (8,6). There are 523 such (a,b)!

Some benchmarking showed me that if I chose y 'small' and x of order 10N, my computer could check 10000 different values of (x,y) in about N seconds. Approximately 1/ln(4x2) of such numbers should be prime - we can call this the 'probability' q of a number being prime (although of course primeness is not random), so in one second, my computer could check about K.q values of (x,y) for some constant K. (actually, K is about 46600)

Thus, the chance of finding a 'nice' configuration in one second is K.q5.(1-q)523. I could check Kq values per second, for each value, we want 4 particular numbers to be prime, and 523 to be composite. What is the best value of q? Well, I just differentiated this and set it to 0. This gave (ignoring q=0 and q=1) q about 1/105, and therefore x about 1024 or 1025, with a probability of success each second of 1 in 40,800,000. Ouch! I didn't think I wanted to wait a year or two for the answer!

So, it was time to use a technique called 'sieving'. That is, choosing (x,y) in such a way that I can be sure the corresponding (desired) primes are not divisible by certain small factors. For example, if x is odd and y is even, we know that the Ulam spiral places an even number on (x,y). Similarly, we can characterise what values of (x,y) give multiples of 3, 5, 7 and so on.

I decided to let x be a fixed multiple of 9699690, so 969969 x 10N-6. Why 9699690? Because it's 2x3x5x7x11x13x19. I also decided I'd choose a value of s, and check only y = 9699690 t + s. The challenge was then to find N and s that would give me answers in the shortest possible time.

In the Ulam spiral, if (x,y) = (9699690 10N-7 , 9699690 t + s), then the number at (x+a,y+b) is (2x+2a-1)2+x+y+a+b. Dividing this by 9699690, the remainder is (2a-1)2+a+b+s. So I wanted two things :

  • The numbers
    • (2.0-1)2+0+0+s = s+1,
    • (2.(-4)-1)2+(-4)+0+s = s+77,
    • (2.0-1)2+0+(-2)+s = s-1, or
    • (2.8-1)2+8+6+s = s+239
    should not have any (nontrivial) common factor with 9699690.
  • As many as possible of (2a-1)2+a+b+s, for (a,b) closer to (0,0) than at least one of (-4,0), (0,-2) or (8,6), should have a common factor with 9699690.
Scanning all the values of s from 0 to 9699689 yielded s = 2652162. Of the 523 original values of (a,b), all but 60 were sure to hold composite numbers, being divisible by either 2, 3, 5, 7, 11, 13, 17 or 19.

So now, I could focus my search in a more promising area of the plane : y = 9699690 t + 2652162, and x = 969969 . 10N-6. I still hadn't chosen N. What value of N would give most likely give results in the shortest time? And would it be short enough?

Well, the equation to maximise was now Kq(1-q)60 This gave the best choice for N as 16. I wrote some code to check the x and y values planned, and in less time that it has taken to write this web page, I had my treasured answer :

This corresponds to the prime 376335944384399970908404671063373. The numbers
  • 376335944384399970908404671063373, at (x,y),
  • 376335944384399970908404671063371, at (x-2,y),
  • 376335944384400591688564671063611, at (x+8, y+6), and
  • 376335944384399660518324671063449, at (x-4, y)
are all prime. The nearest other primes occur at (x-24,y+10), (x-23,y-7), (x-22,y-16), (x-21,y-21), (x-21,y+3), (x-20,y+14), (x-18,y-20), (x-14,y-18), (x-7,y+21), (x-3,y-15), (x-3,y-5), (x+2,y-12), (x+7,y-9), (x+8,y-16), (x+9,y-9), (x+10,y+14), (x+16,y+14), (x+19,y-19), (x+20,y-16), (x+20,y-6), (x+24,y-6) and (x+24,y+22).

The corners of the Voronoi cell are at (x-2,y-1), (x+7,y-1) and (x-2,y+11). It is a 9-12-15 triangle, with perimeter 36 and area 54.

Just for fun, here's another set of primes, giving the same shape Voronoi cell. Here, x=1666666666668663660, and y=16962927220752.

  • 11111111111137737683888921803739612173, at (x,y),
  • 11111111111137737657222255137040993635, at (x-2,y),
  • 11111111111137737683888921803739612169, at (x+8, y+6), and
  • 11111111111137737790555588470534086651, at (x-4, y)

Enjoy!