Problem 930: Quadratic Residue Patterns

Mathematical Foundation

Theorem 1 (Character Sum Identity). For every odd prime $p$:

Proof. Since $\left(\frac{a}{p}\right)\left(\frac{a+1}{p}\right) = \left(\frac{a(a+1)}{p}\right)$ by the multiplicativity of the Legendre symbol, we have:

Note that the $a = 0$ term contributes $\left(\frac{0}{p}\right) = 0$, so $R(p) = \sum_{a=0}^{p-1}\left(\frac{a^2+a}{p}\right)$.

Complete the square: $a^2 + a = (2a+1)^2/4 - 1/4$. As $a$ ranges over $\mathbb{F}_p$, $u = 2a + 1$ also ranges over all of $\mathbb{F}_p$ (since $\gcd(2, p) = 1$ for odd $p$). Thus:

Since $4 = 2^2$ is a perfect square, $\left(\frac{4^{-1}}{p}\right) = \left(\frac{(2^{-1})^2}{p}\right) = 1$. So:

It remains to evaluate $(*)$.

Lemma (Evaluation of $\sum_u \left(\frac{u^2 - c}{p}\right)$). For any $c \not\equiv 0 \pmod{p}$:

Proof of Lemma. Count solutions to $y^2 = u^2 - c$ over $\mathbb{F}_p$, i.e., $u^2 - y^2 = c$, i.e., $(u-y)(u+y) = c$. Set $s = u - y$, $t = u + y$, so $st = c$. For each $s \in \mathbb{F}_p^*$, $t = c/s$ is determined, giving $p - 1$ pairs $(s, t)$. Recovering $(u, y) = ((s+t)/2, (t-s)/2)$, each pair $(s,t)$ yields exactly one $(u, y)$ (since $p$ is odd). So the equation $y^2 = u^2 - c$ has exactly $p - 1$ solutions $(u, y)$.

Now, $\sum_{u=0}^{p-1}\left(\frac{u^2 - c}{p}\right) = \sum_u \left(\text{number of } y \text{ with } y^2 = u^2-c\right) - \sum_u 1$ … more precisely:

Here we used $\left(\frac{v}{p}\right) = \#\{y : y^2 = v\} - 1$ for all $v \in \mathbb{F}_p$ (this is $+1$ for QR, $-1$ for QNR, $0$ for $v = 0$, and $\sum_{y} \mathbf{1}[y^2 = v] = 1 + \left(\frac{v}{p}\right)$). $\square$ (Lemma)

Applying the lemma with $c = 1$ to $(*)$: $R(p) = -1$. $\square$ (Theorem 1)

Theorem 2 (Special Case $p = 2$). $R(2) = 0$.

Proof. The sum has one term ($a = 1$): $R(2) = \left(\frac{1}{2}\right)\left(\frac{2}{2}\right) = 1 \cdot 0 = 0$. $\square$

Theorem 3 (Final Answer). $\displaystyle\sum_{\substack{p \leq N \\ p \text{ prime}}} R(p) = -(\pi(N) - 1)$ for $N \geq 2$.

Proof. By Theorems 1 and 2: $R(2) = 0$ and $R(p) = -1$ for every odd prime $p \leq N$. There are $\pi(N) - 1$ odd primes up to $N$. Hence the sum is $0 + (-1)(\pi(N) - 1) = -(\pi(N) - 1)$. $\square$

For $N = 10^5$: $\pi(10^5) = 9592$, so the answer is $-(9592 - 1) = -9591$.

Editorial

Or equivalently. We count primes up to N. We first generate the primes required by the search, then enumerate the admissible combinations and retain only the values that satisfy the final test.

Pseudocode

Count primes up to N
Or equivalently
for p in primes
else

Complexity Analysis

• Time: $O(N \log \log N)$ for the prime sieve; $O(1)$ for the final computation once $\pi(N)$ is known.
• Space: $O(N)$ for the sieve.

Answer

#include <bits/stdc++.h>
using namespace std;
int main() {
    const int N = 100000;
    vector<bool> sieve(N + 1, true);
    sieve[0] = sieve[1] = false;
    for (int i = 2; i * i <= N; i++)
        if (sieve[i])
            for (int j = i*i; j <= N; j += i)
                sieve[j] = false;
    int prime_count = 0;
    for (int p = 3; p <= N; p++)
        if (sieve[p]) prime_count++;
    // R(2)=0, R(p)=-1 for odd primes
    cout << -prime_count << endl;
    return 0;
}

"""
Problem 930: Quadratic Residue Patterns

For a prime p, define R(p) = sum_{a=1}^{p-1} L(a,p) * L(a+1,p) where L is
the Legendre symbol. Compute sum of R(p) for all primes p <= N = 10^5.

Key results:
  - R(2) = 0.
  - R(p) = -1 for all odd primes p (classical result from character sums).
  - Therefore sum = 0 + (-1) * (number_of_odd_primes_up_to_N).

Methods:
  - solve: O(N log log N) sieve, then apply the formula directly.
  - R_brute: O(p^2) brute-force computation of R(p) for verification.
  - legendre: Euler criterion for the Legendre symbol.

Complexity: O(N log log N) for sieve; verification is O(p) per prime.
"""

from collections import Counter

# Core functions
def legendre(a, p):
    """Compute the Legendre symbol (a/p) via Euler's criterion."""
    if a % p == 0:
        return 0
    return 1 if pow(a, (p - 1) // 2, p) == 1 else -1

def R_brute(p):
    """Brute-force computation of R(p) = sum L(a,p)*L(a+1,p)."""
    return sum(legendre(a, p) * legendre((a + 1) % p, p) for a in range(1, p))

def solve(N=10**5):
    """Sum of R(p) for primes p <= N. Uses R(2)=0, R(odd p)=-1."""
    sieve = [True] * (N + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(N**0.5) + 1):
        if sieve[i]:
            for j in range(i * i, N + 1, i):
                sieve[j] = False
    primes = [p for p in range(2, N + 1) if sieve[p]]
    # R(2) = 0, R(p) = -1 for all odd primes
    total = 0 + (-1) * (len(primes) - 1)
    return total

def qr_set(p):
    """Return the set of quadratic residues mod p."""
    return set(x * x % p for x in range(1, p))

# Verification
assert R_brute(3) == -1
assert R_brute(5) == -1
assert R_brute(7) == -1
assert R_brute(11) == -1
assert R_brute(13) == -1
assert R_brute(2) == 0

# Cross-check solve against brute force for small N
for test_N in [10, 50, 100]:
    sieve_t = [True] * (test_N + 1)
    sieve_t[0] = sieve_t[1] = False
    for i in range(2, int(test_N**0.5) + 1):
        if sieve_t[i]:
            for j in range(i * i, test_N + 1, i):
                sieve_t[j] = False
    ps = [p for p in range(2, test_N + 1) if sieve_t[p]]
    brute_sum = sum(R_brute(p) for p in ps)
    assert solve(test_N) == brute_sum, f"Mismatch at N={test_N}"

# Compute answer
answer = solve()
print(answer)