2
$\begingroup$

The following is a formula for the $n$-th prime number ($[\,]$ represents the floor function). Who was the first person to discover it?

enter image description here

The value of this formula: people have been exploring the general term of the prime number sequence, and this is an answer to it.

$\endgroup$
1
  • 3
    $\begingroup$ Did you a basic google search? The first search I tried, a phrase search for "formulas for primes", leads to a lot of places to begin looking. You'll want to focus especially on journal papers cited in connection with this specific formula and survey papers of such formulas in general, and for these this google scholar search will also be helpful. Also try varying the phrase to things like "prime formulas", "prime number formulas", etc. $\endgroup$ Jul 11 at 15:17
4
$\begingroup$

The formula is derived in Willans, On Formulae for the nth Prime Number (1964) (Mathematical Gazette vol. 48, no. 366, pp. 413-415), who references Dickson's History of the Theory of Numbers, ch. XVIII "for references to other formulae of this nature". He does not quite mean explicit formulas for $p_n$, but rather explicit formulas for functions that take different types of values on primes and non-primes (and can be adapted to the task by simple manipulations that Willans sketches). Explicit formulas of a somewhat different nature were published earlier by Mills A prime-representing function (1947) and Wright A Prime-Representing Function (1951).

Dickson gives a couple of examples, including Pocklington's 1911 example based on Wilson's theorem that seems to be Willans's inspiration. Later variations on the theme are reviewed in Dudley's Formulas for Primes (1982), who remarks:"Although Wilson's Theorem has proved to be notoriously unuseful in finding primes, this has not stopped the production of formulas in which it is essential". Interestingly, Willans shared the sentiment, and already felt the need to justify the exercise:

"While the formulae in this article are unsuitable for application to problems in prime number theory, they at least provide definite answers to the questions (see e.g. Hardy and Wright, An Introduction to the Theory of Numbers, § 1.5):
Is there a formula for the nth prime number?
Is there a formula for a prime, given the preceding prime?
"

Connes, the Fields medalist best known for developing noncommutative differential geometry, wrote a recent follow-up Around Wilson's theorem (2018) that quotes Willans's related formula for the prime number function. Rowland's A natural prime-generating recurrence (2017) quotes Willans's formula from the OP noting that it and its relatives are "generally infeasible to compute in practice".

$\endgroup$
6
  • $\begingroup$ I was surprised that the formula was so new. $\endgroup$
    – user776490
    Jul 13 at 8:56
  • 1
    $\begingroup$ @Conifold, It is a pity you didn't quote Dudley's conclusion in "Formulas for Primes": "... formulas for formulas' sake do not advance the mathematical enterprise". Formulas should be useful. If not they should be astounding, elegant, enlightening, simple, or have some redeeming value". I am curious to know whether you think Willan's formula has any of these values? $\endgroup$
    – Ng Ph
    Jul 14 at 9:31
  • $\begingroup$ @NgPh I do not know if it can astound or enlighten somebody, or suggest something useful to them, maybe. Willans got the formula as a side effect of reflections on relationships between different types of formulas in Dickson that Dudley and later Connes reused. Sometimes insights come from unexpected places and in small increments, so I am content to pass on the information. $\endgroup$
    – Conifold
    Jul 15 at 0:33
  • $\begingroup$ @Conifold, fair. Let me correct that Dudley didn't "reuse" Willan's formula for nth prime. Neither did Connes' paper (Conne reformatted Willan use of Wilson's theorem to get a formula for a characteristic function, F(x)=1 if x is prime and 0 otherwise). This is another example of "for formulas' sake" observed by Dudley. Wilson's theorem itself is of little use as a primality test, by the huge computations it requires. Wrapping a cos around it (for formula's sake) is a joke, not a prowess. Willan himself seemed to imply that he was teasing, in his conclusion. Thanks for the biblio research! $\endgroup$
    – Ng Ph
    Jul 15 at 8:10
  • 1
    $\begingroup$ @NgPh That sentence is too cumbersome, sorry, the intended object of "reused" was "reflections" rather than "formula" :) $\endgroup$
    – Conifold
    Jul 15 at 8:28
3
$\begingroup$

In my opinion, this formula has value in teaching Mathematics (not only to kids). It can be used to illustrate what exactly is Math (as a science of rigorous problem statements and reasonnings). It can be used to explain that Math does not reduce to, or necessarily imply, complicated formulas. It can be used to explain the deep implications of the question “Is there a (practical) formula for the nth prime?”, and why Willan’s “formula” (and many alike) is not an answer to the question.

I do not need to recall that, absent of a “true” formula, a brute-force approach is necessary, that is testing exhaustively for primality condition. Conversely then, a formula is not an answer to the question if it is just a disguised form of the exhaustive search approach, or even worse, the computation it implies is greater than that of a search algorithm. It is quite easy to determine that Willan’s solution is not an answer, in this sense of "no pratical use". The demonstration holds in one page (out of the 3-page publication) and is quite easy to follow. But we can do that by dissecting the formula itself.

We have a first summation to perform, over index k=1 to 2^n. Why? Simply because 2^n is large enough so that we are sure that the nth prime we are looking for is in the set of integers less than 2^n. This is a first clue that the so-called “formula” could be a disguised exhaustive search (in the set of integers [1,2^n]).

Next, let’s dissect the inner second summation, with index i=1 to k. What if this is a disguised primality test for all integers <k? That is, the terms of the summation use a function that takes value 1 if index i is prime and 0 otherwise. And sure, the cosinus is there just for that (see Eq. 1 in Willan’s proof). At this point, we can conclude, mathematically, that the whole exercise is to disguise an exhaustive search. But we can also point out that it is a very inefficient search. Eratosthène’s method (280BC) is less computing intensive.

In fact, anyone trying to "program" such a formula will quickly ditch it in the bin. Those who never try, will marvel at it as a "discovery".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.