An Exact Formula for the Primes: Willans' Formula

1,323,610
0
Published 2022-09-22
Formulas for the nth prime number actually exist! One was cleverly engineered in 1964 by C. P. Willans. But is it useful?

----------------

References:

Herbert Wilf, What is an answer?, The American Mathematical Monthly 89 (1982) 289–292.
doi.org/10.1080/00029890.1982.11995435

C. P. Willans, On formulae for the nth prime number, The Mathematical Gazette 48 (1964) 413–415.
doi.org/10.2307/3611701

Further reading:

Jeffrey Shallit, No formula for the prime numbers?.
recursed.blogspot.com/2013/01/no-formula-for-prime…

----------------

Python code

import math

def prime(n):
return 1 + sum([
math.floor(pow(n/sum([
math.floor(pow(math.cos(math.pi * (math.factorial(j - 1) + 1)/j), 2))
for j in range(1, i+1)
]), 1/n))
for i in range(1, pow(2, n)+1)
])

----------------

(* Mathematica code *)

prime[n_] := 1 + Sum[Floor[(n/Sum[Floor[Cos[Pi ((j - 1)! + 1)/j]^2], {j, 1, i}])^(1/n)], {i, 1, 2^n}]

----------------

0:00 A formula for primes?
1:24 Engineering a prime detector
4:00 Improving the prime detector
5:46 Counting primes
6:29 Determining the nth prime
9:42 The final step
11:36 What counts as a formula?
12:56 What's the point?
13:51 Who was Willans?

----------------

Animated with Manim. www.manim.community/
Thanks to Ken Emmer for supplying the microphone.

Web site: ericrowland.github.io/
Twitter: twitter.com/ericrowland

