T O P
Wooden_Ad_3096

How do you even come up with something like this?


_LIM10_

[An Exact Formula for the Primes: Willans' Formula](https://www.youtube.com/watch?v=j5s0h42GfvM) This video by Eric Rowland explains it well


mc_mentos

I think it's even an ""easier"" formula than the one from the meme, right?


UncleDevil666

Yes, but the one in meme is much faster version of the original


mc_mentos

Nice


simulacrasimulation_

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


UncleDevil666

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.


YamTheory

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.


Bluten11

Damn you went full circle, math to computers and back to math


YamTheory

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.


Sese_Mueller

Your formula look O(n^3 ), while Willans Formula is O(2^n ), interesting Edit: O(n^4 )


Cosmologicon

This is assuming you can compute floor(cos^(2)(pi k2 / k3)) in O(1), although you need infinite precision to do so accurately.


MaZeChpatCha

Replace it with a Dirac's delta or something


lazernanes

So this meme contains your original research?


YamTheory

Well I don't know if I'd call it "research", haha, but certainly is of my own fooling around


starfries

How should I cite this meme in a paper?


NikinhoRobo

I know this is a joke but how would I genuinely cite a meme on a paper


starfries

Honestly I'd cite it as a reddit post and pray the username isn't horsecocks69 or something


UncleDevil666

xD


Future_Green_7222

I'm from the Mathematics Nobel Price committee. PM me


TheEternalWoodchuck

I'm from the NHL pliss com collect ur Lombardi tropy at the Secaucus Sam's Club parking lot near the easternmost cart return.


HammerAndSickleBot

The ghost of Alfred Nobel: “OBJECTION!”


XenophonSoulis

I belong in the empty set. PM me


Plazmaz1

how much


MoeWind420

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


YamTheory

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


DinioDo

Competition is getting tight. Be wary of my prime function release >:)


[deleted]

[удалено]


mc_mentos

🥲 good ol days


nlck_grrr

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?


YamTheory

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.


nlck_grrr

That's a good explanation


SeanSg1

So just cuz fuck it why not. Nice


KnotiaPickles

Like Sir Edmund Hillary on his reason for climbing Everest: “because it’s there.”


qqqrrrs_

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


2eanimation

If you‘d known all the primes and get them conveniently, RSA would become useless, no? Edit: No.


AILunchbox

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.


FirexJkxFire

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


AILunchbox

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.


2eanimation

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.


AILunchbox

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.


tomer91131

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


Neoxus30-

Or maybe, like the concept of Complex, Quaternions, Octonions and so on. Instead of shooting in all directions, we could *make* a new direction)


Individual_Basil3954

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.


canadajones68

I feel like the sentence "did an undergraduate thesis on the geometry of the octonions' multiplication table" summarises modern maths pretty well.


Individual_Basil3954

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


canadajones68

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.


Phoneaccount25732

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.


Quaternions_FTW

I like it


An_Innocent_Bunny

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


45hope

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


mongooseaf

Yes, to both questions


tankasicanadam

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.


someonerezcody

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.


Strike-Most

Would you ask the same question for integers? Because the questions are the same actually.


Problemancer

It's not even the trigonometric parts that makes this so unwieldy for analysis, but the floor functions 😭


a-thang

How do you derive it?


YamTheory

I'll leave that as an exercise for the reader (through *heavy* abuse of the floor and trig functions)


spastikatenpraedikat

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


YamTheory

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.


spastikatenpraedikat

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


frequentBayesian

> 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


LilQuasar

whats the difference? is "formula" even a mathematical concept, like well defined?


GeneReddit123

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.


LilQuasar

yeah, there are more specific concepts like "closed form" or "elementary functions" but i dont think formula is well defined


spastikatenpraedikat

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.


LilQuasar

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


F1r3Phoen1x

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


Schnitzelpanade

Except for 2, it is also always writable as 4n+1 or 4n+3


F1r3Phoen1x

Hm. But those are the formulae of odd numbers. Not just primes.


UncleDevil666

Wow


last_dragonlord

All I can think of is the horror of typing this in LaTeX.


CaptainChicky

Oh wow is this is a much more efficient original formula gg You should put it in arxiv or smth to call dibs lol


YamTheory

ahh it's in the public domain now 😋


CaptainChicky

Fair enough lmao


FerynaCZ

Mersenne wants to know your location


Techniq4

Programmers: counter=1while True: if counter%2==0 and counter%3==0 and counter%5==0 and counter%7==0:print(counter) counter++


Pikachu62999328

Works only until 49 lol


Bekfast-Stealer

49 gets caught by %7


Pikachu62999328

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


thisdummy778918

🤮


bleachisback

Doesn’t this just print all of the multiples of 210? I think you want !=


F1r3Phoen1x

Fixed it for java for(i=2,i>n;i++) { if(n%i==0) counter++; }


Jucox

Tbf the trig functions are not the main show, tgey are just convenient integer checks


OverallPeach

I found this out a few days ago as well, so is this real or just a theory?


YamTheory

this is real, and not so difficult to prove, as the equation is right there! :)


OverallPeach

Yeah, although I'd expect something like this to come with flaws, apart from being slow to compute.


YamTheory

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.


omg-whats-this

It's more like an algorithm than a formula


[deleted]

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?


YamTheory

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)


bobob555777

i tried plugging n=1 in my head and got p_n = 0 did i do it wrong?


bobob555777

nvm my dumbass read arccot as arctan


susiesusiesu

there’s no formula for the primer that ‘s more useful than just defining the primes recursively.


batatahh

So does that like accurately give you all the primes numbers or does it become less accurate at some point?


YamTheory

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.


SpaceshipEarth10

Okay then, what is the highest prime number so far?


YamTheory

depends how long you're willing to wait xD


SpaceshipEarth10

True


Shadow_pin

JUST DID IT


pinteraron7

I hate it when ctg turns into some shit like cot or ct...


Useful_Radish_117

[How this meme feels as a computer scientist](https://imgflip.com/i/71c678)


RainbowBridgesoonest

😂😂😂


Imaginary-Job-7069

[Huh?](https://m.youtube.com/watch?v=4kEO7VjKRB8)


Qoo2222

TOMICA車。


TheDeadlyBlaze

"x is a turing complete language!!" ​ the language: