Problem 934: Primitive Root Sequences

Mathematical Foundation

Definition. An integer $g$ with $\gcd(g, p) = 1$ is a primitive root modulo a prime $p$ if $\operatorname{ord}_p(g) = p - 1$, i.e., $g$ generates the cyclic group $(\mathbb{Z}/p\mathbb{Z})^*$.

Theorem 1 (Existence of primitive roots). Every prime $p$ possesses exactly $\varphi(p - 1)$ primitive roots modulo $p$.

Proof. The group $(\mathbb{Z}/p\mathbb{Z})^*$ is cyclic of order $p - 1$ (a standard result following from the fact that a finite subgroup of the multiplicative group of a field is cyclic). A cyclic group of order $n$ has exactly $\varphi(n)$ generators. $\square$

Theorem 2 (Primitive root test). Let $p$ be prime and let $q_1, \ldots, q_s$ be the distinct prime factors of $p - 1$. Then $g$ is a primitive root modulo $p$ if and only if

Proof. ($\Rightarrow$) If $g$ is a primitive root, then $\operatorname{ord}_p(g) = p - 1$. Since $(p-1)/q_i < p - 1$, we have $g^{(p-1)/q_i} \not\equiv 1$.

($\Leftarrow$) Suppose $\operatorname{ord}_p(g) = d < p - 1$. Then $d \mid (p - 1)$ and $d < p - 1$, so there exists a prime $q_i \mid (p - 1)$ such that $d \mid (p-1)/q_i$ (since $p - 1$ has a prime factor not dividing $d$, or equivalently, $(p-1)/d > 1$ implies some $q_i \mid (p-1)/d$). This gives $g^{(p-1)/q_i} \equiv (g^d)^{(p-1)/(dq_i)} \equiv 1$, a contradiction. $\square$

Lemma 1 (Smallness of $g(p)$). Under the Generalized Riemann Hypothesis, $g(p) = O((\log p)^6)$. Unconditionally (Vinogradov), $g(p) \leq p^{0.499}$ for sufficiently large $p$. Empirically, $g(p) \leq 6$ for the majority of primes, and $g(p) = 2$ for approximately 37% of primes below $10^7$.

Proof. The GRH bound follows from the work of Shoup (1992). The unconditional bound is due to Vinogradov’s character sum estimates. The empirical distribution is verified computationally. $\square$

Editorial

For each prime p, let g(p) be the smallest primitive root modulo p. Compute S(N) = sum of g(p) for all primes p <= N. We sieve primes and smallest prime factors up to N. We then iterate over each prime p in primes. Finally, factor p - 1 using spf.

Pseudocode

Sieve primes and smallest prime factors up to N
for each prime p in primes
Factor p - 1 using spf
Test candidates g = 2, 3, 4, 5, 
for g from 2 to p-1
for each q in factors

Complexity Analysis

• Time:
  • Sieve of Eratosthenes: $O(N \log \log N)$.
  • For each prime $p$: factoring $p - 1$ takes $O(\log p)$ using the precomputed SPF table. Testing each candidate $g$ requires $O(s \log p)$ modular exponentiations, where $s = \omega(p-1)$ is the number of distinct prime factors of $p-1$. By Lemma 1, $g(p)$ is typically very small (constant on average), so the expected total work is $O(\pi(N) \cdot \overline{s} \cdot \log N)$ where $\overline{s}$ is the average value of $\omega(p-1)$, which is $O(\log \log N)$.
  • Overall: $O(N \log \log N)$.
• Space: $O(N)$ for the sieve.

Answer

#include <bits/stdc++.h>
using namespace std;
int main(){
    const int N=100000;
    vector<bool> is_p(N+1,true);
    is_p[0]=is_p[1]=false;
    for(int i=2;i*i<=N;i++) if(is_p[i]) for(int j=i*i;j<=N;j+=i) is_p[j]=false;
    auto factorize=[](int n){
        set<int> f;
        for(int d=2;d*d<=n;d++) while(n%d==0){f.insert(d);n/=d;}
        if(n>1) f.insert(n);
        return f;
    };
    long long S=0;
    for(int p=2;p<=N;p++){
        if(!is_p[p]) continue;
        if(p==2){S+=1;continue;}
        auto facs=factorize(p-1);
        for(int g=2;g<p;g++){
            bool ok=true;
            for(int q:facs){
                long long r=1,base=g,exp=(p-1)/q;
                long long b=base%p;
                long long e=exp;
                r=1;
                long long bb=b;
                while(e>0){if(e&1) r=r*bb%p; bb=bb*bb%p; e>>=1;}
                if(r==1){ok=false;break;}
            }
            if(ok){S+=g;break;}
        }
    }
    cout<<S<<endl;
    return 0;
}

"""
Problem 934: Primitive Root Sequences

For each prime p, let g(p) be the smallest primitive root modulo p.
Compute S(N) = sum of g(p) for all primes p <= N.

Key results:
  - A primitive root g mod p has multiplicative order p-1.
  - g(2) = 1 (by convention).
  - The smallest primitive root is often 2 or 3; g(p) = 2 is most common.
  - Artin's conjecture: 2 is a primitive root for infinitely many primes.

Methods:
  - sieve_primes: Sieve of Eratosthenes.
  - factorize: Trial division to find prime factors of p-1.
  - smallest_prim_root: Test candidates g=2,3,... using the standard criterion.
  - solve: Sum g(p) for all primes p <= N.

Complexity: O(N log log N) for sieve + O(p^{1/4} * log p) per prime on average.
"""

from collections import Counter

# Sieve of Eratosthenes
def sieve_primes(n):
    """Return list of primes up to n."""
    is_p = [True] * (n + 1)
    is_p[0] = is_p[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_p[i]:
            for j in range(i * i, n + 1, i):
                is_p[j] = False
    return [i for i in range(2, n + 1) if is_p[i]]

# Factorize via trial division
def factorize(n):
    """Return set of distinct prime factors of n."""
    factors = set()
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.add(d)
            n //= d
        d += 1
    if n > 1:
        factors.add(n)
    return factors

# Smallest primitive root
def smallest_prim_root(p):
    """Find the smallest primitive root modulo prime p."""
    if p == 2:
        return 1
    phi = p - 1
    factors = factorize(phi)
    for g in range(2, p):
        if all(pow(g, phi // q, p) != 1 for q in factors):
            return g
    return -1

# Method: Check if g is a primitive root
def is_primitive_root(g, p):
    """Check whether g is a primitive root mod p."""
    if p == 2:
        return g % 2 == 1
    phi = p - 1
    factors = factorize(phi)
    return all(pow(g, phi // q, p) != 1 for q in factors)

# Solve: sum of smallest primitive roots
def solve(N):
    """Compute S(N) = sum of g(p) for primes p <= N."""
    primes = sieve_primes(N)
    return sum(smallest_prim_root(p) for p in primes)

# Verification
# Known smallest primitive roots:
assert smallest_prim_root(2) == 1
assert smallest_prim_root(3) == 2
assert smallest_prim_root(5) == 2
assert smallest_prim_root(7) == 3
assert smallest_prim_root(11) == 2
assert smallest_prim_root(13) == 2
assert smallest_prim_root(17) == 3
assert smallest_prim_root(23) == 5
assert smallest_prim_root(41) == 6

# Verify is_primitive_root
assert is_primitive_root(3, 7)
assert not is_primitive_root(2, 7)  # 2^3 = 8 = 1 mod 7, order 3 != 6

# Compute answer
primes = sieve_primes(10000)
roots = [smallest_prim_root(p) for p in primes]
S = sum(roots)
print(f"S(10^4) = {S}")