All Comments (21)
  • @MrDannyDetail
    Assuming Birmingham is the British one, rather than the one in Alabama, then our C.P. WIllans should be in the England and Wales Birth, Marriage and Death records so I had a look for you. I found a Charles Percy Willans whose birth was registered in Huddersfield in 1878, and whose marriage to either Amy Warner or Beatrice Woodman was registered in Birmingham(!) in 1899. Then there's another Charles Percy Willans whose birth is registered in Birmingham(!!) in 1902, with mother's maiden name Warner, making him likely the son of the other one, and making it likely the other one's wife was Amy Warner rather than Beatrice Woodman. A Charles Percy Willans (presumably the younger one) registered a marriage in 1923 in Sculcoates to Ada Smith. The problem is the younger Charles Percy's death was registered in Buckrose aged 55 in 1957, and the older one's death was registered in Hull aged 81 in 1960, so if it was either of these gentlemen they'd have to have been published at least a few years posthumously, and I've no idea if that is plausible. There is only one other possibility, a Christopher Paul Willans whose birth is registered in 1942 Bradford, with mother's maiden name Walker. Sadly there is a death registered in 1971 in Bradford of a Christopher Paul Willans who was born 17th January 1942. Looking for a marriage of a Mr Willans and Miss Walker gives me Christopher's likely parents, Ernest Victor Willans and Jessie G Walker, who married in 1937, and looking for Ernest's details shows that he was born in 1904, and died in 1964 aged 59. Looking for Jessie G Willans led me to a death record in 1984 in Bradford of Jessie Gordon Willans who was born 5th March 1909, so that is likely her. Checking for births of Willans' with mother's maiden name Walker didn't find any real possibilties for siblings, so Christopher was likely an only child. Also no sign of a marriage for him, so probably no children either. All in all I suspect C.P.Willans actually was Christopher Paul, but can't find actual proof, and he seems to have no living close relatives who could be contacted and asked if he was the mathematician in question. One other possibility to bear in mind is that C.P. might have been a woman who had either married a Mr Willans, or who was born as a Miss C.P. Willans and went on to marry and change her surname afterwards. If C.P. was a woman perhaps she used initials-only to conceal this fact, rather like J.K.Rowling did. I found only one female whose birth name was of the form 'C.P. Willans' but she was born in the early 60s (and is very likely still living, so I have to stay vague here for data protection reasons) so she can be ruled out. Searching for every Miss C.P [Surname] who ever (by 1964 anyway) married a Mr Willans is a harder and more time consuming task which I'm afraid I don't have the opportunity to attempt today.
  • @jakebrusca49
    I’m pretty sure C. P. Stands for coolformulaforcalculating primes
  • @tolstoj_
    When I first saw the formula I was like.... ya, I'll never get that. Then I followed the formula every step of the way with no difficulties after you explained it. You are amazing at explaining things, man. That's a rare gift.
  • @gblargg
    The floor function is the key here. It's basically a conditional.
  • @zhru-kq6in
    He didn't find a suitable programming language so he decided to use math as one.
  • @omp199
    I have devised a formula for working out the true identity of C. P. Willans. It involves representing a human being as a positive integer that encodes the information in all of their synaptic connections. Part of the formula then loops through the interactions between the synapses, generating all the thoughts that this person would have, including all the mathematical papers that they would compose. You then have to apply a function that yields 1 if these mathematical papers include the paper with the prime-generating formula in it, and 0 otherwise. Then of course you have to loop through all possible humans, picking out those for whom the formula yields a 1. It all gets very messy, but I have completed the work. I would quote the formula explicitly in this comment, but unfortunately the character limit does not permit it.
  • @iamsushi1056
    My favorite example of this sort of “math as a programming language” is the guy who managed to extend the 3n+1 problem into a continuous function that can be expanded to process complex numbers. It goes like this: C(z)=.25(2 +7z -(2+5z)cos(πz)) It’s beautifully simple (when not expanded) and super cool.
  • As an engineer who frequently uses a fair amount of math, I am impressed with how elegantly all the pieces fit together, even if it is slow to implement. I'll have to keep this in mind the next time I have a complicated function / algorithm to design. It's something to aspire to!
  • @muskyoxes
    The thing we want is to "skip over" finding all the other primes up to the one we want. The summations in this formula make it so we aren't skipping over anything
  • Primes aside: I find the idea of turning source code into a math formula, which can be processed with a whole new set of tools, very fascinating. Yes, it is massively chunky and the complexity (think big O) is through the roof, still you can write it down without problems. Maybe there is a similar approach for other algorithms, which then can yield new insights. A very interesting field of study. I have to learn more about this.
  • @uhbayhue
    This was one of the most incredible explanations I've ever heard. You broke down an unapproachable formula into small digestible bits, and it seemed so easy afterwards! Thank you, and your teaching skills are fabulous!
  • I really really empathize with this formula since when i was a teen i discovered Desmos. In desmos you can input arithmetic formulas and ONLY arithmetic formulas, it was not a programing language or anything like that, and yet, i decided that i wanted to use it AS a programing language. I managed to make som pretty cool things! Like the mandelbrot set, and a 3D projection system with custom controls, and a LOT of extremely fun and informative projects. The thing is that for doing these things i needed to write everything in the contexts of arithmetic. I did have the ability to write piecewise functions, so this formula for example could have been a lot shorter, and there were list that could be iterated on sums (I think, i don't really remember super well). But the point is that whenever i has a project in mind i had to do a process very very similar to this, where i had to translate everything into the language of maths. I was a pretty hard experience that showed me that math is truly beautiful in it's notation, being so simple to define and undestand (You can build the whole thing just using logic and the idea that there exists a thing called a set, which could either be empty, or contain one or more sets, you can't get more fundamental than that in my opinion), and that even then, there were a lot of things i simple was not able to do. Of course, the language of math goes far far far beyond what you can do in desmos, and there were far more efficient ways to do what i wanted to archive, like learning an actual programing language. But at one point it became not a matter of weather i should, but rather weather i even could. And that question of "can i" filled me with a lot of passion for the subjets i was trying to explore and learn about. And idk, in a way, the fact that this formula exists, and that i recieved the backlash that is did feels kinda, nice. Feels like i was not alone in this weird, useless, but very interesting and passion driven math endeavour.
  • I feel like the existence of such a formula wouldn't be too surprising in the 1960s since it's after Turing's paper and the study of primitive recursion, but I did study recursion/computability theory. Though the specific formula itself is pretty cool.
  • @Spulg
    Love it! Your way of narration is excellent, the pacing really on point. Keep it up. ✨
  • This is just amazing. I never in my life conceived that you could write something that I’d feel must require an algorithm as a formula. It’s superbly ingenious and mind blowing. Thanks for making this
  • The last clip illustrates better than a 1000 words how inefficient the formula is lmao Btw, this is one of the best maths videos I've seen so far, especially cause I've never seen anyone approach a formula as an algorithm that performs useful transformations on a small function that generates a desired pattern. I guess this approach cannot be applied to most formulas, but in this case it makes it very easy to understand how it works, despite the scary step, cos and nth root functions. I feel like this kind of approach should be taught more to maths students to develop their pattern recognition and intuition when seeing new formulas. I guess this kind of develops naturally, but I've never been taught to analyze formulas in this way
  • I feel like the floor function is some kind of "cheat" for algebraic operations. It's basically using an if statement
  • @yumnuska
    Please keep going; don’t stop! Your pacing, narration, and tone are exceptional. I’m so happy to have another maths channel to follow. Great work!
  • @spase667
    Excellent video, Eric! Something about this made me nostalgic for high school: I recall vividly the point when I started seeing formulas as shorthand for computational algorithms, when I reproduced the formula for Riemann sums by recalling the process of chopping the area under the curve into rectangular bits. Numerous other formulas for integrals in calculus came immediately; I rarely had to memorize them because the correspondence between the formula and the geometry is so crystal clear.