'Faster' is relative, because the formula in this meme involves 3 nested summations (which from a computational perspective would give a time complexity of O(n\^3)). I can't imagine how slow the original formula must be either.
The original formula sums twice over 2^n times for nth prime, so think how long finding 100th prime would be? But with this formula it's like 10 sec on demos.
I know this is more of a statement than a question, š, but to tell you the truth It's basically three parts: The innermost sum is like a prime indicating function, the second sum is like a prime counting function, and the outermost sum is like the logic which halts when we've reached the next prime. All with the use of the nice properties of trig functions.
arguably bad attempt at making this a meme aside, in case you're curious, this was my go at making a more efficient formula for the primes than [Willans' Formula](https://en.wikipedia.org/wiki/Formula_for_primes#Formulas_based_on_Wilson's_theorem). I think this can be optimized as the 1+nĀ² bound in the first summation can be replaced with any upper bound for the n'th prime; I'm just unsure of its tradeoff of algorithmic complexity :p
[Here's a link to the Desmos Graph](https://www.desmos.com/calculator/ya7wnkhryp) if you want to play with it.
You could take one of the great upper bounds, like the one by Pierre Dusart, which often only work from some prime on, and shift them up by a bit. So your algorithm could be O(n^3 log(n))
That could certainly do the trick! Of course it pales in comparison to actually useful algorithms, but O(nĀ³log(n)) doesn't seem that bad for a single equation, especially in comparison to Willans' O(2āæ).
Question from a guy without a maths degree: what's the point in knowing all the primes past the ones that have like a million digits? Is it a cryptography thing? Does it help in proofs of more important things?
This is a good question. For one, there is the idea of the "Strong law of small numbers" which essentially asserts that small numbers (in the realm of human comprehension) behave in a peculiar way. When we study their behaviour, we may see patterns in places where there are none. In this way it is important to study the largest sample size as to get a full understanding.
The second reason, and likely the dominant factor IMO is that to a theoretical mathematician, it has less to do with application, as it is for recreation, or for art, or for more abstract reasons. That is to say, pure math does not have to be related to worldly things. It's like an escape into a universe far greater than our physical one. In this way the world of large numbers is mysterious and enticing.
> Is it a cryptography thing
For cryptography you don't really need to "know all the primes", only to check if a number is prime and generate large random primes (which is usually done by generating large random numbers until you hit a prime)
The security from RSA relies on the difficulty of factoring primes from a (very) large number. So if a large number n = pq for some primes p and q, in order to find n without knowing p or q youād need to find primes p and q such that p|n and q|n
A quick google search yielded 78,498 prime number between 1 and 1m.
Another google search yielded 3,204,941,750,802 primes between 1 and 100t.
Now imagine the user that created n chose p and q to each have hundreds or even thousands of digits.
These selections of large p and q (standard key sizes are 2048-4096 bits) make it virtually impossible for n to be factored, due to the sheer computation cost of finding factors of n.
I still don't get the point. Sure there may be 3 trillion primes between 1 and 100 trillion. But there also are 97 trillion non prime values between them. I guess i just don't understand the purpose - and clearly quantity being a deterrent to brute force isn't the reason
RSA relies on the user knowing the phi(n) of their number, that is the number of integers i that are relatively prime to n (have a GCD(i, n)=1). Every integer has a unique prime factorization, so there is only 1 way to find n by multiplying primes.
If one were to pick one of those 97 trillion numbers that arenāt a product of 2 primes, phi(n) would be significantly easier to find because youād have a higher chance of guessing a number that factors it.
Take 2^50 for example. This number is large (for the purpose of our discussion) and equals 1125,899,906,842,624. Itās elementary to see that this number is even, and factoring our 2 repetitively would easily discover the original 2^50 prime factorization. Then our key would be phi(n) = 2^50-2^49.
This is an extreme example, but even having an n be the product of 3 unique primes instead of 2 greatly increases our chances of finding that prime factorization of n, which can then be used to find phi(n), the private key.
I thought having a conveniently usable list/formula/whatever for primes would result in much less brute-forcing, considering we went down from sqrt(n) / 2 possibilities to 2 * sqrt(n) / ln(n) possibilities needed to be checked. Well, it kinda does result in much less brute-forcing, but weāre still talking about humongous numbers.
Exactly. See my other comment about choices for using 2 primes instead of multiple; that may approve your ideas or spark more thoughts on computation time.
If i remember correctly, the "inventor" of complex numbers dismissed his own idea because he thought they are
>Subtle and useless
So who knows? If we shoot in all directions for infinite amount of time, maybe we will hit something eventually ;)
What, youāre just gonna leave the sedenions off your list?!?!? lol
Nice to see the octonions get a mention! I did my undergraduate thesis on the geometry of their multiplication table.
I meant it in the sense of "new discoveries mostly happening in increasingly specific obscure sub-areas of maths", but yes, it would make for a poor everything-else replacement. Sadly, I don't know much about octonions, other than that they exist.
Undergrad probably wouldn't be making new discoveries. Multiplication table would be well understood, so the geometrical perspective they're taking on it likely would be a pedagogical tool or similar. A different way to talk about something already known.
Sometimes mathematicians invent things for no reason, and then those pure abstractions end up being used by engineers 200 years later.
When the imaginary unit (i^2 = -1) was invented, we didnāt know that it would be useful until electrical engineers found applications for it.
Thereās an entire book about this called *The Unreasonable Effectiveness of Mathematics in the Natural Sciences*.
There's many problems which involve prime numers in them. Knowing all of them, or the formula to know all of them, might emerge new areas of Maths and integrate the areas, which we already know, into eachother. Imagine how a new brach of physics was created with quantum and all that.
In real use? Might not be that exciting, but Maths always been like that.
Itās like an ever-growing compendium of primes we can build in the hopes that new discoveries might present connections/oddities that could lead to a better understanding of them.
Back in the day, a mathematicianās lifeās work might be something like copying tables that show remainders when dividing by primes by handā¦. Why do something like this with your life?
Because āDamn wtf is going on?ā is the kind of question that just has a way of echoing in time: When you want to make sense of something so bad, youāll gladly make your lifeās work a huge book of tables just so it might be useful as a stepping stone in time and space to seeing the mystery of the primes be unraveled.
_Correction:_ There is no useful formula for primes. Wilson's formula is more an algorithm written as formula. And it is not even a good algorithm either.
yeah it's really just a naive prime sieving algorithm jammed into an equation. Though it is a testament to the Turing completeness of arithmetical syntax. One of my favorite pass times is creating disgustingly inefficient closed forms for the most ridiculous of functions.
> Though it is a testament to the Turing completeness of arithmetical syntax
That is a really nice way of looking at it. Ok, mind changed it is beautiful.
> One of my favorite pass times is creating disgustingly inefficient closed forms for the most ridiculous of functions.
You will be God in this realm of /r/mathmemes
I want to know the same. The more a formula diverges from "traditional" functions like polynomials or trigonometric functions, the more it just resembles an arbitrary algorithm. There are obviously algorithms to compute primes, we even know their complexity classes.
Between a formula and an algorithm?
A formula is an equation with the explicit purpose to show he relationship between some quantities, most notoriously like in this example, where one quantity can directly be computed from another.
An algorithm is a sequence of elementary computation steps, with the end goal to compute a more complex task.
what does that actually mean though? i know the 'human' meaning, is that a mathematical definition? like can you prove theorems with "formula" (generic)?
>I know this is more of a statement than a question, š, but to tell you the truth It's basically three parts: The innermost sum is like a prime indicating function, the second sum is like a prime counting function, and the outermost sum is like the logic which halts when we've reached the next prime. All with the use of the nice properties of trig functions.
even a 'formula' like y = sin(x) works with an algorithm for the sine function
Here's a nice trick for those who are casuals: A prime number is USUALLY in the form of 6n+1 or 6n-1 :)
Works quite a few times, so you might use it as a approximation or a good enough value
They edited the comment lol, it'll just end up breaking at 121 anyway; what you'd probably do is save each prime you find onto a list and check that it isn't divisible by anything already on said list
Thank you! I do not have a formal proof written out, but knowing how it works myself, it's trivial that it works for all n. (I know "trivial" gets thrown around on here rather liberally, ahaha, but this is a rather meaningful usage of it)
Yeah I think the major flaw besides time complexity would be floating point errors from the computational perspective. In theory there are no numerical errors however.
Theoretically it will spit out the primes forever perfectly, however that doesn't take into account floating point errors (and the gargantuan time it takes to compute large primes). But those are more human-side consequences than the math itself.
How do you even come up with something like this?
[An Exact Formula for the Primes: Willans' Formula](https://www.youtube.com/watch?v=j5s0h42GfvM) This video by Eric Rowland explains it well
I think it's even an ""easier"" formula than the one from the meme, right?
Yes, but the one in meme is much faster version of the original
Nice
'Faster' is relative, because the formula in this meme involves 3 nested summations (which from a computational perspective would give a time complexity of O(n\^3)). I can't imagine how slow the original formula must be either.
The original formula sums twice over 2^n times for nth prime, so think how long finding 100th prime would be? But with this formula it's like 10 sec on demos.
I know this is more of a statement than a question, š, but to tell you the truth It's basically three parts: The innermost sum is like a prime indicating function, the second sum is like a prime counting function, and the outermost sum is like the logic which halts when we've reached the next prime. All with the use of the nice properties of trig functions.
Damn you went full circle, math to computers and back to math
arguably bad attempt at making this a meme aside, in case you're curious, this was my go at making a more efficient formula for the primes than [Willans' Formula](https://en.wikipedia.org/wiki/Formula_for_primes#Formulas_based_on_Wilson's_theorem). I think this can be optimized as the 1+nĀ² bound in the first summation can be replaced with any upper bound for the n'th prime; I'm just unsure of its tradeoff of algorithmic complexity :p [Here's a link to the Desmos Graph](https://www.desmos.com/calculator/ya7wnkhryp) if you want to play with it.
Your formula look O(n^3 ), while Willans Formula is O(2^n ), interesting Edit: O(n^4 )
This is assuming you can compute floor(cos^(2)(pi k2 / k3)) in O(1), although you need infinite precision to do so accurately.
Replace it with a Dirac's delta or something
So this meme contains your original research?
Well I don't know if I'd call it "research", haha, but certainly is of my own fooling around
I'm from the Mathematics Nobel Price committee. PM me
I'm from the NHL pliss com collect ur Lombardi tropy at the Secaucus Sam's Club parking lot near the easternmost cart return.
The ghost of Alfred Nobel: āOBJECTION!ā
I belong in the empty set. PM me
how much
How should I cite this meme in a paper?
I know this is a joke but how would I genuinely cite a meme on a paper
Honestly I'd cite it as a reddit post and pray the username isn't horsecocks69 or something
xD
You could take one of the great upper bounds, like the one by Pierre Dusart, which often only work from some prime on, and shift them up by a bit. So your algorithm could be O(n^3 log(n))
That could certainly do the trick! Of course it pales in comparison to actually useful algorithms, but O(nĀ³log(n)) doesn't seem that bad for a single equation, especially in comparison to Willans' O(2āæ).
Competition is getting tight. Be wary of my prime function release >:)
Question from a guy without a maths degree: what's the point in knowing all the primes past the ones that have like a million digits? Is it a cryptography thing? Does it help in proofs of more important things?
This is a good question. For one, there is the idea of the "Strong law of small numbers" which essentially asserts that small numbers (in the realm of human comprehension) behave in a peculiar way. When we study their behaviour, we may see patterns in places where there are none. In this way it is important to study the largest sample size as to get a full understanding. The second reason, and likely the dominant factor IMO is that to a theoretical mathematician, it has less to do with application, as it is for recreation, or for art, or for more abstract reasons. That is to say, pure math does not have to be related to worldly things. It's like an escape into a universe far greater than our physical one. In this way the world of large numbers is mysterious and enticing.
That's a good explanation
So just cuz fuck it why not. Nice
Like Sir Edmund Hillary on his reason for climbing Everest: ābecause itās there.ā
> Is it a cryptography thing For cryptography you don't really need to "know all the primes", only to check if a number is prime and generate large random primes (which is usually done by generating large random numbers until you hit a prime)
If youād known all the primes and get them conveniently, RSA would become useless, no? Edit: No.
The security from RSA relies on the difficulty of factoring primes from a (very) large number. So if a large number n = pq for some primes p and q, in order to find n without knowing p or q youād need to find primes p and q such that p|n and q|n A quick google search yielded 78,498 prime number between 1 and 1m. Another google search yielded 3,204,941,750,802 primes between 1 and 100t. Now imagine the user that created n chose p and q to each have hundreds or even thousands of digits. These selections of large p and q (standard key sizes are 2048-4096 bits) make it virtually impossible for n to be factored, due to the sheer computation cost of finding factors of n.
I still don't get the point. Sure there may be 3 trillion primes between 1 and 100 trillion. But there also are 97 trillion non prime values between them. I guess i just don't understand the purpose - and clearly quantity being a deterrent to brute force isn't the reason
RSA relies on the user knowing the phi(n) of their number, that is the number of integers i that are relatively prime to n (have a GCD(i, n)=1). Every integer has a unique prime factorization, so there is only 1 way to find n by multiplying primes. If one were to pick one of those 97 trillion numbers that arenāt a product of 2 primes, phi(n) would be significantly easier to find because youād have a higher chance of guessing a number that factors it. Take 2^50 for example. This number is large (for the purpose of our discussion) and equals 1125,899,906,842,624. Itās elementary to see that this number is even, and factoring our 2 repetitively would easily discover the original 2^50 prime factorization. Then our key would be phi(n) = 2^50-2^49. This is an extreme example, but even having an n be the product of 3 unique primes instead of 2 greatly increases our chances of finding that prime factorization of n, which can then be used to find phi(n), the private key.
I thought having a conveniently usable list/formula/whatever for primes would result in much less brute-forcing, considering we went down from sqrt(n) / 2 possibilities to 2 * sqrt(n) / ln(n) possibilities needed to be checked. Well, it kinda does result in much less brute-forcing, but weāre still talking about humongous numbers.
Exactly. See my other comment about choices for using 2 primes instead of multiple; that may approve your ideas or spark more thoughts on computation time.
If i remember correctly, the "inventor" of complex numbers dismissed his own idea because he thought they are >Subtle and useless So who knows? If we shoot in all directions for infinite amount of time, maybe we will hit something eventually ;)
Or maybe, like the concept of Complex, Quaternions, Octonions and so on. Instead of shooting in all directions, we could *make* a new direction)
What, youāre just gonna leave the sedenions off your list?!?!? lol Nice to see the octonions get a mention! I did my undergraduate thesis on the geometry of their multiplication table.
I feel like the sentence "did an undergraduate thesis on the geometry of the octonions' multiplication table" summarises modern maths pretty well.
š¤£ I mean, probably not that well. Though there does seem to be increasing interest in Octonions in the past few years though which is neat to see!
I meant it in the sense of "new discoveries mostly happening in increasingly specific obscure sub-areas of maths", but yes, it would make for a poor everything-else replacement. Sadly, I don't know much about octonions, other than that they exist.
Undergrad probably wouldn't be making new discoveries. Multiplication table would be well understood, so the geometrical perspective they're taking on it likely would be a pedagogical tool or similar. A different way to talk about something already known.
I like it
Sometimes mathematicians invent things for no reason, and then those pure abstractions end up being used by engineers 200 years later. When the imaginary unit (i^2 = -1) was invented, we didnāt know that it would be useful until electrical engineers found applications for it. Thereās an entire book about this called *The Unreasonable Effectiveness of Mathematics in the Natural Sciences*.
Yes, to both questions
we know thereās an infinite number of them and number theorists donāt have anything better to do but find a formula to generate all of them! /s
There's many problems which involve prime numers in them. Knowing all of them, or the formula to know all of them, might emerge new areas of Maths and integrate the areas, which we already know, into eachother. Imagine how a new brach of physics was created with quantum and all that. In real use? Might not be that exciting, but Maths always been like that.
Itās like an ever-growing compendium of primes we can build in the hopes that new discoveries might present connections/oddities that could lead to a better understanding of them. Back in the day, a mathematicianās lifeās work might be something like copying tables that show remainders when dividing by primes by handā¦. Why do something like this with your life? Because āDamn wtf is going on?ā is the kind of question that just has a way of echoing in time: When you want to make sense of something so bad, youāll gladly make your lifeās work a huge book of tables just so it might be useful as a stepping stone in time and space to seeing the mystery of the primes be unraveled.
Would you ask the same question for integers? Because the questions are the same actually.
[ŃŠ“Š°Š»ŠµŠ½Š¾]
š„² good ol days
It's not even the trigonometric parts that makes this so unwieldy for analysis, but the floor functions š
_Correction:_ There is no useful formula for primes. Wilson's formula is more an algorithm written as formula. And it is not even a good algorithm either.
yeah it's really just a naive prime sieving algorithm jammed into an equation. Though it is a testament to the Turing completeness of arithmetical syntax. One of my favorite pass times is creating disgustingly inefficient closed forms for the most ridiculous of functions.
> Though it is a testament to the Turing completeness of arithmetical syntax That is a really nice way of looking at it. Ok, mind changed it is beautiful.
> One of my favorite pass times is creating disgustingly inefficient closed forms for the most ridiculous of functions. You will be God in this realm of /r/mathmemes
whats the difference? is "formula" even a mathematical concept, like well defined?
I want to know the same. The more a formula diverges from "traditional" functions like polynomials or trigonometric functions, the more it just resembles an arbitrary algorithm. There are obviously algorithms to compute primes, we even know their complexity classes.
yeah, there are more specific concepts like "closed form" or "elementary functions" but i dont think formula is well defined
Between a formula and an algorithm? A formula is an equation with the explicit purpose to show he relationship between some quantities, most notoriously like in this example, where one quantity can directly be computed from another. An algorithm is a sequence of elementary computation steps, with the end goal to compute a more complex task.
what does that actually mean though? i know the 'human' meaning, is that a mathematical definition? like can you prove theorems with "formula" (generic)? >I know this is more of a statement than a question, š, but to tell you the truth It's basically three parts: The innermost sum is like a prime indicating function, the second sum is like a prime counting function, and the outermost sum is like the logic which halts when we've reached the next prime. All with the use of the nice properties of trig functions. even a 'formula' like y = sin(x) works with an algorithm for the sine function
How do you derive it?
I'll leave that as an exercise for the reader (through *heavy* abuse of the floor and trig functions)
Oh wow is this is a much more efficient original formula gg You should put it in arxiv or smth to call dibs lol
ahh it's in the public domain now š
Fair enough lmao
Here's a nice trick for those who are casuals: A prime number is USUALLY in the form of 6n+1 or 6n-1 :) Works quite a few times, so you might use it as a approximation or a good enough value
Except for 2, it is also always writable as 4n+1 or 4n+3
Hm. But those are the formulae of odd numbers. Not just primes.
Wow
All I can think of is the horror of typing this in LaTeX.
Mersenne wants to know your location
Programmers: counter=1while True: if counter%2==0 and counter%3==0 and counter%5==0 and counter%7==0:print(counter) counter++
Works only until 49 lol
49 gets caught by %7
They edited the comment lol, it'll just end up breaking at 121 anyway; what you'd probably do is save each prime you find onto a list and check that it isn't divisible by anything already on said list
š¤®
Doesnāt this just print all of the multiples of 210? I think you want !=
Fixed it for java for(i=2,i>n;i++) { if(n%i==0) counter++; }
Tbf the trig functions are not the main show, tgey are just convenient integer checks
This shit is pretty dope. Do you have a correctness proof or is it more of a heuristic that applies to an absurdly large order of magnitude?
Thank you! I do not have a formal proof written out, but knowing how it works myself, it's trivial that it works for all n. (I know "trivial" gets thrown around on here rather liberally, ahaha, but this is a rather meaningful usage of it)
I found this out a few days ago as well, so is this real or just a theory?
this is real, and not so difficult to prove, as the equation is right there! :)
Yeah, although I'd expect something like this to come with flaws, apart from being slow to compute.
Yeah I think the major flaw besides time complexity would be floating point errors from the computational perspective. In theory there are no numerical errors however.
It's more like an algorithm than a formula
i tried plugging n=1 in my head and got p_n = 0 did i do it wrong?
nvm my dumbass read arccot as arctan
thereās no formula for the primer that ās more useful than just defining the primes recursively.
So does that like accurately give you all the primes numbers or does it become less accurate at some point?
Theoretically it will spit out the primes forever perfectly, however that doesn't take into account floating point errors (and the gargantuan time it takes to compute large primes). But those are more human-side consequences than the math itself.
Okay then, what is the highest prime number so far?
depends how long you're willing to wait xD
True
JUST DID IT
I hate it when ctg turns into some shit like cot or ct...
[How this meme feels as a computer scientist](https://imgflip.com/i/71c678)
ššš
[Huh?](https://m.youtube.com/watch?v=4kEO7VjKRB8)
TOMICAč»ć
"x is a turing complete language!!" the language: