An Exact Formula for the Primes: Willans' Formula

Поділитися
Вставка
  • Опубліковано 27 бер 2024
  • Formulas for the nth prime number actually exist! One was cleverly engineered in 1964 by C. P. Willans. But is it useful?
    ----------------
    References:
    Herbert Wilf, What is an answer?, The American Mathematical Monthly 89 (1982) 289-292.
    doi.org/10.1080/00029890.1982...
    C. P. Willans, On formulae for the nth prime number, The Mathematical Gazette 48 (1964) 413-415.
    doi.org/10.2307/3611701
    Further reading:
    Jeffrey Shallit, No formula for the prime numbers?.
    recursed.blogspot.com/2013/01/...
    ----------------
    Python code
    import math
    def prime(n):
    return 1 + sum([
    math.floor(pow(n/sum([
    math.floor(pow(math.cos(math.pi * (math.factorial(j - 1) + 1)/j), 2))
    for j in range(1, i+1)
    ]), 1/n))
    for i in range(1, pow(2, n)+1)
    ])
    ----------------
    (* Mathematica code *)
    prime[n_] := 1 + Sum[Floor[(n/Sum[Floor[Cos[Pi ((j - 1)! + 1)/j]^2], {j, 1, i}])^(1/n)], {i, 1, 2^n}]
    ----------------
    0:00 A formula for primes?
    1:24 Engineering a prime detector
    4:00 Improving the prime detector
    5:46 Counting primes
    6:29 Determining the nth prime
    9:42 The final step
    11:36 What counts as a formula?
    12:56 What's the point?
    13:51 Who was Willans?
    ----------------
    Animated with Manim. www.manim.community
    Thanks to Ken Emmer for supplying the microphone.
    Web site: ericrowland.github.io
    Twitter: / ericrowland

