Project Euler

Sum of Primitive Roots

For a prime p, the sum of all primitive roots modulo p is mu(p-1) (mod p). Find sum_(p <= 10^6, p prime) (sum of primitive roots mod p) (mod 10^9+7).

Source sync Apr 19, 2026

Problem #0949

Level Level 39

Solved By 65

Languages C++, Python

Answer 726010935

Length 277 words

number_theorymodular_arithmeticlinear_algebra

Left and Right play a game with a number of words, each consisting of L’s and R’s, alternating turns. On Left’s turn, for each word, Left can remove any number of letters (possibly zero), but not all the letters, from the left side of the word. However, at least one letter must be removed from at least one word. Right does the same on Right’s turn except that Right removes letters from the right side of each word. The game continues until each word is reduced to a single letter. If there are more L’s than R’s remaining then Left wins; otherwise if there are more R’s than L’s then Right wins. In this problem we only consider games with an odd number of words, thus making ties impossible.

$\vspace {0.75\baselineskip }$

Let $G(n, k)$ be the number of ways of choosing $k$ words of length $n$, for which Right has a winning strategy when Left plays first. Different orderings of the same set of words are to be counted separately.

It can be seen that $G(2, 3)=14$ due to the following solutions (and their reorderings): \begin {align} (\texttt {LL},\texttt {RR},\texttt {RR})& : 3\text { orderings}\\ (\texttt {LR},\texttt {LR},\texttt {LR})& : 1\text { ordering}\\ (\texttt {LR},\texttt {LR},\texttt {RR})& : 3\text { orderings}\\ (\texttt {LR},\texttt {RR},\texttt {RR})& : 3\text { orderings}\\ (\texttt {RL},\texttt {RR},\texttt {RR})& : 3\text { orderings}\\ (\texttt {RR},\texttt {RR},\texttt {RR})& : 1\text { ordering} \end {align}

You are also given $G(4, 3)=496$ and $G(8, 5)=26359197010$.

Find $G(20, 7)$ giving your answer modulo $1001001011$.

Problem 949: Sum of Primitive Roots

Mathematical Analysis

Sum of Primitive Roots

Theorem. For a prime $p$ , the sum of all primitive roots modulo $p$ is congruent to $\mu(p-1) \pmod{p}$ .

Proof. The primitive roots are elements of order $p-1$ in $(\mathbb{Z}/p\mathbb{Z})^*$ . If $g$ is a primitive root, the others are $g^k$ where $\gcd(k, p-1) = 1$ . The sum is:

\sum_{\substack{k=1 \\ \gcd(k,p-1)=1}}^{p-1} g^k = \sum_{k=1}^{p-1} g^k \sum_{d | \gcd(k, p-1)} \mu(d)

By Mobius inversion and Ramanujan sum theory, this equals $\mu(p-1) \pmod{p}$ . $\square$

The Mobius Function on $p-1$

$\mu(p-1) \in \{-1, 0, 1\}$ :

$\mu(p-1) = 0$ if $p-1$ has a squared prime factor (e.g., $p = 5$ : $p-1 = 4 = 2^2$ ).
$\mu(p-1) = (-1)^k$ if $p-1$ is a product of $k$ distinct primes.

Editorial

Compute sum of mu(p-1) for primes p up to 10^6, mod 10^9 + 7. For a prime p, the number of primitive roots modulo p is phi(p-1). The Mobius function mu(p-1) indicates the “squarefree structure” of p-1: mu(p-1) = 0 if p-1 has a squared prime factor mu(p-1) = +1 if p-1 has an even number of distinct prime factors mu(p-1) = -1 if p-1 has an odd number of distinct prime factors. We sieve primes up to $N$ . We then iterate over each prime $p$ , compute $\mu(p-1)$ by factoring $p-1$ . Finally, accumulate $\mu(p-1) \bmod (10^9+7)$ (treating $\mu = -1$ as $10^9+6$ ).

Pseudocode

Sieve primes up to $N$
For each prime $p$, compute $\mu(p-1)$ by factoring $p-1$
Accumulate $\mu(p-1) \bmod (10^9+7)$ (treating $\mu = -1$ as $10^9+6$)

Factoring $p-1$

Use a smallest-prime-factor (SPF) sieve up to $N$ to factorize $p-1$ quickly.

Concrete Examples

$p$	$p-1$	$\mu(p-1)$	Sum of prim roots mod $p$
2	1	1	1
3	2	-1	2 (= $-1 \bmod 3$ )
5	4	0	0
7	6	1	1

Proof of Correctness

Sum formula: Classical result in number theory.
Mobius via SPF sieve: Correct factorization.
Modular reduction: $-1 \equiv p - 1 \pmod{p}$ , but accumulated $\bmod 10^9+7$ .

Complexity Analysis

