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.
@@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.
this is the type of comment that I keep coming to RUclips 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... ~_~
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 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
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
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.
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.
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.
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..... 🤦♀
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!
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.
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.
@@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...
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!
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
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.
@@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)
@@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
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.
@@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.
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!
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).
@@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 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 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!
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.
@@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.
@@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.
"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 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.
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
@@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.
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.
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.
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.
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!
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.
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.
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
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
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! 🚀🚀🚀🚀🚀🚀
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.
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!
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!
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.
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.
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!
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
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 is the best stealth esolang programming video I've ever seen, lol. By the way, one thing I notice is that these "sneak arbitrary computation into closed formulas" things often seem to use the floor function, seems it's particularly useful for extracting the only bit of information you care about and throwing the rest away.
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.
@@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.
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
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).
Every time I get cocky "I know a lot of maths" you see an awesomely beautiful formula like this and then think "maybe not". Sure, inefficient as hell, but still, awesome
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.)
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.
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!!
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!
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!
This is precisely up my alley. I find using functions to produce formulas (no matter how silly they look or inefficient) in a way adjacent to that of coding wonderful. Excellent video!
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!
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.
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
The proof of Wilson's Theorem is surprisingly simple, learnt it in our 1st year maths course on numbers and sets. Wilson's Theorem: If p is a prime number, then (p-1)! ≡ -1 (mod p) Proof: We consider (p-1)! = (p-1)*...*3*2*1. Since p is prime, we can pair each element between 1 and p-1 with its unique inverse modulo p, also in this range. This is because of Bezout’s Theorem; we know all numbers n between 1 and p-1 satisfy hcf(n,p) = 1, so by Bezout’s Theorem there exist integers r,s such that rn + sp = 1, I.e. nr ≡ 1 (mod p), or r = inv(n) (mod p). A little caveat: Consider solving the quadratic modular equation x^2 ≡ 1 (mod p). So x^2 - 1 ≡ 0 (mod p) (x-1)(x+1) ≡ 0 (mod p) => x-1 ≡ 0 (mod p) or x+1 ≡ 0 (mod p) => x ≡ 1 (mod p) or x ≡ -1 (mod p) i.e x ≡ p-1 (mod p) Hence we see that 1 and p-1 are self-inverse elements modulo p, whereas all other elements 2 to p-2 contain a unique different modular inverse between 2 and p-2 also. We pair up the units: (p-1)! ≡ (2*inv(2)) (3*inv(3)) ... ((p-2)*inv(p-2))(1)(p-1) (mod p). So (p-1)! ≡ (1) (1) ... (1) (1) (p-1) (mod p). So (p-1)! ≡ p-1 (mod p) (p-1)! ≡ -1 (mod p) Q.E.D
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 RUclips 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
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. 🤗
@@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.
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 like how when I watched this video the first time, started to anyway, I didn't really saw how it end up would connecting to primes (didn't end up watching the video then). But now that It showed up in my feed again, a few months later, having taken a number theory course I immediately recognised that (j-1)! as an "indicator" of j being prime. Math really is beautiful, I like how number theory connects with Group theory. Earlier I never would've guessed that I would find a result like Wilson's Theorem "obvious", but knowing the proof now it couldn't be more intuitive
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 :)
What if I say, I have another formula to find the n-th prime (also by iteration) and/or to define the index of a prime number, but from 'the opposite' way that all the mathematicians do.
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:/
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!
I thought i wasn't going to like this because of hard math, but it turns out this formula is exactly how i like to code. Every if and ternary in my code is a slap in the face.
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.
@@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
@@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.
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
This reminds me of BRANCHLESS CODE. Using math formulae that naturally result in "branching" behavior instead of explicitly asking questions like "is x greater than y?" is a powerful tool on hardware that hates branches. My favorite branchless algorithm (not by me) is this elegant max(a,b) function: return a ^ ((a ^ b) & -(a < b)); It only works in older languages like C where (a < b) returns a number. In more modern languages like Java and C# boolean variables are not numbers any more so you can't plug them into a calculation like this. But there is another way that does work in modern languages: return a - ((a - b) & ((a - b) >> 31));
the main challenge of the proof at 8:45 is that we need to know that the function never goes above 2. this requires the critical points test, which requires that we differentiate the function, which is a bit of a problem when we have u^v where both u and v are functions of x. it is doable, just a lot more messy
It would just spit out infinity, if I read this right. taking an integral of the floor of cos^2 will always end up with 0, since that will always be 0 except for the finite points that it tries to return. Since those have 0 width and finite height, they won't contribute to the integral. If you try to be fancy and replace those spikes with proper impulse spikes, you would be left with garbage since you would have a lot of false positives, as (gamma(x)+1)/x is a smooth function and there is a lot of integers that it must cross between primes. It might be interesting to see what other properties those false positives end up with though.
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!!!
As I understood it, the key building block is actually Wilson’s theorem because other parts of the formulas are some sort of intermediate steps that lead to the final objective.
It's not actually that surprising that we can make a programming language out of arithmetic operations -- all you need to create a Turing-complete language is Boolean algebra, which is essentially just a more convenient version of propositional logic. The only operations you need are logical AND (boolean algebra multiplication), OR (addition), and NOT. All the complexity of modern computers, every algorithm the computer implements, can, in principle, be modeled using a system with just those three operations. Of course, in reality, trying to actually do this would be equivalent to trying to write a complicated and high-level piece of software directly in machine code -- possible in theory but utterly impractical and completely unnecessary.
Don’t you also need at least one conditional jump instruction? After all, a Türing Machine is defined as an infinite tape where you go forward and backward based on a condition. For instance, SBN (Subtract and Branch if Negative) is a Türing Complete system.
@@Misteribel You can create conditional statements using AND, OR, and NOT, or, as someone else pointed out, using just NAND (negation of AND) or just NOR (negation of OR). It's an XOR (exclusive OR) circuit. You can easily find examples online if you're curious how to build XOR.
@@Lucky10279 of course, it’s trivial to do that. You can have a conditional statement, but what I meant is, after the condition, you’d need to execute the next statement, or skip it. I may be missing something, but afaik, any Türing Machine must have some form of IO. Ah, I’m conflating language and machine.
@@Misteribel @Misteribel I'm not quite sure what you're asking about. The whole _point_ of an if statement is that it determines whether or not the following instruction is executed or not. If you're actually asking about loops, those are implement using flip-flops circuits or something similar, which can easily be modeled via Boolean algebra. If you're asking how IO is handled, I believe that's usually separate from the logic of the machine itself, as we want to be able to use the same computer architecture with a variety of different IO devices. Obviously most laptops, for example, have a keyboard and trackpad built-in, but they can, I believe, use the same basic hardware design for the CPU, etc., as desktops because _HOW_ the input signals are received is independent of that design. Of course, the actual IO hardware itself (e.g. keyboard, mouse, or touchscreen) will probably _also_ use digital circuits which can also be modeled via Boolean algebra. Although, I should note that using Boolean algebra directly is really only useful when we're talking about a small and relatively simple circuit. If we're talking about something more complicated, while we _could,_ in theory, use Boolean algebra, in practice it's much easier and makes for better communication to either use diagrams with symbols for common simpler circuits or to use a hardware design/description language such as Verilog. When I took a course on digital logic design, we started out directly using the symbols for AND, OR, and NOT, and writing out logical statements the way you would in an intro course on logic. We did that for a week, then switched to Boolean algebra, which I immediately loved because it was _so_ much easier to parse Boolean algebra expressions than the equivalent expressions written in logic notation. Then we gradually started using actual circuit diagrams and different kinds of charts, such as k-maps.
13:00 bahahahahaha i love it. its like a really weird practical joke: "hey bro, I gotta formula for all the primes. naw really, try to compute the first 100 primes with it, just to test it out" its like the pull my finger bit, but extra rediculous
For natural numbers i, j and n>j there exist a product function from i=2 to i=n-1 [sin (pi*n/i)] which is different than 0 and it is a prime number. For such function there is also true that: P= sum j=3 to j=n from [product function from i=2 to i=n-1 psin (pi*n/i)]/product function from i=2 to i=n-1 [sin (pi*n/i)] where P+1 is the order of prime number (O.O.P.N.) which also can be written as O.O.P.N. =1 + sum j=3 to j=n from [product function from i=2 to i=n-1 psin (pi*n/i)]/product function from i=2 to i=n-1 [sin (pi*n/i)] We also must add number 2 as a 1st prime as an axiom to complete this formula.
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 RUclips 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!
He didn't find a suitable programming language so he decided to use math as one.
LOL
ALGOL was around from 1958. That could have done the job. I guess you would need to construct the Cos with a Taylor series.
Yeah that's true. Mathematics is the most powerful programming language. The entirety of the universe is governed by it.
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.
"when not expanded" induces primal fear in a mf like no other stimuli
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
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!
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...
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!
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 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
Love it! Your way of narration is excellent, the pacing really on point. Keep it up. ✨
Thank you so much!
Notably, Willans does describe the formulae presented in the article as "unsuitable for application to problems in prime number theory". ;)
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.
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 RUclipsr 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.
RUclips threw this up on my feed, and despite failing at Maths in school, I found this bizarrely relaxing.
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."
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!
This video is an absolute beauty. It should be shown to each and every math student in the world. Kudos!
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.
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?
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.
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.
I haven't seen anyone explaining Math so beautifully
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 😃
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
I hope more mathematicians pick something rather complicated looking and break it down like you did. It is so enlightening thank you so much.
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!
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 gotta be my favorite math video on yt by far (and I like to watch math yt videos every day) . Thank you!
Wow, thanks!
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 RUclips just said "there's still no formula"...
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
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
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.
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!
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!
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.
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.
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!
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
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 is the best stealth esolang programming video I've ever seen, lol.
By the way, one thing I notice is that these "sneak arbitrary computation into closed formulas" things often seem to use the floor function, seems it's particularly useful for extracting the only bit of information you care about and throwing the rest away.
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.
Excellent. Remarkably clever even if it is "useless" as you say.
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.
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
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).
Every time I get cocky "I know a lot of maths" you see an awesomely beautiful formula like this and then think "maybe not". Sure, inefficient as hell, but still, awesome
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
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.
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!
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!
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!
This is precisely up my alley. I find using functions to produce formulas (no matter how silly they look or inefficient) in a way adjacent to that of coding wonderful. Excellent video!
Dude, your videos are amazing. I hope u keep going, this is up there with some of the best math content an RUclips
Thank you so much!
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.
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
Remember this for your next math test. If your teacher asks what is the 10th prime, just give this formula & say that n = 10.
The proof of Wilson's Theorem is surprisingly simple, learnt it in our 1st year maths course on numbers and sets.
Wilson's Theorem: If p is a prime number, then (p-1)! ≡ -1 (mod p)
Proof: We consider (p-1)! = (p-1)*...*3*2*1. Since p is prime, we can pair each element between 1 and p-1 with its unique inverse modulo p, also in this range. This is because of Bezout’s Theorem; we know all numbers n between 1 and p-1 satisfy hcf(n,p) = 1, so by Bezout’s Theorem there exist integers r,s such that rn + sp = 1, I.e.
nr ≡ 1 (mod p), or r = inv(n) (mod p). A little caveat:
Consider solving the quadratic modular equation
x^2 ≡ 1 (mod p). So
x^2 - 1 ≡ 0 (mod p)
(x-1)(x+1) ≡ 0 (mod p)
=> x-1 ≡ 0 (mod p) or x+1 ≡ 0 (mod p)
=> x ≡ 1 (mod p) or x ≡ -1 (mod p) i.e x ≡ p-1 (mod p)
Hence we see that 1 and p-1 are self-inverse elements modulo p, whereas all other elements 2 to p-2 contain a unique different modular inverse between 2 and p-2 also. We pair up the units:
(p-1)! ≡ (2*inv(2)) (3*inv(3)) ... ((p-2)*inv(p-2))(1)(p-1) (mod p). So
(p-1)! ≡ (1) (1) ... (1) (1) (p-1) (mod p). So
(p-1)! ≡ p-1 (mod p)
(p-1)! ≡ -1 (mod p)
Q.E.D
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.
As someone with zero knowledge of math after and including calculus, I found these explanations were really easy to follow! Really good explanation!
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 RUclips 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
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.
Great video and explanation, loved it. I'm a mechanical engineer but I also love computer science and math so this video was perfect for me
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.
It is a clever way to work around limitations of mathematical formulation for something trivial to represent in any programming language.
what programming language do you use? Math++
I like how when I watched this video the first time, started to anyway, I didn't really saw how it end up would connecting to primes (didn't end up watching the video then). But now that It showed up in my feed again, a few months later, having taken a number theory course I immediately recognised that (j-1)! as an "indicator" of j being prime. Math really is beautiful, I like how number theory connects with Group theory. Earlier I never would've guessed that I would find a result like Wilson's Theorem "obvious", but knowing the proof now it couldn't be more intuitive
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 :)
This came up in my recommended videos, a minute or so in, I said "this guy sounds familiar"... sure enough, my Calc II professor from 2010.
Hi, Ian!
That guy was a true genius, imagine what he could've done with our technology now days
What if I say, I have another formula to find the n-th prime (also by iteration) and/or to define the index of a prime number, but from 'the opposite' way that all the mathematicians do.
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
My grandfather used to work in a prime factory in the 60's. Of course, they all moved overseas long ago.
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!
I thought i wasn't going to like this because of hard math, but it turns out this formula is exactly how i like to code. Every if and ternary in my code is a slap in the face.
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.
The way you explained that hell of a formula..... You are gifted bro..... I understood everything
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
This reminds me of BRANCHLESS CODE. Using math formulae that naturally result in "branching" behavior instead of explicitly asking questions like "is x greater than y?" is a powerful tool on hardware that hates branches. My favorite branchless algorithm (not by me) is this elegant max(a,b) function:
return a ^ ((a ^ b) & -(a < b));
It only works in older languages like C where (a < b) returns a number. In more modern languages like Java and C# boolean variables are not numbers any more so you can't plug them into a calculation like this. But there is another way that does work in modern languages:
return a - ((a - b) & ((a - b) >> 31));
This formular is very impressive! 7:31 is there a reason why you write power of 1/n when you could just write the n-th root? That's the same.
Yes, it’s the same. I wrote it this way just for typographic reasons, to have the 1/n in one small area rather than a large root sign.
Intersection graphics worked great for me and I finally understood a math video on youtube.
One thing of note is that this formula (kinda) implies that the 0th prime is 1.
0:29 this pi sitting there is kinda obvious. it makes the cos have a period of 2
The best student of 3B1B academy! Keep it up!!
the main challenge of the proof at 8:45 is that we need to know that the function never goes above 2. this requires the critical points test, which requires that we differentiate the function, which is a bit of a problem when we have u^v where both u and v are functions of x. it is doable, just a lot more messy
What do you get if you replace the sums with integrals and the factorial with the gamma function?
It would just spit out infinity, if I read this right. taking an integral of the floor of cos^2 will always end up with 0, since that will always be 0 except for the finite points that it tries to return. Since those have 0 width and finite height, they won't contribute to the integral. If you try to be fancy and replace those spikes with proper impulse spikes, you would be left with garbage since you would have a lot of false positives, as (gamma(x)+1)/x is a smooth function and there is a lot of integers that it must cross between primes. It might be interesting to see what other properties those false positives end up with though.
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!!!
this made for a pretty fun little 5 minute python project
I need this video for every formula in existence
Bro chose math as a coding language 💀
Coding is just math
@@ReCamHead everything is math
As I understood it, the key building block is actually Wilson’s theorem because other parts of the formulas are some sort of intermediate steps that lead to the final objective.
It's not actually that surprising that we can make a programming language out of arithmetic operations -- all you need to create a Turing-complete language is Boolean algebra, which is essentially just a more convenient version of propositional logic. The only operations you need are logical AND (boolean algebra multiplication), OR (addition), and NOT. All the complexity of modern computers, every algorithm the computer implements, can, in principle, be modeled using a system with just those three operations.
Of course, in reality, trying to actually do this would be equivalent to trying to write a complicated and high-level piece of software directly in machine code -- possible in theory but utterly impractical and completely unnecessary.
You don't even need three operations, you need one, which is NAND. you can create all and, or and not operations using it.
Don’t you also need at least one conditional jump instruction? After all, a Türing Machine is defined as an infinite tape where you go forward and backward based on a condition. For instance, SBN (Subtract and Branch if Negative) is a Türing Complete system.
@@Misteribel You can create conditional statements using AND, OR, and NOT, or, as someone else pointed out, using just NAND (negation of AND) or just NOR (negation of OR). It's an XOR (exclusive OR) circuit. You can easily find examples online if you're curious how to build XOR.
@@Lucky10279 of course, it’s trivial to do that. You can have a conditional statement, but what I meant is, after the condition, you’d need to execute the next statement, or skip it. I may be missing something, but afaik, any Türing Machine must have some form of IO. Ah, I’m conflating language and machine.
@@Misteribel @Misteribel I'm not quite sure what you're asking about. The whole _point_ of an if statement is that it determines whether or not the following instruction is executed or not.
If you're actually asking about loops, those are implement using flip-flops circuits or something similar, which can easily be modeled via Boolean algebra. If you're asking how IO is handled, I believe that's usually separate from the logic of the machine itself, as we want to be able to use the same computer architecture with a variety of different IO devices. Obviously most laptops, for example, have a keyboard and trackpad built-in, but they can, I believe, use the same basic hardware design for the CPU, etc., as desktops because _HOW_ the input signals are received is independent of that design. Of course, the actual IO hardware itself (e.g. keyboard, mouse, or touchscreen) will probably _also_ use digital circuits which can also be modeled via Boolean algebra.
Although, I should note that using Boolean algebra directly is really only useful when we're talking about a small and relatively simple circuit. If we're talking about something more complicated, while we _could,_ in theory, use Boolean algebra, in practice it's much easier and makes for better communication to either use diagrams with symbols for common simpler circuits or to use a hardware design/description language such as Verilog.
When I took a course on digital logic design, we started out directly using the symbols for AND, OR, and NOT, and writing out logical statements the way you would in an intro course on logic. We did that for a week, then switched to Boolean algebra, which I immediately loved because it was _so_ much easier to parse Boolean algebra expressions than the equivalent expressions written in logic notation. Then we gradually started using actual circuit diagrams and different kinds of charts, such as k-maps.
13:00 bahahahahaha i love it. its like a really weird practical joke: "hey bro, I gotta formula for all the primes. naw really, try to compute the first 100 primes with it, just to test it out"
its like the pull my finger bit, but extra rediculous
For natural numbers i, j and n>j there exist a product function from i=2 to i=n-1 [sin (pi*n/i)] which is different than 0 and it is a prime number.
For such function there is also true that:
P= sum j=3 to j=n from [product function from i=2 to i=n-1 psin (pi*n/i)]/product function from i=2 to i=n-1 [sin (pi*n/i)]
where P+1 is the order of prime number (O.O.P.N.)
which also can be written as
O.O.P.N. =1 + sum j=3 to j=n from [product function from i=2 to i=n-1 psin (pi*n/i)]/product function from i=2 to i=n-1 [sin (pi*n/i)]
We also must add number 2 as a 1st prime as an axiom to complete this formula.
Despite its inefficiency, this formula remains a conceptually magnificent tinkering.
Seeing this all come together is truly amazing! A formular for primes? Imagine what this guy was on developing this. 😅