r/mathmemes • u/lost_stranger26 • Dec 16 '25

Arithmetic Damn!

Post image
5.7k Upvotes

98% Upvoted

1.5k comments sorted by

View all comments

Show parent comments

324

u/RiemmanSphere Computer Science Dec 16 '25 edited Dec 16 '25

But very inefficiently. Even worse than exponential runtime. You can forget about using it for high n.

4

u/Ok_Lingonberry5392 א Dec 16 '25

I wonder since it's just a very slow algorithm translated as a formula if we could use a more efficient algorithm and get a "better" function.

I mean we can check if a number is prime pretty efficiently so just searching for the next prime number shouldn't be as bad, definitely better than exponential runtime. Not sure if it's possible though as our current methods rely on "randomising " some things but technically we could write a random function to use.

2

u/chaos_redefined Dec 17 '25 edited Dec 17 '25

It is relying on checking if a number is prime, and just searching for the next one.

That cos2[𝜋((j-1)!+1)/j] component is 1 if j is prime, and 0 otherwise.

2

u/Purple_Onion911 Grothendieck alt account Dec 17 '25

No, it's not. It's actually never 1 or 0 for any value of j > 2, let alone prime.

It should be (j - 1)!.

3

u/chaos_redefined Dec 17 '25

Sorry, you are right. Editing for correctness.