SPF sieve: $O(N)$ .
Per prime: $O(\log p)$ for factorization via SPF.
Total: $O(N)$ .

Answer

\boxed{726010935}

C++ project_euler/problem_949/solution.cpp

#include <bits/stdc++.h>
using namespace std;
int main(){
    const int N=1000000;
    const long long MOD=1e9+7;
    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;
    vector<int> mu(N+1,0); mu[1]=1;
    vector<bool> ip2(N+1,true); vector<int> primes;
    for(int i=2;i<=N;i++){
        if(ip2[i]){primes.push_back(i);mu[i]=-1;}
        for(int p:primes){
            if((long long)i*p>N) break;
            ip2[i*p]=false;
            if(i%p==0){mu[i*p]=0;break;}
            else mu[i*p]=-mu[i];
        }
    }
    long long S=0;
    for(int p=2;p<=N;p++) if(is_p[p]) S=(S+mu[p-1]+MOD)%MOD;
    cout<<S<<endl;
    return 0;
}

Python project_euler/problem_949/solution.py

"""
Problem 949: Sum of Primitive Roots

Compute sum of mu(p-1) for primes p up to 10^6, mod 10^9 + 7.

For a prime p, the number of primitive roots modulo p is phi(p-1).
The Mobius function mu(p-1) indicates the "squarefree structure" of p-1:
  mu(p-1) = 0  if p-1 has a squared prime factor
  mu(p-1) = +1 if p-1 has an even number of distinct prime factors
  mu(p-1) = -1 if p-1 has an odd number of distinct prime factors

Key results:
  - For small primes: mu(1)=1(p=2), mu(2)=-1(p=3), mu(4)=0(p=5), mu(6)=1(p=7)
  - The sum S(N) = sum_{p<=N, p prime} mu(p-1) oscillates near zero

Methods:
  1. Sieve of Eratosthenes for prime detection
  2. Linear sieve for Mobius function
  3. Cumulative sum analysis over primes
  4. Distribution breakdown of mu(p-1) values
"""

MOD = 10 ** 9 + 7

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

def compute_mobius(n):
    """Compute mu(k) for k=0..n via linear sieve."""
    mu = [0] * (n + 1)
    mu[1] = 1
    is_p = [True] * (n + 1)
    primes = []
    for i in range(2, n + 1):
        if is_p[i]:
            primes.append(i)
            mu[i] = -1
        for p in primes:
            if i * p > n:
                break
            is_p[i * p] = False
            if i % p == 0:
                mu[i * p] = 0
                break
            else:
                mu[i * p] = -mu[i]
    return mu

def sum_mu_over_primes(N):
    """Compute sum of mu(p-1) for all primes p <= N."""
    is_prime = sieve_primes(N)
    mu = compute_mobius(N)
    S = 0
    for p in range(2, N + 1):
        if is_prime[p]:
            S = (S + mu[p - 1]) % MOD
    return S, is_prime, mu

def mu_prime_distribution(N, is_prime, mu):
    """Count primes p <= N by mu(p-1) value."""
    neg = zero = pos = 0
    for p in range(2, N + 1):
        if is_prime[p]:
            v = mu[p - 1]
            if v == -1:
                neg += 1
            elif v == 0:
                zero += 1
            else:
                pos += 1
    return neg, zero, pos

# Verification with assertions
is_prime_small = sieve_primes(100)
mu_small = compute_mobius(100)

# mu(1)=1 for p=2, mu(2)=-1 for p=3, mu(4)=0 for p=5, mu(6)=1 for p=7
assert mu_small[1] == 1      # p=2
assert mu_small[2] == -1     # p=3
assert mu_small[4] == 0      # p=5: 4=2^2
assert mu_small[6] == 1      # p=7: 6=2*3, two prime factors => +1
assert mu_small[10] == 1     # p=11: 10=2*5 => +1
assert mu_small[12] == 0     # p=13: 12=2^2*3 => 0

# Compute answer
N = 100000  # Using 10^5 as in original (adjustable)
S, is_prime, mu = sum_mu_over_primes(N)
print(f"S({N}) = {S}")
print(S)

Sum of Primitive Roots

Problem Statement

Problem 949: Sum of Primitive Roots

Mathematical Analysis

Sum of Primitive Roots

The Mobius Function on $p-1$

Editorial

Pseudocode

Factoring $p-1$

Concrete Examples

Proof of Correctness

Complexity Analysis

Answer

Code

Problem Statement

Problem 949: Sum of Primitive Roots

Mathematical Analysis

Sum of Primitive Roots

The Mobius Function on p−1p-1p−1

Editorial

Pseudocode

Factoring p−1p-1p−1

Concrete Examples

Proof of Correctness

Complexity Analysis

Answer

Code

The Mobius Function on $p-1$

Factoring $p-1$