КОМЕНТАРІ • 1,8 тис.

  • @MrDannyDetail
    @MrDannyDetail Рік тому +3281

    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
      @EricRowland  Рік тому +874

      Thanks so much for spending some time on this! So the current best guess seems to be Christopher Paul Willans (1942-1971).

    • @MrDannyDetail
      @MrDannyDetail Рік тому +598

      @@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.

    • @Poppp
      @Poppp Рік тому +132

      Wow you really did your work

    • @MrBLAA
      @MrBLAA Рік тому +27

      All things “”complex””~>
      should be simple😉
      We all know it… just never accept it

    • @kurzackd
      @kurzackd Рік тому +77

      this is the type of comment that I keep coming to UA-cam 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... ~_~

  • @jakebrusca49
    @jakebrusca49 Рік тому +3874

    I’m pretty sure C. P. Stands for coolformulaforcalculating primes

    • @vnever9078
      @vnever9078 Рік тому +292

      Mr. Coolformulaforcalculating 'Primes' Willans

    • @jjmccurdy314channel
      @jjmccurdy314channel Рік тому +89

      Hmmmmmmmm

    • @kingoreo7050
      @kingoreo7050 Рік тому +390

      cp might stand for something else

    • @alexismiller2349
      @alexismiller2349 Рік тому +20

      At a glance that looks like generatingfunctionology, which happens to be a famous book from Herbert Wilf who coincidentally appears in this video

    • @manvithbhandary2081
      @manvithbhandary2081 Рік тому +62

      @@kingoreo7050 sus

  • @tolstoj_
    @tolstoj_ Рік тому +2563

    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.

    • @nonchip
      @nonchip Рік тому +51

      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

    • @theendofthestart8179
      @theendofthestart8179 Рік тому

      All he did was explain it tho

    • @puppergump4117
      @puppergump4117 Рік тому

      I still don't know why j is there

    • @marcdeusxtetris877
      @marcdeusxtetris877 Рік тому +5

      I totally agree. It all started making so much sense, when he explained it step by step

    • @martynconkling8876
      @martynconkling8876 Рік тому +12

      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!

  • @gblargg
    @gblargg Рік тому +2246

    The floor function is the key here. It's basically a conditional.

    • @EinChris75
      @EinChris75 Рік тому +476

      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...)

    • @benr3799
      @benr3799 Рік тому +70

      I’ve never heard of a floor function but it looks hella useful lmao

    • @hcasavantes
      @hcasavantes Рік тому +50

      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

    • @rorke6092
      @rorke6092 Рік тому +125

      Learning the floor function for the first time, I remember thinking floor and cieling functions felt different, almost like cheating or non-math

    • @ferociousfeind8538
      @ferociousfeind8538 Рік тому +36

      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())

  • @omp199
    @omp199 Рік тому +1707

    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.

    • @globalincident694
      @globalincident694 Рік тому +152

      willans would be proud

    • @el_saltamontes
      @el_saltamontes Рік тому +107

      Died with the last joke, good one XD

    • @davidemmanuel9418
      @davidemmanuel9418 Рік тому +27

      LoL 😂, obviously fake but I dare you to make a video about it

    • @coolorphans
      @coolorphans Рік тому +5

      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..... 🤦‍♀

    • @thefrog4772
      @thefrog4772 Рік тому +123

      @@coolorphans
      r/woooosh

  • @AndreasHontzia
    @AndreasHontzia Рік тому +876

    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.

    • @Moonz97
      @Moonz97 Рік тому +15

      Is there a name for this process?

    • @rosiefay7283
      @rosiefay7283 Рік тому +70

      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.

    • @AndreasHontzia
      @AndreasHontzia Рік тому +58

      @@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.

    • @marcliebhardt1793
      @marcliebhardt1793 Рік тому +34

      @@Moonz97 You should look up „branchless programming“. It‘s definitly not the name for the process, but in my opinion the idea ist similar.

    • @alainzscheile6913
      @alainzscheile6913 Рік тому +11

      @@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...

  • @iamsushi1056
    @iamsushi1056 Рік тому +210

    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.

    • @geekjokes8458
      @geekjokes8458 Місяць тому +1

      where is it from? and what do you mean "when not expanded"?

    • @TimJSwan
      @TimJSwan 18 днів тому

      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.

  • @uhbayhue
    @uhbayhue Рік тому +36

    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!

  • @muskyoxes
    @muskyoxes Рік тому +63

    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

    • @nathannathan44
      @nathannathan44 Рік тому +4

      Exactly.

    • @locomotivetrainstation6053
      @locomotivetrainstation6053 Рік тому +4

      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

  • @sugarfrosted2005
    @sugarfrosted2005 Рік тому +449

    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.

    • @EricRowland
      @EricRowland  Рік тому +93

      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.

    • @ValkyRiver
      @ValkyRiver Рік тому +16

      @@EricRowland Is arithmetic turing complete?

    • @globalincident694
      @globalincident694 Рік тому +4

      @@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

    • @schwingedeshaehers
      @schwingedeshaehers Рік тому +13

      @@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)

    • @pierrecurie
      @pierrecurie Рік тому +7

      @@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.

  • @Cynthia_Cantrell
    @Cynthia_Cantrell Рік тому +58

    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!

  • @verr12
    @verr12 Рік тому +149

    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!

    • @EricRowland
      @EricRowland  Рік тому +19

      Thank you, that's great to hear! Yes, more are on the way...

    • @Lolwutdesu9000
      @Lolwutdesu9000 Рік тому +5

      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).

    • @xninja2369
      @xninja2369 Рік тому +3

      @@Lolwutdesu9000 can you explain in more simplify launguage ?
      I mean it's unfair to whom...?
      To 3b1b or other UA-camr who claims it?

    • @Memories_broken_
      @Memories_broken_ 7 місяців тому

      ​@@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.

    • @kindlin
      @kindlin 6 днів тому

      @@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.

  • @Spulg
    @Spulg Рік тому +535

    Love it! Your way of narration is excellent, the pacing really on point. Keep it up. ✨

  • @hungrystork7252
    @hungrystork7252 Рік тому +275

    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
      @LegendLength Рік тому +1

      @@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.

    • @bobaGogo
      @bobaGogo Рік тому +4

      @@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.

    • @raskr8137
      @raskr8137 Рік тому +15

      @@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.

    • @artembaguinski9683
      @artembaguinski9683 Рік тому +1

      @@bobaGogo there is almost a way: en.wikipedia.org/wiki/Floor_and_ceiling_functions#Continuity_and_series_expansions

    • @raresaturn
      @raresaturn Рік тому +1

      Are the 1's and 0's always consecutive? could you stop after hitting the first zero?

  • @sebastiangudino9377
    @sebastiangudino9377 Рік тому +116

    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.

    • @itismethatguy
      @itismethatguy Рік тому +3

      Wow man that's reallly cool

    • @cameron7374
      @cameron7374 Рік тому +4

      "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.

    • @sebastiangudino9377
      @sebastiangudino9377 Рік тому +2

      @@cameron7374 Yup, I really really love set theory just because of that

    • @dfeuer
      @dfeuer Рік тому +5

      ​@@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.

    • @blemmyes
      @blemmyes Рік тому

      Same. I recommend trying out the Haskell programming language - the overall thought process is quite similar to that of Desmos.

  • @toufique3390
    @toufique3390 Рік тому +13

    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!

  • @nicholasouellette
    @nicholasouellette Рік тому +193

    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!

  • @oscarhalse2026
    @oscarhalse2026 Рік тому +16

    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.

    • @fatitankeris6327
      @fatitankeris6327 Рік тому +1

      I'm shocked that there was a formula, and everybody on UA-cam just said "there's still no formula"...

  • @AlessandroBottoni
    @AlessandroBottoni Рік тому +15

    This video is an absolute beauty. It should be shown to each and every math student in the world. Kudos!

  • @oystercatcher943
    @oystercatcher943 Рік тому +5

    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

  • @veni1
    @veni1 Рік тому +9

    your first two videos are already so professional, I genuinely believe you can turn this into a lucrative business if you keep it up

  • @shahzaibhassan2777
    @shahzaibhassan2777 2 місяці тому +4

    I haven't seen anyone explaining Math so beautifully

  • @johanneskarlsson6535
    @johanneskarlsson6535 Рік тому +33

    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!
    🚀🚀🚀🚀🚀🚀

    • @fatitankeris6327
      @fatitankeris6327 Рік тому +2

      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...

    • @piotrkozbial8753
      @piotrkozbial8753 Рік тому

      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).

    • @alext5497
      @alext5497 Рік тому

      @@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.

    • @dr3v1l1993
      @dr3v1l1993 Рік тому +3

      I mean technically it is just the mathematical formal way of describing how you yourself would figure out what the n-th prime is with pen and paper (including some shortcuts like the prime detector that you wouldnt have easily come up with). So yeah technically you can formularize everything you can physically do with a mathematical formula but this one shows pretty well that not every result is a useful one...

  • @jeffanderson5396
    @jeffanderson5396 Рік тому +56

    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.

  • @tracythomas132
    @tracythomas132 Рік тому +4

    UA-cam threw this up on my feed, and despite failing at Maths in school, I found this bizarrely relaxing.

  • @johnchessant3012
    @johnchessant3012 Рік тому +63

    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.

    • @hansfranz1069
      @hansfranz1069 Рік тому +1

      @Lanz Friszt Like, just for the name 😃

  • @Kurtlane
    @Kurtlane Рік тому +12

    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!

    • @ipudisciple
      @ipudisciple Рік тому +5

      *Willans

    • @montralanca
      @montralanca 9 днів тому +1

      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.

  • @giannismentz3570
    @giannismentz3570 Рік тому +11

    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.

    • @borissinaga
      @borissinaga 3 місяці тому +2

      This "formula" basically says "Oh, you want the nth prime? Let's check them one by one from 1 up to 2^n."

  • @tropfen
    @tropfen Рік тому +23

    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!

  • @Creepyslandofdreams
    @Creepyslandofdreams Рік тому +308

    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
      @AndrewBlucher Рік тому +15

      You have it upside down. Computer "science" is not science, it's Mathematics.

    • @Creepyslandofdreams
      @Creepyslandofdreams Рік тому +10

      @@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)

    • @AndrewBlucher
      @AndrewBlucher Рік тому +7

      @@Creepyslandofdreams Oh, there's no doubt that it's a field of study. Just not a science, just as mathematics is not a science.

    • @ahuman32478
      @ahuman32478 Рік тому +8

      @@AndrewBlucher Anything is considered a science nowadays, like history, sociology, economics, and other social “sciences”

    • @AndrewBlucher
      @AndrewBlucher Рік тому +1

      @@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

  • @krumpy8259
    @krumpy8259 Рік тому +2

    I hope more mathematicians pick something rather complicated looking and break it down like you did. It is so enlightening thank you so much.

  • @mathiasriedel6228
    @mathiasriedel6228 Рік тому +11

    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!

  • @omega4959
    @omega4959 Рік тому +4

    This gotta be my favorite math video on yt by far (and I like to watch math yt videos every day) . Thank you!

  • @spase667
    @spase667 Рік тому +6

    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.

  • @yumnuska
    @yumnuska Рік тому +1

    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!

  • @mr_clean575
    @mr_clean575 6 місяців тому +3

    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.

  • @martinshoosterman
    @martinshoosterman Рік тому +3

    it's so awesome to see such an intractable looking formula made so easy to understand when broken down slowly into small pieces.

  • @Misteribel
    @Misteribel Рік тому +13

    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.

  • @aditya95sriram
    @aditya95sriram Рік тому +2

    Quality content, very underrated, but looking at some of the other comments there's a good chance you can reach an audience beyond just the people who are comfortable with this sort of stuff. So glad youtube recommended it. Keep it up!

  • @mrdraw2087
    @mrdraw2087 Рік тому +6

    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.

  • @10sTinTh0uGhT
    @10sTinTh0uGhT Рік тому +22

    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!

  • @DavidSartor0
    @DavidSartor0 Рік тому +145

    I think probably difficulty was hidden in Wilson's Theorem. It would have been nice to see an outline of a proof for it.

    • @EricRowland
      @EricRowland  Рік тому +48

      Thanks, I’ll consider that for a possible future video topic!

    • @alexismiller2349
      @alexismiller2349 Рік тому +12

      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

    • @Tletna
      @Tletna Рік тому +3

      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.

    • @mironhunia300
      @mironhunia300 Рік тому +18

      ​@@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

    • @lgooch
      @lgooch Рік тому

      The proof is actually pretty easy, there are videos on yt that cover it

  • @javonfair
    @javonfair Рік тому +6

    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

    • @cyberpass
      @cyberpass 8 місяців тому +1

      ABS function

  • @SteveAcomb
    @SteveAcomb Рік тому +6

    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!

  • @einschwein375
    @einschwein375 Рік тому +12

    Dude, your videos are amazing. I hope u keep going, this is up there with some of the best math content an UA-cam

  • @IngresaElNombreDelCanal
    @IngresaElNombreDelCanal Рік тому +54

    I feel like the floor function is some kind of "cheat" for algebraic operations. It's basically using an if statement

    • @EricRowland
      @EricRowland  Рік тому +35

      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.

    • @atlas_19
      @atlas_19 Рік тому +8

      I feel like we need more of these. Taking the sign of a number is unnecessarily bothersome without the sign() function.

    • @jonorgames6596
      @jonorgames6596 Рік тому

      @@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.

    • @calvindang7291
      @calvindang7291 Рік тому +16

      @@jonorgames6596 A function has a very clearly defined definition in mathematics, until people call something that isn't a function a function anyway.

    • @BainesMkII
      @BainesMkII Рік тому +7

      @@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.

  • @MrCheeze
    @MrCheeze Рік тому +1

    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.

  • @reallyWyrd
    @reallyWyrd Рік тому +2

    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.

  • @chris-hu7tm
    @chris-hu7tm Рік тому +3

    I didnt know there was a formula, kinda beautiful, I was waiting for the time in the video where you say "this formula is just an approximation" or something like that. Even if its not practical its astonishing

    • @janisir4529
      @janisir4529 Рік тому

      It uses a floor though. Totally ruins it

  • @danielkishazi2751
    @danielkishazi2751 Рік тому +23

    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.

    • @matthewcooke4011
      @matthewcooke4011 Рік тому +4

      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.

    • @meable3763
      @meable3763 10 місяців тому

      You'd still be able to just get a hash table from somewhere with values for factorials up to some number

    • @boiii2148
      @boiii2148 8 місяців тому

      for the 2^n a better upper bound could be used instead

    • @dekippiesip
      @dekippiesip 5 місяців тому

      ​@@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.

  • @DevanshGuptaChess
    @DevanshGuptaChess 10 місяців тому

    Beautifully explained with top-of-the-line editing and voiceover. Glad that youtube recommended me this gem of a channel. +1 sub

  • @KarelSeeuwen
    @KarelSeeuwen Рік тому

    Eric. Absolutely Brilliant. I studied Electrical Engineering back in the day, so we got a good immersion in Maths and Physics, and in later years using computer hardware and software to simulate and realize engineering solutions.
    When you dropped the date of this publication at the end of the video, it all became crystal clear, in the late 70's I amazed myself by writing a game of space invaders (sort of) using a text editing language TECO, a decade earlier Willans must have heard of computation but being versed in maths came up with this. I can only imagine that this sort of thinking was was common place back then.
    I could go on and on, but I stop and just say thanks Eric, I was an eye opening experience.

    • @EricRowland
      @EricRowland  Рік тому +1

      Thanks so much! That's great to hear!

  • @zhru-kq6in
    @zhru-kq6in 11 місяців тому +6

    He didn't find a suitable programming language so he decided to use math as one.

  • @ed.puckett
    @ed.puckett Рік тому +17

    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!!

    • @EricRowland
      @EricRowland  Рік тому +1

      Glad to hear it! Definitely serendipitous!

  • @SpiderMan-hb7nr
    @SpiderMan-hb7nr Рік тому

    The way you explained that hell of a formula..... You are gifted bro..... I understood everything

  • @briannguyen6994
    @briannguyen6994 Рік тому +2

    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!!!

  • @matthewpassage65536
    @matthewpassage65536 Рік тому +3

    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 :)

  • @brianmccormick8328
    @brianmccormick8328 Рік тому +5

    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.

  • @yanntal954
    @yanntal954 3 місяці тому +1

    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

  • @backwashjoe7864
    @backwashjoe7864 Рік тому

    Excellent video! I paused it after the first minute and dove into the formula myself. What a fun journey that was! I implemented the algorithm in a spreadsheet, and figured out what the parts were doing. And my gosh it works, lol! Now the cool part is, watching the rest of the video was still illuminating. I'll echo others here in the comments that your pacing and graphics and explanations and organization are outstanding! You gave such great structure to how the parts fit together in this formula, each step along the way. That showed it to me in a whole new, better light. Thanks!
    Also, it struck me that this would be perfect for Grant's SoME2, and then I see that your other video was submitted to that. I am not surprised! Now to go watch that one, and Grant's SoME2 wrap up video. :)

    • @EricRowland
      @EricRowland  Рік тому

      Great to hear you experimented with the formula!

    • @backwashjoe7864
      @backwashjoe7864 Рік тому +1

      @@EricRowland Thanks! The hardest part was making myself stop and climb back out of the rabbit hole, lol. I choose to turn around when I started planning how to calculate cosine from the very large ((j - 1)! + 1) / j that my spreadsheet failed to get right. For example, at j = 17 it gave -0.99999997.... That was the subtle error. By j = 23 it was rather blatant, producing 1.53...E+20, lol!

  • @millamulisha
    @millamulisha Рік тому +3

    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
      @Barnaclebeard Рік тому

      Can the floor function be decomposed into basic arithmetic?

    • @millamulisha
      @millamulisha Рік тому

      @@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.

  • @zecuse
    @zecuse Рік тому +41

    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!

    • @LegendLength
      @LegendLength Рік тому

      are there ways like newton's method where you take a guess then hone into the real value?

    • @pierrecurie
      @pierrecurie Рік тому +4

      @@LegendLength Newton's method requires evaluating a function repeatedly, so it's even worse.

    • @LegendLength
      @LegendLength Рік тому

      @@pierrecurie this also iterates though so it's a matter of how fast it approaches

    • @timseguine2
      @timseguine2 Рік тому +1

      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.

    • @priyanshugoel3030
      @priyanshugoel3030 Рік тому

      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.

  • @oscaroblivion6570
    @oscaroblivion6570 Рік тому +1

    Not only an interesting mathematical topic but an excellent presentation as well. Thank you.

  • @limpinggabriel6658
    @limpinggabriel6658 Рік тому

    These videos are stunningly amazing. Please keep making them!

  • @nathanielkingsbury6355
    @nathanielkingsbury6355 Рік тому +3

    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!

  • @codatheseus5060
    @codatheseus5060 Рік тому +9

    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.

    • @vanessaashford9203
      @vanessaashford9203 Рік тому +1

      Seconded. Maybe also one on Grassmann numbers more generally as well. The only videos on these subjects currently on UA-cam 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

  • @totolamenace
    @totolamenace Рік тому

    Thank you eric, that's the kind of equations I avoided during my studies, as it was not necessary for my field and it looked way too scary. You make it easy to understand ! I always love getting insight in the way things are crafted, and you did an excellent job at that.

  • @zzz942
    @zzz942 Рік тому

    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

  • @grayjphys
    @grayjphys Рік тому +9

    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.

    • @fullfungo4476
      @fullfungo4476 Рік тому +2

      but cot(pi•x) is not defined for integer values of x though.

  • @GreenMeansGOF
    @GreenMeansGOF Рік тому +15

    Wow. That’s awesome. I always thought there was no formula for primes. It’s unfortunate that the formula is inefficient.

    • @nahometesfay1112
      @nahometesfay1112 Рік тому +24

      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.

  • @el-yago-pe
    @el-yago-pe Рік тому

    This is one of the most beautiful formulas I have ever seen, it’s probably my favourite now

  • @akawmv
    @akawmv Рік тому

    Thanks for this explanation! Very insightful, and you explained it in an easily digestible manner. The graphics helped a lot. 10/10 mealtime video.

  • @davisantos5672
    @davisantos5672 Рік тому +3

    That guy was a true genius, imagine what he could've done with our technology now days

  • @cparks1000000
    @cparks1000000 Рік тому +28

    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).

  • @debochando
    @debochando Рік тому

    I'm in love with the way you explained this math formula. Thank you so much. I think I just learn a new way to look at math.

  • @jokingii
    @jokingii Рік тому

    This is one of the coolest videos I’ve seen in a long time. Definitely made my 170 minute Disney land ride wait much much more worth it.

  • @Ceelbc
    @Ceelbc Рік тому +5

    Remember this for your next math test. If your teacher asks what is the 10th prime, just give this formula & say that n = 10.

  • @ChuzzleFriends
    @ChuzzleFriends Рік тому +101

    1:30 (j − 1)!
    1:40 (A + 1)/j
    4:23 cosπB
    5:11
    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.)

    • @vin0drath0re
      @vin0drath0re 11 місяців тому +2

      ᐟ you can use this for a superscript "/"

    • @General12th
      @General12th 4 місяці тому

      @@vin0drath0re
      /I am the one who knocks/

    • @vin0drath0re
      @vin0drath0re 4 місяці тому

      @@General12th bruh I didn't mean that

  • @thromboid
    @thromboid Рік тому +2

    Notably, Willans does describe the formulae presented in the article as "unsuitable for application to problems in prime number theory". ;)

  • @TrulyNaN
    @TrulyNaN Рік тому

    Thank you for the two videos so far! Looking forward to other topics from your channel :)

  • @petrospaulos7736
    @petrospaulos7736 Рік тому +4

    The best student of 3B1B academy! Keep it up!!

  • @playerguy2
    @playerguy2 Рік тому +3

    time complexity of O( (n!)³ ), _...but a space complexity of O(1)_

  • @anshumanagrawal346
    @anshumanagrawal346 Рік тому +1

    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

  • @Vishal-zr1yz
    @Vishal-zr1yz 15 днів тому

    This reminded me of a Phyics problems regarding counting the no. of collisions between the blocks of mass 'm' and '(100^(n-1))m' (and the no. of collisions between the lighter block and the wall used for rebounding) to calculate the first 'n' digits of π.
    By the way, your explanation regarding the formula was great (couldn't understand anything initially, but slowly grasped on the ideas used here).

  • @dannydandaniel8040
    @dannydandaniel8040 Рік тому +12

    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:/

    • @EricRowland
      @EricRowland  Рік тому +3

      Great that it had already made its way into some calculus classes!

    • @lekiwi_4145
      @lekiwi_4145 Рік тому

      XD

  • @jonahuellenberg6325
    @jonahuellenberg6325 Рік тому +3

    Wonderful video! I got a bit inspired to make my own prime formula. It isn't quite as small as Willans' (I doubt you could get much smaller), but it doesn't require factorial or trigonometric functions.
    UA-cam blocked my comment last time so I'm going to put the link as a reply. It's just a Desmos graph link.

    • @jonahuellenberg6325
      @jonahuellenberg6325 Рік тому +2

      That's too bad, looks like comments with links are silently removed. For the adventurous, the ID of the Desmos graph is 0dwu3aqnlq.

    • @jonahuellenberg6325
      @jonahuellenberg6325 Рік тому +1

      Alternatively, here's the function:
      p(n)=({\sum_{v_{1}=2}^{1.5*n*\operatorname{ln}(n)}{(\operatorname{floor}(\frac{1}{\operatorname{floor}({2}^{({\sum_{v_{2}=2}^{v_{1}}{(({\prod_{v_{3}=2}^{\operatorname{floor}(\sqrt{v_{2}})}{(1-\operatorname{floor}({2}^{-\operatorname{abs}(\operatorname{floor}(\frac{v_{2}}{v_{3}})-\frac{v_{2}}{v_{3}})}))}}))}})-n})+1}))}})+2

    • @EricRowland
      @EricRowland  Рік тому

      Neat! Can you say a bit about how it works? What do you use instead of Wilson's theorem?

    • @jonahuellenberg6325
      @jonahuellenberg6325 Рік тому +1

      @@EricRowland The first working version I came up with went through every number to an upper bound, then checked if that number was prime and if it had n-1 primes below it. Later, I took one of the ideas from Willans' formula and changed it to count every number with less than n primes below it.
      For my prime check, I have a product from 2 -> sqrt(n) and multiply by one if it does not divide, and 0 if it does. That way, if any number divides, the product will be zero, and one otherwise.

    • @jonahuellenberg6325
      @jonahuellenberg6325 Рік тому

      I'm going to leave it at that because half of what I send gets instantly deleted by UA-cam. There's a lot more info on the Desmos graph, but I can't link it. I posted the ID of the graph, but if anyone wants to check it out, you have to figure out how to get there yourself, sorry. I posted some instructions but they got deleted.

  • @TheScawer
    @TheScawer Рік тому

    No clue why this was recommended to me next to my usual content, but hell, I loved it! Great video!

  • @jasonrubik
    @jasonrubik Рік тому +2

    The new 4e7r ? Obviously is doesn't roll off the tongue like 3b1b, but it will eventually work its way into the local vernacular !! ;) Top notch presentation and editing on an esoteric topic worthy of my attention !! Bravo !

  • @safebox36
    @safebox36 Рік тому +4

    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
      @daruyami Рік тому +2

      did you get the job?

    • @safebox36
      @safebox36 Рік тому +1

      @@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
      @piushpaul4880 Рік тому

      @@safebox36 there is an easier algorithm called sieve of erasthomus

    • @zecuse
      @zecuse Рік тому +1

      @@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.

    • @drmonkeys852
      @drmonkeys852 Рік тому

      @@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.

  • @PrincessEev
    @PrincessEev Рік тому +7

    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.

    • @felixstuber8046
      @felixstuber8046 Рік тому +6

      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

    • @Misteribel
      @Misteribel Рік тому +2

      @@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.

    • @drmonkeys852
      @drmonkeys852 Рік тому

      @@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

  • @wiselyXpress
    @wiselyXpress Рік тому

    What a great video! I was under the impression from other content that there was really no way to calculate this. Thank you!

  • @konstantinrebrov675
    @konstantinrebrov675 Рік тому

    When I first learned about prime numbers in high school, I always knew deep in my soul that they are not just randomly arranged, that there must be some kind of algorithm to them, a method behind the madness. I always thought that there's a reason why prime numbers are prime. Even though my math teacher ridiculed me for not recognizing that "there's no pattern to prime numbers, do you see a pattern, kid?" But deep down I knew that they were wrong and that there is some kind of reason, I just didn't have the words to explain my thoughts at that time. I had a hunch, but no proof. But now after watching this video, I finally found the proof that my idea was right, so thank you very much for that.

  • @timanderson5717
    @timanderson5717 Рік тому +8

    What do you get if you replace the sums with integrals and the factorial with the gamma function?

    • @rianfelis3156
      @rianfelis3156 Рік тому +1

      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.

  • @TheNerd484
    @TheNerd484 Рік тому +4

    this made for a pretty fun little 5 minute python project

  • @nicopb4240
    @nicopb4240 11 днів тому

    What a beautiful video!
    Very well explained and illustrated, thank you 🙏🏻

  • @yiannchrst
    @yiannchrst Рік тому +2

    Such a good video! Very well put together and very easy to follow! Well done!

  • @addymant
    @addymant Рік тому +6

    One thing of note is that this formula (kinda) implies that the 0th prime is 1.

  • @Lucky10279
    @Lucky10279 Рік тому +5

    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.

    • @watchpanzer6387
      @watchpanzer6387 Рік тому +5

      You don't even need three operations, you need one, which is NAND. you can create all and, or and not operations using it.

    • @Misteribel
      @Misteribel Рік тому +1

      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.

    • @Lucky10279
      @Lucky10279 Рік тому

      @@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.

    • @Misteribel
      @Misteribel Рік тому

      @@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.

    • @Lucky10279
      @Lucky10279 Рік тому

      @@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.

  • @chestrpop8497
    @chestrpop8497 Рік тому

    It really worked for me after I look and try some tutorials, yours is the one that worked. Owe you a lot.

  • @CrazyGaming-zh3qk
    @CrazyGaming-zh3qk Рік тому

    Your method of explain with the visuals are so amazing.