An Exact Formula for the Primes: Willans' Formula
Vložit
- čas přidán 18. 05. 2024
- 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...
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/...
----------------
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: / ericrowland
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.
Thanks so much for spending some time on this! So the current best guess seems to be Christopher Paul Willans (1942-1971).
@@EricRowland Yes, and just to add I've been looking in the British Newspaper Archive and have found a C.P. Willans in the 17th September 1958 edition of the Shipley Times and Express, in a article listing the boys of Bradford Grammar School who had achived passes in the Oxford and Cambridge General Certificate of Education examination at the Ordinary Level, and detailing what subjects they passed in. The C.P. Willans in this article passed in Scripture, English Language, English Literature and French. There's no mention of Mathematics though. In 1958 Christopher Paul Willans would have been about 16, which is the age that British students take their GCSEs (or GCEs/O-Levels as they were until the 1970s), and Bradford is exactly the right place for it to be him, so I think the C.P. in the 1958 article is Christopher and that at the very least it proves that Christopher was an academically gifted person, and therefore a plausible candidate for being the C.P. Willans of the mathematical paper.
Wow you really did your work
All things “”complex””~>
should be simple😉
We all know it… just never accept it
this is the type of comment that I keep coming to CZcams for !! :)
Thank you SO MUCH for all this !!
P.S. Though, to be perfectly fair: I somehow can't buy your excuse that it:
"is a harder and more time consuming task which I'm afraid I don't have the opportunity to attempt today"
I don't see how it should be thus, considering all the work you'd already done... ~_~
I’m pretty sure C. P. Stands for coolformulaforcalculating primes
Mr. Coolformulaforcalculating 'Primes' Willans
Hmmmmmmmm
cp might stand for something else
At a glance that looks like generatingfunctionology, which happens to be a famous book from Herbert Wilf who coincidentally appears in this video
@@kingoreo7050 sus
The floor function is the key here. It's basically a conditional.
The floor function is a conditional and the sum is a loop.
If you have loops and conditions, you have a quite universal programming language.
Efficiency is the key at that case. But one could code with that. (Debugging would be hell...)
I’ve never heard of a floor function but it looks hella useful lmao
I've heard about the floor function in computing but first time in math notation realm. I guess I'm now able to solve my 1-100 using four-fours formulae
Learning the floor function for the first time, I remember thinking floor and cieling functions felt different, almost like cheating or non-math
it can be replaced with an arbitrarily large exponent. As the exponent increases (and also stays even), cosine to the power of the exponent approaches floor(cos^2())
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.
the two sums kinda made me suspect something like he explained, because the "naive" algorithm in programming would be to loop over integer candidates and then loop over more integers to divide them by, but i would've never suspected the amount of math tricks going into this formula :D
All he did was explain it tho
I still don't know why j is there
I totally agree. It all started making so much sense, when he explained it step by step
it's not a gift, it is a skill, a process, and takes a lot of time to make these videos :) but yes it is definitely a gift for us!
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.
willans would be proud
Died with the last joke, good one XD
LoL 😂, obviously fake but I dare you to make a video about it
I highly doubt you have a formula for calculating the neuronal activity of the brain. There are millions and millions of syntaxes firing every second and furthermore I highly doubt you can reduce the complexity of the neuronal activity of the brain to simply just a 1 and a 0..... 🤦♀
@@coolorphans
r/woooosh
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.
Is there a name for this process?
I see it as not turning *source code* into a mathematical formula, but turning an *algorithm* into a formula. The result demonstrates that we've translated the algorithm into something which is needlessly clunky and hard to understand, and inefficient in the sense that any attempt to implement the formula would be far less efficient than a straightforward attempt to implement even a naive algorithm for counting primes. It is like implementing it in an esolang. Someone might derive enjoyment from translating it into a formula, but nobody would actually use the result. The difference is that we know that esolangs are jokes -- programs in them are cute but useless -- but publishing the mathematical formula disguises something useless as something important.
@@rosiefay7283 Evaluating the formula is way slower, than running the efficient algorithm. But from the formula, you could derive some attributes or invariants, that could help to get new insights. I am still looking for an example to demonstrate this.
@@Moonz97 You should look up „branchless programming“. It‘s definitly not the name for the process, but in my opinion the idea ist similar.
@@AndreasHontzia although "new insights" is probably pretty hard (and inspecting the algorithm itself, or just parts of the algorithm, is probably easier), at least in this case, especially because the usage of the floor function makes the applicable theorems and such much more, uhh "sparse", it is similar to the absolute value function, but even worse (not continuous); and applying discrete mathematics gets hard when cosine is invoked. Classic computer-level fixed-width numbers calculations/simulations run into trouble either with precision (fixed width floating pointer) or overflow (fixed width integers); arbitrary-precision numbers use a large amount of memory. So at first an approach like this might make sense (and in many cases it actually works), but this specific example doesn't yield much...
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.
where is it from? and what do you mean "when not expanded"?
That's amazing. I wonder if that's the formula the fingers fractal uses. I plugged into wolframalpha for 1 thru 50 and it gave back all their one step iterations. You can feed it any complex number you want though.
He didn't find a suitable programming language so he decided to use math as one.
LOL
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
Exactly.
That's true, we have tested numbers in the 30 million digit range, when there's still numbers with about 50 digits that haven't been tested
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.
This is a great point. Were the people working on primitive recursive functions constructing prime-generating formulas and such? I've never seen Willans' formula discussed in that context, so it would be interesting to understand how it fits in.
@@EricRowland Is arithmetic turing complete?
@@ValkyRiver is it? I can see how you could extend the ideas here to show primitive recursion, but full turing completeness seems a bit of a stretch
@@globalincident694 primitive recursion is not turing complete, (for example, then cant not stop) but mu recursive formulas are (mostly similar, but without the search limit)
@@globalincident694 The current context doesn't involve primitive recursion, but I think arithmetic can in some sense be generalized to a turing machine. Given my limited understanding, Godel's incompleteness theorem is very related. Take a look at fractran, which is turing complete.
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!
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!
Thank you so much!
I feel like the floor function is some kind of "cheat" for algebraic operations. It's basically using an if statement
For me it's not so much that the floor is a type of if statement (it rounds down every number, regardless of what it is). But it is true that the floor function is not continuous, which is a big departure from most traditional functions.
I feel like we need more of these. Taking the sign of a number is unnecessarily bothersome without the sign() function.
@@EricRowland To be honest, the very definition of a "function" is vague, in general. For example: Prove that a function f(x)n is NOT, in fact, a function.
@@jonorgames6596 A function has a very clearly defined definition in mathematics, until people call something that isn't a function a function anyway.
@@EricRowland I can't help but think that Willans also felt it was a bit of a "cheat". Look at how he eliminated the sign. If someone sees absolutely no issue with using the floor function, then you'd expect that they'd see no issue with using the absolute value function. But when Willans needed to remove the sign, he didn't use the direct approach of taking the absolute value, he instead used the indirect approach of squaring the value.
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.
Wow man that's reallly cool
"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"
Not just your opinion, you cannot get more fundamental than that, period. It's pretty much the main assumption that all of math is built upon.
@@cameron7374 Yup, I really really love set theory just because of that
@@cameron7374 That's not really true. Logic+set theory is a traditional approach to mathematical foundations, but many researchers these days are working instead from type theory+category theory.
Same. I recommend trying out the Haskell programming language - the overall thought process is quite similar to that of Desmos.
I love formulas like this because, whether most people admit or not, it is computer science. Computer science is just one of the logical extension of math, pushing it to its limits to perform tasks instead of explore itself, and its amazing to see people explore that without even approaching computer science as its own field.
You have it upside down. Computer "science" is not science, it's Mathematics.
@@AndrewBlucher That's what I said, its one of the logical extensions of math. I was pointing out how people used math in that way without considering it as a unique field I thought it was interesting.
(And computer science is a science, just as math is. People are making hypotheses, testing them, and finding results. In my eyes that's enough to be a field of study)
@@Creepyslandofdreams Oh, there's no doubt that it's a field of study. Just not a science, just as mathematics is not a science.
@@AndrewBlucher Anything is considered a science nowadays, like history, sociology, economics, and other social “sciences”
@@ahuman32478 That's a nice screen name you have!
You can be sure that any field of study that has Science in it's name isn't.
Lot's of fields of study use "scientific" methods and "modern" technologies and techniques, and so they should. But that doesn't make them sciences.
Why do they want to be a science?
There are plenty of other ways to learn and develop. Mathematics is one worthy field, for example. Some people claim that it's a science, but where science makes predictions, Math has hypotheses. Not the same thing.
Cheers
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
Love it! Your way of narration is excellent, the pacing really on point. Keep it up. ✨
Thank you so much!
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
@@bobaGogo That's why i view math as an extension of programming rather than vice versa. I've never been able to formalize those feelings though.
@@LegendLength i feel like it depends. But using floor in math is definitely an extension of programming.
How can I represent the flooring function with algebra?
Floor(x) = ?
Maybe there is some crazy way through trigonometry and logarithms to create a flooring function, if there is then this is a formula and not an algorithm. But I've never seen the flooring function ever represented through algebra.
@@bobaGogo Neither trigonometry functions nor logarithms are algebraic. The only algebraic functions are addition, multiplication, subtraction, rational exponentiation, integer nth root, and funnily enough, finite sums and finite products.
en.wikipedia.org/wiki/Algebraic_expression#Algebraic_and_other_mathematical_expressions
Flooring doesn't seem to be algebraic though, you're right.
@@bobaGogo there is almost a way: en.wikipedia.org/wiki/Floor_and_ceiling_functions#Continuity_and_series_expansions
Are the 1's and 0's always consecutive? could you stop after hitting the first zero?
This video is an absolute beauty. It should be shown to each and every math student in the world. Kudos!
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!
it's so awesome to see such an intractable looking formula made so easy to understand when broken down slowly into small pieces.
I think probably difficulty was hidden in Wilson's Theorem. It would have been nice to see an outline of a proof for it.
Thanks, I’ll consider that for a possible future video topic!
I feel like Wilson's theorem is cool if you present modular arithmetic first, and that would distract a bit from the main point of the video
I guess I can search later but if someone has a link to any proof of Wilson's Theorem, it would be interesting to read. Otherwise if Mr Rowland would do a short video on it, that would be great too.
@@Tletna The proof is pretty quick.
Lemma: If a is in [1, p-1], then in the sequence a, 2a, ..., (p-1)a each element gives a different remainder modulo p.
Assume by contradiction that ka and la (p-1>=k>l>=1) give the same remainder modulo p. Then p | ka-la = a(k-l), so p|a or p|(k-l), which results in contradiction because 0
The proof is actually pretty easy, there are videos on yt that cover it
I once wrote a wave function for primes. It was a product of sawtooth waves up to "n". Where n was the size from zero of the numbers you wanted to plot.
It was very inefficient, but I liked that I could just see the primes as divots in an otherwise straight line.
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.
This is super cool! I haven't had the chance to study formulas like this yet, but it's amazing seeing what ones mind can come up with!
P.S. The way you formulated this video is amazing, it was well paced and very digestible, I could follow along despite my lack of knowledge so hats off to you! I hope you keep creating content, I love what you're doing!
Thank you! Glad you enjoyed it!
I hope more mathematicians pick something rather complicated looking and break it down like you did. It is so enlightening thank you so much.
Notably, Willans does describe the formulae presented in the article as "unsuitable for application to problems in prime number theory". ;)
Great step-by-step explanation of a very complicated-looking formula. Didn't know about the factorials' ability to identify primes, that was really interesting.
This reminds me of an idea I've had before, which is using contour integrals to factor integers. For example, the function f(z) = 1/(cos(2πz) + cos(2πn/z) - 2) has a pole precisely when z is an integer and n/z is an integer; i.e. when z is a factor of n. The integral of f(z) over a contour that encloses the range z = 2 to z = n-1 on the real axis would give the sum of the residues at each of the factors of n. If (say) n = pq, then the residues at z = p and z = q will be known expressions in terms of p and q, which would allow us to quickly solve for p and q. So factoring n is computationally equivalent to numerically integrating f(z) to high precision.
Unfortunately, this is an idea others have also had and it turns out f(z) has too many oscillations for fast numerical integration. In fact, trying to factor integers this way would likely be slower than trial division.
@Lanz Friszt Like, just for the name 😃
Really excellent two videos so far. I've shared both with some of my capable 17 year old high school students hoping to do mathematical degrees and it's very rare I can find videos on topics like this with good enough pedagogy that I feel they'll actually benefit. Up there with 3B1B. So impressed, hope there is more to come!
Thank you, that's great to hear! Yes, more are on the way...
Kinda unfair to 3b1b to claim others are equally good given that they literally use the same style of narration...and literally use the same visual scheme (ie manim).
@@Lolwutdesu9000 can you explain in more simplify launguage ?
I mean it's unfair to whom...?
To 3b1b or other CZcamsr who claims it?
@@Lolwutdesu9000Well, they put in a lot of effort to make a quality video as well. It's not like they stole a video idea from 3b1b or plagiarizing off from him... They just used his application which is free for all users.
@@Lolwutdesu9000 3b1b DID publicly release the software that HE created to make his mathematical videos with the express purpose of making it easier for anyone to make mathematical content. I think it worked.
I haven't seen anyone explaining Math so beautifully
These videos are stunningly amazing. Please keep making them!
I wasn't aware there was a formula for primes. Impressive! Mathematics is a really interesting field. The way they combine different theorems and formulas to make up new useful stuff is awesome.
This "formula" basically says "Oh, you want the nth prime? Let's check them one by one from 1 up to 2^n."
Again phenomenal video! I can't wait for more videos by you. I love the way you build your explanations. It makes it really easy to follow and understand the underlying principles. Keep it up!
Thank you so much!
It's cool seeing programming logic like this done with arithmetic. It feels very similar in theme to how computers are created, combining physical logic gates to create calculators, loops, and conditionals, which is then translated to complex computation.
Thank you for the two videos so far! Looking forward to other topics from your channel :)
CZcams threw this up on my feed, and despite failing at Maths in school, I found this bizarrely relaxing.
your first two videos are already so professional, I genuinely believe you can turn this into a lucrative business if you keep it up
Thanks! I am considering setting up a Patreon.
Uhh, well fuc ur computers
Fantastic video! Probably one of the best I have seen in terms of presentation and clarity. Step by step you took me from "this formula is impossible to understand" to "this makes perfect sense". Definitely keep up the great work!
Wow, I just stumbled upon this video via my youtube algorithm! I'm glad I did, this was a really fun and cool way to conceptualize formulas! I would love to see more videos!!!
Great explanation. Reminds me a bit of that other joke formula: the “formula of everything”, which can literally output, on a graph, any image, given the correct inputs. I think Standup Maths did a vid on that once.
This is beyond cool, I'm surprised that I haven't heard about this before!
Great explanation pace too, this was quite comfortable to follow along with :)
Beautiful exposition, beautifully illustrated.
The way you explained that hell of a formula..... You are gifted bro..... I understood everything
This presentation is absolutely perfect. Analysing the formula and then explaining it in layman's terms then bringing up the topic "what is an answer?" to show that it is not a very practical formula and then going on to tell us the actual takeaways from Willans' formula in just 14 mins that too with visual representations like graphs and all is simply amazing. Very engaging presentation!
Thank you!
1:30 (j − 1)!
1:40 (A + 1)/j
4:23 cosπB
5:11 C²
5:27 ⌊D⌋
5:46 Σⁱⱼ ₌ ₁E
7:16 (n/F)¹/ⁿ [there is no superscript
7:51 ⌊G⌋
9:43 Σ²ᵢ^₌ⁿ₁H
11:24 1 + I
(I know there are timestamps but this is for the prime factory's steps. Capital letters represent the step previous to another.)
ᐟ you can use this for a superscript "/"
@@vin0drath0re
/I am the one who knocks/
@@General12th bruh I didn't mean that
I'm in love with the way you explained this math formula. Thank you so much. I think I just learn a new way to look at math.
Such a good video! Very well put together and very easy to follow! Well done!
This gotta be my favorite math video on yt by far (and I like to watch math yt videos every day) . Thank you!
Wow, thanks!
you can write the floor function as x - 0.5 + (1/π)arctan(cot(πx)) if you want to completely avoid functions that are like computational functions.
but cot(pi•x) is not defined for integer values of x though.
Not only an interesting mathematical topic but an excellent presentation as well. Thank you.
Thanks, glad you liked it!
What a great video! I was under the impression from other content that there was really no way to calculate this. Thank you!
I think with hash tables you can greatly improve the performance... calculating n! is equal to n*(n-1)!, so you don't need to calculate the factorials each time and can reuse the values already calculated when looping over j.
Same for the 2^n summation, you don't need to use pow() function in each iteration over i.
Isn't that assuming that you've already calculated all the primes before the nth?
So what you say is true if you were using the formula to generate a list of "all" primes, but if you just wanted to jump to the 37th prime (say) you'd have to brute force it.
You'd still be able to just get a hash table from somewhere with values for factorials up to some number
for the 2^n a better upper bound could be used instead
@@boiii2148 in programming you would just stop the loop when hitting the first 0. Still none of it is nearly fast enough to actually reasonably count as a 'formula for the nth prime' but so many algorithms are orders of magnitude faster than this one still.
Wow! This is a truly fantabulous video, and would be a really fun thing to include in a discrete math or elementary number theory class. Thank you for sharing this!
This was a truly masterful explanation. Thank you so very, very much for sharing your insights!
Great explanation of a difficult topic! I'm impressed! Thank you!
I'm a bit late to the party, but you might be interested to know that there's a different formula for the prime numbers. You can find it in the book on Prime Numbers by Carl Pomerance, in the exercises for the first chapter. It's called the Gandhi formula or something. It's structured similarly, but works based off of the sieve of Eratosthenes rather than Wilson's Theorem.
Anyways, great video!
It might make people comfortable to call this a "formula", but I would consider this just to be an algorithm. The reason for this is that the computational complexity of the "formula" given is (quadraticically) exponential in the input. It's still cool, though, to see the algorithm has a "closed form" (including the floor function).
Your method of explain with the visuals are so amazing.
No clue why this was recommended to me next to my usual content, but hell, I loved it! Great video!
From a programming perspective, this formula isn't *that* bad. The factorial can be reduced to a single multiplication by using a running factorial variable (be careful of overflow!), the inner sum can likewise be a running sum so we don't recalculate all of our work again (be careful when multiplying by pi and using the cos function!), and finally we can end early when we detect a 0 in the outer sum since there's only 0s afterwards (this will happen at the nth prime!). This is now reduced to a single loop, but requires VERY large numbers VERY quickly. I coded this in Python for fun and the division fails when it uses the value of 19! when trying to calculate the 9th prime. Unlike the times at 1:18, this approach won't appear to hang at values close to 10.
This method only really works if you can accurately use large digit (more than 15) numbers in the division. It's also not much different than just starting at 2 and counting up how many primes you see with the detector function!
are there ways like newton's method where you take a guess then hone into the real value?
@@LegendLength Newton's method requires evaluating a function repeatedly, so it's even worse.
@@pierrecurie this also iterates though so it's a matter of how fast it approaches
You can fix the exponential upper bound to a more reasonable one too. Even 2n would be a massive improvement if not optimal. Using a number sieve is still more efficient though.
Rather than taking the whole formula implement the approach,we have if statements and loops to prevent the outer loop going out of hand or the inner one.
Your description of the “prime detector” at the start of the video is my go-to example for demonstrating how systems engineering approaches work for pure mathematics. Great video!
Well, the most straight-forward way to improve this algorithm to take at least sub-exponential time, would be to use, for example, the result of Pierre Dusart from 2016.
Pierre Dusart showed that for n >= 89693, there is at least one prime p in the interval: n < p
This explanation and the topic itself are great. Very well done
This is a great video, ty. [EDIT:] I really like your key observation -- that this is best viewed as a computer-algorithm *disguised as* a mathematical formula. This really serves to illustrate how different those things can be-- and maybe how different forms of symbolic representation naturally lend themselves to different purposes.
I'd love to see a series on dual numbers, their matrix representations, and how they work with complex numbers and higher dimensional systems like quaternions or octonions.
I'm still new to them and there aren't very many videos on the subject. I'm into comp sci and heard they have some great applications there.
Seconded. Maybe also one on Grassmann numbers more generally as well. The only videos on these subjects currently on CZcams are for the most part like actual full-length lectures geared toward an audience who are probably some ways into their math or physics degrees, it'd be really cool to see some more content on them that's more accessible to a wider viewership
What a beautiful video!
Very well explained and illustrated, thank you 🙏🏻
Beautifully explained with top-of-the-line editing and voiceover. Glad that youtube recommended me this gem of a channel. +1 sub
This absolutely blew my mind and totally made my evening!! When you claimed that this formula would spit out primes I audibly shouted that there was no way this would work. I have never seen this function or heard of Wilson's theorem. And the clever way mathematical functions were used to construct this piece of machinery is just amazing.
I was always impressed by how you could simply define and then magically decide to construct the dirac delta function (or unit impulse) by carefully squishing a curve and this reminds me of that, except this is even cooler. Man, it makes me wonder what other kind of crazy constructions people have come up with in this spirit!
🚀🚀🚀🚀🚀🚀
I am so disappointed that I didn't hear about it before, nobody told me of it... And everybody told me there's no formula...
This formula - although not elementary, so kind of fake - is at least mathematically valid, unlike the Dirac delta which is a total scam (much of the quantum physics is).
@@fatitankeris6327 I read that this only works up to n=40 in college. Maybe they showed me something else but I think it was this. Im about to go plug this into a computer and check.
I mean technically it is just the mathematical formal way of describing how you yourself would figure out what the n-th prime is with pen and paper (including some shortcuts like the prime detector that you wouldnt have easily come up with). So yeah technically you can formularize everything you can physically do with a mathematical formula but this one shows pretty well that not every result is a useful one...
WOW!
I am floored, this is basically as good as what 3B1B produces. The similarly well done animation adds to it, but really the pedagogy is what impressed me.
When the punchline came it conveyed -what I assume is- exactly the message you hoped to convey. As I had been perfectly primed with all the context I needed to vividly understand the deeper mathematical insight that you had prepared for me to "actually" walk away with. It hit me as if I had known it all along and was just waiting for someone to tell it to me - sliding into my understanding without any resistance.
I say this because I hope you continue making equally impressive videos. My time is clearly efficiently spent learning from you.
I'm shocked that there was a formula, and everybody on CZcams just said "there's still no formula"...
This is one of the most beautiful formulas I have ever seen, it’s probably my favourite now
People have been searching for a formula that computes primes for over 2000 years. Finally, we have one. This is a great achievement, no matter how quick or practical it is. Kudos to C.P. Williams!
*Willans
Yeah, efficiency is irrelevant. The article at the end was irrelevant. The only way for this formula to not be an answer is to change the question. I wonder if we can establish a rule that constructs functions that themselves pick the codomain within their images and are all in the same class such that the definition is not merely based on conjunctions.
It's the universal solution formula, aka brute force.
Not a mathematician, I’m trying to recreate this in Excel for the first 3 or 4 primes. The thinking that went into this formula is amazing and you explain it very well. I had never heard of floor and ceiling functions so learning how to use them was a treat
ABS function
Thank you eric, that's the kind of equations I avoided during my studies, as it was not necessary for my field and it looked way too scary. You make it easy to understand ! I always love getting insight in the way things are crafted, and you did an excellent job at that.
Thank you! Glad you enjoyed it!
This is a beautiful formula and a beautiful explanation
A few years ago I came up with my own version of this, using the floor function interestingly enough... By the time I verified my ‘recipe’ worked (I was traveling at the time) I realized that it was a bit vapid (in the sense that I had just created a kind of exhaustive algorithm and such a formula or method had undoubtedly already been discovered or used). I was studying PDEs (not number theory) and just filed the little result away and moved on to other things (though I did share some novel result on the floor function itself elsewhere). That all said, looking back at it now, it’s great to know that this method, result, algorithm has a good story behind it. Great video. 🤗
Can the floor function be decomposed into basic arithmetic?
@@Barnaclebeard It can be represented as a composition of one analytic function involving the imaginary unit and the natural logarithm. That’s the best I can do without looking into it again… Proved using Fourier Analysis.
Interesting stuff. The general idea I always heard is there is no known formula for generating the n’th prime, but the reality is there is no known efficient formula for generating the n’th prime. Reminds me of the discovery of a polynomial formula to determine if a number is prime, but people didn’t want to use it since it was inefficient.
There is a way to avoid using Bertrand Postulate, but at the cost of an enormous upper bound (just the first thing that came into my mind).
It sufficies to show that we can find an upper bound for p_n as a function of n. Let us proceed by using a very simple trick: product of first n primes plus 1 must be divisible by prime p_k with k > n. So p1*... *pn + 1 >= p_{n+1}. Suppose that m is a minimal such number that p_m > 2^(2^m). It means that the inverse inequality is true for every j
This is my new favorite algorithm! Thanks so much for sharing.
Dude, your videos are amazing. I hope u keep going, this is up there with some of the best math content an CZcams
Thank you so much!
I didnt know there was a formula, kinda beautiful, I was waiting for the time in the video where you say "this formula is just an approximation" or something like that. Even if its not practical its astonishing
It uses a floor though. Totally ruins it
Fascinating stuff. Thank you!
Thanks for this beautiful presentation man!!
I've been looking at generating functions lately, and I started wondering if it would be possible to formula-ize certain algorithms. For example, 1/(1-r) symbolically represents the sum of an infinite geometric series, and when you solve that formula with a (convergent) value of r < 1, then you in essence sum up that infinite series, all at once.
That was a week or two ago. Then this video showed up. Talk about serendipity! Thank you for this video, it has given me a lot more to think about!!
Glad to hear it! Definitely serendipitous!
Remember this for your next math test. If your teacher asks what is the 10th prime, just give this formula & say that n = 10.
Excellent explanation, and conclusion.
Eric. Absolutely Brilliant. I studied Electrical Engineering back in the day, so we got a good immersion in Maths and Physics, and in later years using computer hardware and software to simulate and realize engineering solutions.
When you dropped the date of this publication at the end of the video, it all became crystal clear, in the late 70's I amazed myself by writing a game of space invaders (sort of) using a text editing language TECO, a decade earlier Willans must have heard of computation but being versed in maths came up with this. I can only imagine that this sort of thinking was was common place back then.
I could go on and on, but I stop and just say thanks Eric, I was an eye opening experience.
Thanks so much! That's great to hear!
I do remember graphing this formula in calculus 2. It was an attempt to tease out any useful visual structure or pattern that could've been potentially useful.... I remembered the structure and the formula, but hadn't remembered the application. (I am an an artist so I remember things visually more so than conceptually, syntactically, or emotionally, etc...) So yeah.... nothing of importance at the end of the day:/
Great that it had already made its way into some calculus classes!
XD
Wow. That’s awesome. I always thought there was no formula for primes. It’s unfortunate that the formula is inefficient.
This isn't what you'd usually think of as a formula it's more like a sieve program written in math which is pretty cool by itself.
Thanks for this explanation! Very insightful, and you explained it in an easily digestible manner. The graphics helped a lot. 10/10 mealtime video.
This formula may not be useful practically, but it is beautiful ! Wonderfully prepared video. Thanks for sharing.
time complexity of O( (n!)³ ), _...but a space complexity of O(1)_
That guy was a true genius, imagine what he could've done with our technology now days
Thank you for making this video. Understood without pain. Please make more videos. I have subscribed !
Your method of explanation is elegant! 😊👍
The best student of 3B1B academy! Keep it up!!
I got asked to write one in a programming test for a job interview.
I figured there was no real way to do it since primes are one of the hardest mathematical values to find hence why they're so valuable in cryptography.
So I answered the question by brute-forcing it, I had no idea what else I was to do.
did you get the job?
@@daruyami no, I never even got shortlisted
It was 4 years ago and I wasn't too keen on the company in the first place, it was a stepping stone in the job hunt
@@safebox36 there is an easier algorithm called sieve of erasthomus
@@piushpaul4880 I think you mean Eratosthenes. That method is rather impractical due to how much space you need and that you have to guess you've made the array(s) large enough to contain the nth prime.
The formula in this video can be simplified to a single loop with a running sum and running factorial to avoid redoing the denominator calculation over and over again. However, the factorial poses a problem as it will quickly overflow any datatype you use in most languages and since it's used in the division, this will still likely take longer than the sieve due to how long large number division can take.
@@zecuse Yea the sieve of Atkin is usually the best for performance, but it would be insanely difficult to do on an interview since it's not that intuitive.
Beautifully explained, well done
As someone with zero knowledge of math after and including calculus, I found these explanations were really easy to follow! Really good explanation!
I wonder, relatively speaking, how much more efficient this calculation can be made.
After all, p(n) < 2^n (for p(n) the nth prime) is obviously incredibly inefficient. There is the MUCH stronger bound
p(n) < n [ log n + log log n ]
just offhand, and I imagine there are even tighter bounds nowadays. I wonder just how much more efficient even that much could make the result.
That, or other things; Wilson's theorem is hardly the only thing you could use as a "prime detector," I imagine.
Biggest problem seems to be the factorial part that just grows incredibly fast (faster than exponentially). Dynamic Programming might help a little but still this would take a while and lots of memory. The nested loop is the final nail to the coffin.
But since I already talked about implementing in a programming language, just run the ((j-1)!+1)/j) part and check if it is a whole number (so instead of dividing, check if mod j returns 0). If yes, update some counter, else continue. Once your counter reaches n, you are done. As I said, you can speed up factorial calculation with dynamic programming.
Pseudo code:
nth_prime(n){
counter = 0
fac = 1
current_number = 2
while(counter
@@felixstuber8046 yep, it explodes pretty fast. 1000! ≈ 4.023 ∙ 10²⁵⁶⁷, which is hefty even for powerful cpus. While getting the 1000th prime using that other inefficient method, Sieve of Eratosthenes, takes a moderate computer only a few ms.
@@felixstuber8046 Yea there are so much better primality tests out there some of them are insanely fast (like O((logn)^12) or O((logn)^3 even) but they unfortunately rely on some conjectures still which makes them possibly invalid