Fell deep into the rabbit hole of primality testing today. The best-known algorithm is O(log(n)^6). Desperate quest to understand: why 6?!
Conversation
Replying to
The answer relies on more number theory than I can understand presently, but it’s good to have a project to learn with.
Replying to
For even more fun constants, it looks like the easier proof for the original algorithm is O((log n)^21/2) 🤔
1
Replying to
Is that a bound? Funny constants are common when a bound doesn't try to be too sharp
1
Yeah, it’s a bound, which makes it less bizarre, but still…
1
Show replies