As Don Zagier said in 1975: “There are two facts about the distribution of prime numbers….The first is that, despite their simple definition and role as the building blocks of the natural numbers, the prime numbers grow like weeds among the natural numbers, seeming to obey no other law than that of chance, and nobody can predict when the next one will sprout. The second fact is even more astonishing, for it states just the opposite: that the prime numbers exhibit stunning regularity, that there are laws governing their behaviour, and that they obey these laws with almost military precision.”1
This is a fair interpretation of the knowledge surrounding primes. I have decided to explore how prime numbers fit in with natural numbers. I will discuss their infinity as well as their distribution with regards to natural numbers, and interesting ways of depicting this that raises further questions.
To understand how prime numbers work, one must go right back to 300BCE where Euclid revealed the most concrete fact about prime numbers: there are an infinite number of them. Euclid proved this theorem by simple contradiction2.
He made the assumption that there were a finite number of prime numbers – and therefore one could put them all on a list.
He called these primes p1, p2, …. pn.
If P is the common multiple of these primes plus one (P = p1 * p2 * p3 * ……. pn + 1), P must be indivisible by all the numbers on the list as it is one more than a multiple of any of them individually.
Therefore, either P is a prime that isn’t on the list, or, if P is not prime, then it is divisible by another prime which also isn’t on the list; let’s call this p. We know that p cannot be any of p1, p2, …. pn and therefore p is a prime number that wasn’t on the original list. Thus, the original list was incomplete. As this is always true, we can conclude that there must be an infinite number of primes as the list will always be incomplete.
Euclid had clearly demonstrated that prime numbers were infinite, but what about their distribution. Do they appear regularly, or do they become more spaced out? The simple answer is that they become rarer and more spaced apart, but by how much and at what rate? The Prime Number Theorem (PNT), first discovered by Gauss in 1792, explores the distribution of primes, described as:
where π(x) is the number of primes less than or equal to x and the probability that a random integer in that range is prime is 1/loge(x).
When Gauss’ approximation is plotted against the actual distribution it appears to be incredibly regular for natural numbers up to 50,000 – though clearly not perfect.
In 1808, Adrien-Marie Legendre improved Gauss’ approximation by taking away the constant 1.08366 from log(x), i.e.
However, Gauss also came up with a better approximation than his own by using the fact that the probability that the random integer below x is a prime is 1/loge(x).
This gave the approximation for a Logarithmic sum:
This can be further simplified to the Logarithmic integral:
Both of these plotted against π(x) for the first 50,000 natural numbers appear as:
Where the lines appear to perfectly line up with π(x). It seemed Gauss and Legendre had discovered how prime numbers were distributed. However, this wasn’t the case because as you increased the range they both became less accurate.
The most accurate known approximation of the distribution comes from Bernhard Riemann who further developed Gauss’ method of using the approximation of probability of an integer being a prime in a certain range by including powers of primes into his calculations, e.g a prime squared is “half a prime” and a prime to the power of 3 is a “third of a prime”. This led to the approximation:
now known as R(x) in honour of Riemann. The graph below demonstrates how accurate these three functions are compared with π(x):
The graphs show the general trend that prime numbers become more spaced out amongst the natural numbers, and that we have a few more precise equations which can track this trend for the most part. However, it also tells us that there isn’t much certainty regarding their distribution, just that they become rarer – mathematicians have been unable to discover a perfect trend of their relation with the natural numbers.
One fascinating depiction of prime numbers was first stumbled upon almost by accident. In 1963, Stanslaw Ulam, allegedly while bored in a lecture, started writing out the natural numbers in a spiral pattern. At first it was just a doodle, but when Ulam focused on the prime numbers he discovered that they did in fact appear to form a sort of pattern.
Here is the beginning of an Ulam spiral3 in which I will demonstrate the patterns.
All the prime numbers (excluding 2) lie on diagonal lines on this spiral. All the diagonals can be labelled with a polynomial in the form f(n) = 4n2 + bn + c (where b is even). If c is odd all the values on the diagonal will be as well, which means that c must be odd for primes to occur. A special polynomial discovered by Euler gives a prime value for every integer from 1 to 40, (x2 – x + 41), and can be observed clearly on larger spirals. However, it is observed on two separate diagonals.
The Ulam spiral has shown that there are clear patterns to how prime numbers relate to the natural numbers as seen with the continuous diagonals and the areas which are more densely populated. This highlights how despite not being discovered yet there must be a solution to how they slot in. It can be observed more clearly on a larger Ulam Spiral (as shown below):
Evidence for these higher density diagonals can be calculated to provide numerical evidence behind the obvious trends observed on the spiral.
This is calculated by4:
Let Pf(n) be the number of prime values for f(x), x = 1, 2, 3, 4, …… n.
The value Pf(n) is then divided by π(x) [once again denoting the number of primes up to n in the natural numbers].
The value obtained is given the notation β.
This allows for the discovery of diagonals with a higher prime density than natural numbers, e.g:
- 4n2 + 154n + 1523 , β = 3.3205
- 4n2 + 150n + 1447 , β = 3.3205
- 4n2 + 220n + 3083 , β = 2.9619
Other examples of lines that exhibit a greater density of prime values include both:
x2 + x + 3399714628553118047
x2 + x – 33251810980696878103150085257129508857312847751498190349983874538507313
Both of these contain roughly 12 times as many primes as the average diagonal in the Ulam spiral.
All these little equations show that there is some sort of order or reason to the prime numbers, however at this current point discovering one explanation for the order of primes feels hopeless. Over 2000 years since Euclid proved they went on forever mathematics still couldn’t tell you when one will pop up or how far in between two primes.
A further variation of the Ulam spiral was developed in 1994 by Robert Sacks5– instead of a square spiral he used an Archimedean spiral which distributes the natural numbers equally around the square numbers which are in a horizontal line. This spiral (known as the Sacks Spiral) also exhibits similar patterns to the Ulam spiral; however, they appear more clearly in this format. The Archimedean uses the following equations as polar coordinates to generate it: r = n1/2 and θ = 2 π n1/2.
The larger spiral clearly possesses areas of greater density just like the Ulam spiral – however, where some functions were displayed on two separate diagonals on the Ulam spiral, they are now shown more clearly as one – most namely Euler’s polynomial: x2 – x + 41, which is the single darkest line on the spiral. Lines with the greatest density of primes compared with natural numbers up to 1000 include6:
- n2 + n + 11 => 288/1000 primes
- n2 + n + 17 => 366/1000 primes
- n2 + n + 41 => 582/1000 primes
This contrasts with 168/1000 for the natural numbers. These functions show definite sequences which include a great number of primes; although, they don’t hold much value in the overall order. But could provide other functions more likely to predict prime numbers.
All this evidence proves that despite many attempts all we know about prime numbers is that they go on forever, spreading out amongst the natural numbers. Gauss, Riemann, Legendre, Ulam, Euler and Sacks have all been able to uncover a tiny bit more – a pattern that works but just not for all primes, thus reinforcing how little about primes is really known. The Spirals show clear promise some sort of explanation on their distribution, it is just yet to be found.
- “The first 50 million prime numbers”, Don Zagier (fig 1, fig 2, fig 3) – found at: https://people.mpim-bonn.mpg.de/zagier/files/doi/10.1007/BF03039306/fulltext.pdf
- EUCLID’S THEOREM ON THE INFINITUDE OF PRIMES: A HISTORICAL SURVEY OF ITS PROOFS (300 B.C.–2017) ROMEO MESTROVIC – found at: https://www.researchgate.net/publication/329684399_EUCLID’S_THEOREM_ON_THE_INFINITUDE_OF_PRIMES_A_HISTORICAL_SURVEY_OF_ITS_PROOFS_300_BC-2017
- Ulam Spirals – https://thatsmaths.com/2019/09/12/spiraling-primes/
- Quadratic Polynomials With High Asymptotic Prime Density in The Ulam Spiral – Steve Bode 2018
- Sacks Spirals – http://www.naturalnumbers.org/sparticle.html
- The High Primality of Prime-Derived Quadratic Sequences http://www.naturalnumbers.org/ppanalysis.html
- Fig 4. Image Source – https://en.wikipedia.org/wiki/Ulam_spiral