It is common knowledge that humankind has been fascinated by prime numbers since its origins. On the Ishango bone, an Upper Palaeolithic tool (the fibula of a baboon discovered in 1960 in Africa, to be more precise) someone, around 20,000 years ago, made a series of carved notches divided into three columns, one of which shows the primes 11, 13, 17 and 19. Well, perhaps this beginning is a bit of an exaggeration and the interpretation of the marks on the bone as consciously made prime numbers is a bit fanciful, but, of course, we mathematicians do love primes; at least, a large part of mathematicians, among whom I include myself.
Since Greek times it has been known that there are infinite primes and how to calculate them (Eratosthenes’ sieve), but we mathematicians are always trying to find out more. How many primes are there less than or equal to a given \(x\)? Are there formulae for generating primes? We will focus here on the latter question.
Euler, in 1772, found that \(n^2+n+41\) is prime for \(n=0,1,2,\dots,39\); and there exist other polynomials that generate even more primes. Moreover, using interpolation polynomials (for any data \(x_i\) from \(i=1\) to \(k\) there exists a polynomial \(P(x)\) of degree \(\le k\) such that \(P(i) = x_i\), for \(i=1, \dots,k\), and besides there are simple methods of constructing \(P\)), it is obvious that one can find polynomials that generate, one after the other, as many primes as one wants, and even with prefixed primes. But, as Goldbach had proved in 1752 (yes, the same Goldbach who proposed the conjecture that any even number can be expressed as a sum of two primes, which is still open-ended), there is no polynomial \(P(x)\) (not constant) such that \(P(n)\) is prime for every integer \(n \ge n_0\). In fact, proving this is very simple if we use the language of congruences (this proof is not Goldbach’s proof):
Suppose that there does exist such a polynomial \(P(x)\). We choose an integer \(a \ge n_0\) and take \(p = P(a)\), which by hypothesis must be prime. Any \(b \equiv a \pmod{p}\) will verify \(P(b) \equiv P(a) \pmod{p}\), then \(P(b) \equiv p \pmod{p}\). By hypothesis, \(P(b)\) is also prime, so necessarily \(P(b) = p\). But in the class of \(a\) in \(\mathbb{Z}_p\) there are infinitely many elements (all of the form \(b = a + kp\), \(k \in \mathbb{Z}\), and they are all \(\ge n_0\) when \(k\ge0\)), so the polynomial \(Q(x) = P(x) – p\) has infinitely many roots, which is impossible.
As there are no polynomials that always generate primes, are there other ways to achieve this?
In 1947, Mills [5] proved that there exists a real number \(\theta \in (1,\infty)\) such that \(\lfloor{\theta^{3^n}}\rfloor\) is prime for all \(n \in \mathbb{N}\) (just in case, let us clarify that \(\lfloor{x}\rfloor\) denotes the integer part of \(x\)).
Mills, in his proof, uses a previous result of Ingham: for a certain constant \(K\), and for integers \(N\) greater than a certain \(N_0\), there always exists a prime \(p\) satisfying \(N < p < N + KN^{5/8}\). Assuming this to be true, and roughly speaking, Mills’ method allows us to take \(p_1 = 2\) and from this, and for each \(n\), to choose as \(p_{n+1}\) the first prime of the interval \((p_n, p_n+Kp_n^{5/8})\). Under these circumstances, it is easy to check that \(\lfloor{\theta^{3^n}}\rfloor = p_n\) for each \(n\).
Although determining the value of the constant \(\theta\) is not easy (for example, it depends on the constant \(K\), which is not known), admitting that the Riemann hypothesis is true one can take \(\theta = 1.306\,377\,883\,863\dots\) (details can be found in [1]). But, even under the most favourable conditions, the \(p_n\) that are obtained are enormous:
$$
p_1 = 2,\quad p_2 = 11,\quad p_3 = 1361,\quad p_4 = 2\,521\,008\,887,
$$
\(p_5\) has \(29\) digits, and so on. You can see more terms of this sequence at https://oeis.org/A051254.
But Ingham’s result is not easy to prove, so it is not easy to give a complete proof of Mills’ result. In 1951, Wright [7] realised that, by slightly modifying what Mills had done, he could find — using simpler previous results — another prime generating function; it could be explained in first grade, we might say, but not as physics is explained in first grade (and even in high school), but in a way that students could understand. Wright’s proof only needs to use Bertrand’s postulate, namely that for every \(N \in \mathbb{N}\), there exists some prime number \(p\) such that \(N < p \le 2N\) (if we assume \(N > 3\) we can take \(N < p < 2N-1\)). A simple proof of Bertrand’s postulate can be found in [6, section 9.2] (this proof is essentially the one given by Erdős in 1932).
Starting from \(p_1 = 3\), Wright chooses a sequence of prime numbers \(\{p_n\}\) such that \(2^{p_n} < p_{n+1} < 2^{1+p_n}\)$, whose existence is guaranteed by Bertrand’s postulate. Then, Wright proves that there exists a real number \(\alpha \in (1,2)\) such that the terms of the sequence \(\{\alpha_n\}_{n=0}^{\infty}\) defined —recursively— by means of
$$
\alpha_0 =\alpha, \quad \alpha_{n+1} = 2^{\alpha_n}, \quad n = 0,1,2,3,\dots
$$
satisfies that \(\lfloor{\alpha_n}\rfloor\) is prime (the \(p_n\) we constructed earlier) for all \(n = 1,2,3,\dots\)
In other words, the integer part of \(2^{2^{\cdot^{\cdot^{\cdot^{2^\alpha}}}}}\) is prime for any number of iterations of the exponential.
Even if we always take the smallest prime \(p_{n+1}\) that satisfies \(2^{p_n} < p_{n+1} < 2^{1+p_n}\), the resulting primes are enormous, much larger than in Mills’ case. Indeed, the first values are \(p_1 = 3\), \(p_2 = 11\) y \(p_3 = 2053\), but \(p_4\) already has \(618\) digits.
In addition to the original articles [5] and [7], more details on the Mills and Wright prime generating methods, as well as some others, can be found in [2] and [6, section 9.3.2].
There are also functions generating primes from constants that are defined using all primes (actually, in Mills’ and Wright’s constants the same thing happens, it’s just that it is more hidden through an exists, and now there is going to be an explicit formula for the constant).
For example, taking \(\alpha = \sum_{k=1}^{\infty} p_k/10^{2^{k}}\), where \(\{p_k\}\) is the sequence of all the prime numbers, one has
$$
p_n = \lfloor {10^{2^{n}} \alpha} \rfloor – 10^{2^{n-1}} \lfloor {10^{2^{n-1}} \alpha} \rfloor.
$$
Similarly, and if we have previously proved that the integer \(r\) satisfies \(p_n \le r^n\) for all \(n\) (which is true for \(r=2\) by Bertrand’s postulate, and even easier to prove for \(r=4\)), the series \(\alpha = \sum_{k=1}^\infty p_k/r^{k^2}\) is convergent and gives the following prime generating function:
$$
p_n = \lfloor {r^{n^2}\alpha} \rfloor – r^{2n-1} \lfloor {r^{(n-1)^2}\alpha} \rfloor.
$$
In both cases (which can be seen in [4, section 22.3]), the justification of the corresponding expressions for \(p_n\) is straightforward; the former, in particular, is just a manipulation of the decimal development \(\alpha = \sum_{k=1}^{\infty} p_k/10^{2^{k}}\), which contains the primes embedded in it.
In 2018, four 18- or 19-year-old students from Buenos Aires (Dylan Fridman, Juli Garbulsky, Bruno Glecer and Massi Tron Florentin) devised a new method for generating primes based on a constant, and asked a mathematician from Britain (James Grime) to help them write it up properly and complete the proofs. The method, which can be seen in [3] is, to my taste, beautiful. In the article, the constant is simply called \(f_1\), but here we will denote it \(\lambda\) and I will call it the Buenos Aires constant, which I find much more appealing. In what follows, we will reproduce what they do.
The Buenos Aires constant is defined as
$$
\lambda = \sum_{k=1}^{\infty} \frac{p_{k}-1}{\prod_{i=1}^{k-1} p_{i}},
$$
where, again, \(\{p_k\}\) is the sequence of all primes. This series, which is of positive terms, is convergent since it is bounded by a convergent. Indeed, by Bertrand’s postulate, \(p_{k-1} < p_k < 2p_{k-1} – 1\), so that
\begin{align*}
\lambda &= (p_{1}-1) + \frac{p_{2}-1}{p_{1}} + \frac{p_{3}-1}{p_{2} p_{1}}
+ \frac{p_{4}-1}{p_{3} p_{2} p_{1}} + \cdots \\
&< (p_{1}-1) + \frac{2 p_{1}-2}{p_{1}} + \frac{2 p_{2}-2}{p_{2} p_{1}}
+ \frac{2 p_{3}-2}{p_{3} p_{2} p_{1}} + \cdots,
\end{align*}
and the latter is a telescopic series in which each summand \(({2p_{j}-2})/{\prod_{i=1}^{j} p_{i}}\) (with \(j\ge2\)) is decomposed into two, the first of which is cancelled by part of the previous summand and the second by part of the next. Consequently, \(\lambda < (p_{1}-1) + 2 = 3\). With a computer it is easy to see that \(f_1 = 2.920\,050\,977\,316\dots\).
Let us now use \(g_n\) to denote the partial sums \(\sum_{k=1}^{n}\) of the series with which we have defined \(\lambda\), take \(f_1 = \lambda\) and, for \(n > 1\),
$$
f_{n} = (\lambda-g_{n-1}) \prod_{i=1}^{n-1} p_{i}
= (p_{n}-1 ) + \frac{p_{n+1}-1}{p_{n}} + \frac{p_{n+2}-1}{p_{n+1} p_{n}}
+ \frac{p_{n+3}-1}{p_{n+2} p_{n+1} p_{n}} + \cdots,
$$
with which it is clear that \(f_{n} = p_{n-1}(f_{n-1}-p_{n-1}+1)\).
Then, the \(f_n\) can be defined recursively (starting from the Buenos Aires constant \(f_1=\lambda\)) as
$$
f_{n} = \lfloor f_{n-1}\rfloor (f_{n-1}-\lfloor f_{n-1}\rfloor+ 1),
$$
and satisfies \(\lfloor f_{n}\rfloor = p_n\).
To check this it will be enough to use Bertrand’s postulate again, whereby
$$
f_{n} > (p_{n}-1) + \frac{p_{n}-1}{p_{n}} + \frac{p_{n+1}-1}{p_{n+1} p_{n}}
+ \frac{p_{n+2}-1}{p_{n+2} p_{n+1} p_{n}} + \cdots
$$
and
$$
f_{n} < (p_{n}-1) + \frac{2p_{n}-2}{p_{n}} + \frac{2p_{n+1}-2}{p_{n+1} p_{n}}
+ \frac{2p_{n+2}-2}{p_{n+2} p_{n+1} p_{n}} + \cdots.
$$
As above, these are telescopic series, the first sum \(p_n\) and the second \(p_{n}+1\), so \(p_n < f_n < p_{n}+1\) and \(\lfloor f_{n}\rfloor = p_n\).
It can also be proved that the Buenos Aires number is irrational (for this we use the fact that \(p_{n+1}/p_n \to 1\) when \(n \to \infty\), which is a consequence of the prime number theorem). But, to paraphrase my friend and colleague Eduardo Sáenz de Cabezón in his channel Derivando, I’m not going to do it all myself!; you can read it yourself in the original article [3].
I don’t want to conclude without pointing out that this process of defining the Buenos Aires constant can be applied not only to the sequence of primes \(\{p_n\}\), but to any sequence of positive integers \(\{x_n\}\) that satisfies \(x_{n-1} < x_n < 2x_{n-1} – 1\). Thus we have a Buenos Aires operator \(\operatorname{BA}\) defined as
$$
\operatorname{BA}(\{x_n\})
= \sum_{k=1}^{\infty} \frac{x_{k}-1}{\prod_{i=1}^{k-1} x_{i}};
$$
the number \(\operatorname{BA}(\{x_n\})\) allows us to generate the \(x_n\) in an analogous way as we did with the primes, and \(\operatorname{BA}(\{x_n\})\) is an irrational number if \(x_{n+1}/x_n \to 1\) when \(n \to \infty\). The simplest case is \(\operatorname{BA}(\{n+1\}) = e\).
Referencias
[1] C. K. Caldwell and Y. Cheng,
Determining Mills’ constant and a note on Honaker’s problem,
J. Integer Seq. 8 (2005), paper 05.4.1.
[2] U. Dudley,
History of a formula for primes,
Amer. Math. Monthly 76 (1969), 23-28.
[3] D. Fridman, J. Garbulsky, B. Glecer, J. Grime and M. Tron Florentin,
A prime-representing constant,
Amer. Math. Monthly 126 (2019), 70-73.
[4] G. H. Hardy and E. M. Wright,
An Introduction to the Theory of Numbers,
fifth edition, Oxford University Press, 1979.
[5] W. H. Mills,
A prime-representing function,
Bull. Amer. Math. Soc. 53 (1947), 604.
[6] J. L. Varona,
Recorridos por la Teoría de Números, segunda edición,
Electolibris y Real Sociedad Matemática Española, Murcia, 2019.
[7] E. M. Wright,
A prime-representing function,
Amer. Math. Monthly 58 (1951), 616-618.
Leave a Reply