Sums of prime powers

2,489

Deléglise-Dusart-Roblot [1] give an algorithm which determines the number of primes up to $x$ that are congruent to $l$ modulo $k,$ in time $O(x^{2/3}/\log^2x).$ A modification of the algorithm of Lagarias-Odlyzko [2] allows the same to be computed in time $O(x^{1/2+o(1)}).$

So using either algorithm, find the number of primes in all residue classes mod primes up to $\log m.$ For each prime $q,$ take the total number of primes in each residue class times that residue class to the $k$-th power; this gives the value of $$\sum_{\stackrel{p\le N}{p\text{ prime}}}p^k\pmod q.$$

Use the Chinese Remainder Theorem to determine the value of the sum mod $2\cdot3\cdots\log m.$ The Prime Number Theorem ensure that this, or a little more, is greater than $m$ and hence sufficient to determine the result uniquely. (Note that if $m>N^{k+1}/\log N$ or so, the calculations can be done exactly working mod $k\log N$ or so.)

This gives the sum (mod m or in Z) in time $O(N^{1/2+o(1)})$ since the number of calculations needed is logarithmic.

References

[1] Marc Deléglise, Pierre Dusart, and Xavier-François Roblot, Counting primes in residue classes, Mathematics of Computation 73:247 (2004), pp. 1565-1575. doi 10.1.1.100.779

[2] J. C. Lagarias and A. M. Odlyzko, Computing $\pi(x)$: An analytic method, Journal of Algorithms 8 (1987), pp. 173-191.

[3] Charles, answer on MathOverflow. (Yes, this is the same person. See the other answers there for different approaches.)

Share:
2,489

Related videos on Youtube

Charles
Author by

Charles

Updated on August 15, 2022

Comments

  • Charles
    Charles over 1 year

    You are given positive integers N, m, and k. Is there a way to check if $$\sum_{\stackrel{p\le N}{p\text{ prime}}}p^k\equiv0\pmod m$$ faster than computing the (modular) sum?

    For concreteness, you can assume $e^k<m<N.$

    I don't know of a way, but it's not obvious to me that no method exists. Fast ways to prove or refute the equivalence would be of interest. You can assume that the particular instance of the problem is 'hard', that is, the modulus is not close enough to N so that Rosser-type bounds on the sum would rule it out.

    With $k=0$ this is just asking if $m|\pi(N)$, so it is possible to compute the sum in time $O(N^{1/2+\varepsilon})$ using the Lagarias-Odlyzko method. (Or more practically, one of the combinatorial $\pi(x)$ methods.) For $k>0$ the sum is superlinear and so cannot be stored directly (without, e.g., modular reduction) but it's not clear whether a fast algorithm exists.

    You can think of the problem as "Your friend, who has access to great computational resources, makes the claim (N, m, k). If her claim is true, can you prove it? If her claim is false, can you refute it?".

    Edit: I posted a related problem on cstheory, asking if there is a short proof or interactive proof that the sum is correct.

    • Douglas Zare
      Douglas Zare over 12 years
      The title and tags involve primes, but in the question you only use the suggestive notation $p$. Do you mean the sum to be over primes up to $N$? Can you give some motivation for considering this sum?
    • Charles
      Charles over 12 years
      Yes, the sum over primes up to N. The motivation is checking -- or allowing others to check -- sequences such as oeis.org/A125825 . In this example k = 6, m = a(n), and N = prime(a(n)). There are fast methods for finding prime(n) from n, but none that I know of for finding the sum or the sum mod m faster than re-calculating the entire sequence.
    • davidlowryduda
      davidlowryduda over 12 years
      I would also be interested to know if this can be done for any k greater than 1 - if there is any progress.
    • Angela Pretorius
      Angela Pretorius about 12 years
      let x be the number of primes $\leq N$. Then the sum cannot be 0 if m is even and x is even, or if m is divisible by 3 and x is 1(MOD3) because $p^{2n}$ is 1(mod3) unless p is divisible by 3.
    • GarouDan
      GarouDan about 12 years
      Maybe we can't do fast computer way using this, but is an interesting thing to do: if you create a polinomial wich the roots is the prime numbers and than you expand $\frac{f'(x)}{f(x)}$ you will find the sum of the roots raised in the powers sequentially.
    • djhaskin987
      djhaskin987 about 12 years
      Here is my thought: The Riemann Zeta function ties the natural numbers raised to a power and inverted to the euler product, which are tied to the prime numbers. Is there a tie between the sum of inverted prime numbers and some product of operations on the natural numbers? that might help solve this problem.
    • Dimitrije Kostic
      Dimitrije Kostic about 12 years
      A couple of comments: First, there doesn't seem to be a lot of literature on sums of (powers of) primes. There are some asymptotic results when $k=1$ (e.g. arxiv.org/abs/1011.1667 ) but that's about all I can (quickly) find. Also, the Fermat-Euler theorem can help reduce the sum, because if $(p,m)=1$ then $p^k \equiv p^{k / \Phi(m)} \mod m$. That's still a long way from the computation you want to do, though.
  • Steven Stadnicki
    Steven Stadnicki almost 12 years
    Does the CRT actually apply here? That is, if I have (for instance) the value of the sum mod $(m+10)$, but the sum itself is substantially greater than $m$ (which can easily happen, e.g. if $N\gg m$) then that doesn't tell me anything at all about the value of the sum mod $m$ itself...
  • Charles
    Charles almost 12 years
    @StevenStadnicki: Yes, it does. The easiest way is to use the primes up to, say, 2.01 log N, so that the produce of the primes is larger than the total sum. You can then reduce normally. Other approaches are possible for small and/or smooth m.