Timeline for Quick computation of a certain exponential sum
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 2, 2018 at 23:02 | comment | added | WhatsUp | Maybe $O(X^{1/2}\log\log X)$... but not much difference. Just iterate over prime powers $p^k \leq X$ for $k = 2, 3, \cdots$. | |
| Apr 2, 2018 at 21:02 | comment | added | Mayank Pandey | How would one do the rest in $O(X^{1/2})$? | |
| Apr 1, 2018 at 23:49 | comment | added | WhatsUp | The main problem is to sum over all prime numbers (the rest is $O(X^{1/2})$. A fast algorithm, if ever exist, might look like the algorithm for the prime counting function. en.wikipedia.org/wiki/… This means that it cannot be much faster than, say, $O(X^{2/3})$. Even though, the idea may not be applicable, because doing "minus" will dramatically kill the accuracy. | |
| Mar 31, 2018 at 21:19 | history | edited | Mayank Pandey | CC BY-SA 3.0 |
title
|
| Mar 31, 2018 at 20:01 | history | asked | Mayank Pandey | CC BY-SA 3.0 |