Project Euler

Multiplicative Order Statistics

The multiplicative order ord_n(2) is the smallest positive k such that 2^k equiv 1 (mod n). Find sum_(n=2, gcd(2,n)=1)^10000 ord_n(2).

Source sync Apr 19, 2026

Problem #0980

Level Level 29

Solved By 314

Languages C++, Python

Answer 124999683766

Length 106 words

modular_arithmeticnumber_theoryalgebra

Starting from an empty string, we want to build a string with letters "x", "y", "z". At each step, one of the following operations is performed:

insert two consecutive identical letters "xx", "yy" or "zz" anywhere into the string;
replace one letter in the string with two consecutive letters, according to the rule: "x" "yz", "y" "zx", "z" "xy";
exchange two consecutive different letters in the string, e.g. "xy" "yx", "zx" "xz", etc.

A string is called neutral if it is possible to produce the string from the empty string after an even number of steps.

We define a sequence : and for .

Let . For each , a string of length is defined by translating the finite sequence via the rule: "x", "y", "z".

Let be the number of ordered pairs with such that the concatenated string is neutral.
For example, and .

Find .

Problem 980: Multiplicative Order Statistics

Mathematical Analysis

Multiplicative Order

Theorem (Euler). For $\gcd(a, n) = 1$ : $a^{\phi(n)} \equiv 1 \pmod{n}$ . Hence $\operatorname{ord}_n(a) \mid \phi(n)$ .

Theorem. $n$ is a primitive root modulo $p$ iff $\operatorname{ord}_p(n) = p - 1$ .

Order of 2

The multiplicative order of 2 modulo odd $n$ is a fundamental quantity in number theory. It determines:

The period of the binary expansion of $1/n$ .
The splitting behavior of the prime 2 in cyclotomic fields.

Average Order

Theorem (Hooley, Artin’s conjecture on average). The average of $\operatorname{ord}_n(2)$ over odd $n$ is $\sim c \cdot n$ for a constant $c$ related to Artin’s constant.

Derivation

Editorial

For each odd $n$ from 3 to 10000: compute $2^k \bmod n$ for $k = 1, 2, \ldots$ until $2^k \equiv 1$ .

Complexity Analysis

$O(N \cdot \bar{\phi})$ where $\bar{\phi} \sim N / (2\ln N)$ , giving $\sim O(N^2 / \log N)$ .

Answer

\boxed{124999683766}

C++ project_euler/problem_980/solution.cpp

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long total = 0;
    for (int n = 3; n <= 10000; n += 2) {
        long long val = 2;
        for (int k = 1; k < n; k++) {
            if (val == 1) { total += k; goto next; }
            val = val * 2 % n;
        }
        next:;
    }
    cout << total << endl;
    return 0;
}

Python project_euler/problem_980/solution.py

"""
Problem 980: Multiplicative Order Statistics

Compute sum of ord_n(2) for all odd n in [3, 10000],
where ord_n(2) is the multiplicative order of 2 modulo n
(the smallest positive k such that 2^k = 1 mod n).

Requires gcd(2, n) = 1, i.e., n must be odd.

Key properties:
    - ord_n(2) divides phi(n) (Euler's totient)
    - If n is prime p, ord_p(2) divides p-1
    - If ord_p(2) = p-1, then 2 is a primitive root mod p
    - The distribution of ord_n(2) / phi(n) reveals algebraic structure

Answer: computed by direct iteration

Methods:
    - ord2(n): Compute multiplicative order of 2 mod n
    - euler_phi(n): Euler's totient function
    - is_primitive_root_2(p): Check if 2 is a primitive root mod prime p
    - verify_divides_phi(n): Verify ord_n(2) | phi(n)
"""

from math import gcd


def ord2(n):
    """Compute the multiplicative order of 2 modulo n."""
    if n <= 1 or n % 2 == 0:
        return 0
    val = 2
    for k in range(1, n):
        if val == 1:
            return k
        val = val * 2 % n
    return n


def euler_phi(n):
    """Compute Euler's totient function phi(n)."""
    result = n
    p = 2
    temp = n
    while p * p <= temp:
        if temp % p == 0:
            while temp % p == 0:
                temp //= p
            result -= result // p
        p += 1
    if temp > 1:
        result -= result // temp
    return result


def is_prime(n):
    """Simple primality test."""
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

# Verification

# Known values
assert ord2(3) == 2    # 2^2 = 4 = 1 mod 3
assert ord2(5) == 4    # 2^4 = 16 = 1 mod 5
assert ord2(7) == 3    # 2^3 = 8 = 1 mod 7
assert ord2(15) == 4   # 2^4 = 16 = 1 mod 15

# Verify ord_n(2) divides phi(n) for small odd n
for n in range(3, 200, 2):
    if gcd(2, n) == 1:
        o = ord2(n)
        phi_n = euler_phi(n)
        assert phi_n % o == 0, f"ord_{n}(2) = {o} does not divide phi({n}) = {phi_n}"

# Main computation

N = 10000
total = 0
ns_list = []
ords_list = []
phi_list = []

for n in range(3, N + 1, 2):
    o = ord2(n)
    total += o
    ns_list.append(n)
    ords_list.append(o)
    phi_list.append(euler_phi(n))

print(total)