Intereting Posts

Subfield of rational function fields
On products of ternary quadratic forms $\prod_{i=1}^3 (ax_i^2+by_i^2+cz_i^2) = ax_0^2+by_0^2+cz_0^2$
If $xy+xz+yz=3$ so $\sum\limits_{cyc}\left(x^2y+x^2z+2\sqrt{xyz(x^3+3x)}\right)\geq2xyz\sum\limits_{cyc}(x^2+2)$
Number of path components of a function space
Maximizing a quadratic function subject to $\| x \|_2 \le 1$
Is the derivate on a closed subspace of $C^1$ is a continuous linear map?
$ x^2 + \frac {x^2}{(x-1)^2} = 2010 $
Converse of Lagrange's theorem for abelian groups
Prove that if $\gcd( a, b ) = 1$ then $\gcd( ac, b ) = \gcd( c, b ) $
Division by zero
Expression for normal product similar to semidirect product
On the convexity of element-wise norm 1 of the inverse
Generating Functions in Discrete Math
On the converse of Schur's Lemma
Tetrations of non-integers?

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.

- Algorithm to find the point in a convex polygon closest to an external point
- A 3rd grade math problem: fill in blanks with numbers to obtain a valid equation
- Optimal algorithm for finding the odd spheres
- All pairs shortest path in undirected and unweighted graphs
- Is this a wrong solution to the smallest enclosing circle problem?
- In how many ways we can place $N$ mutually non-attacking knights on an $M \times M$ chessboard?

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.

- Counting square free numbers co-prime to $m$
- The Binary Representation in Number Theory?
- Why don't we define division by zero as an arbritrary constant such as $j$?
- Does the equation $a^{2} + b^{7} + c^{13} + d^{14} = e^{15}$ have a solution in positive integers
- If $n\in\Bbb Z^+$ is not a square, prove exist infinitely many primes $p$ such that $\left(\frac{n}{p}\right)=-1$.
- When is $\binom{n}{k}$ divisible by $n$?
- Ambiguity in the Natural Numbers
- What are the smallest amount of numbers required to generate all the even numbers?
- Relationships between the elements $(a,b,c,d)$ of a solution to $A^2+B^2+4=C^2+D^2$
- Simultaneous Diophantine approximation: multiple solutions required

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.

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

- Affine dimension of a simplex
- Different ways of computing $\sqrt{1+\sqrt{1+\sqrt{1+\cdots}}}$
- How to prove $\gcd(a,\gcd(b, c)) = \gcd(\gcd(a, b), c)$?
- on the adjointness of the global section functor and the Spec functor
- If $a > b$, is $a^2 > b^2$?
- How to prove Fibonacci sequence with matrices?
- What is so interesting about the zeroes of the Riemann $\zeta$ function?
- Twice differentiable function, show there is a fixed point
- Does the sum $\sum_{n=1}^{\infty}\frac{\tan n}{n^2}$ converge?
- Intuitive explanation for Derangement
- One-Way Inverse
- Explanation for why $1\neq 0$ is explicitly mentioned in Chapter 1 of Spivak's Calculus for properties of numbers.
- Finitely generated projective modules are isomorphic to their double dual.
- Norm of element $\alpha$ equal to absolute norm of principal ideal $(\alpha)$
- Fundamental Group on Quotient of Unit Disk