Project Euler

Retractions C

An affine map f_(n,a,b)(x) = ax + b (mod n) with a, b in {0, 1,..., n-1} is a retraction if f circ f = f, i.e., f(f(x)) equiv f(x) (mod n) for all x. Let R(n) denote the number of retractions for n...

Source sync Apr 19, 2026

Problem #0447

Level Level 26

Solved By 392

Languages C++, Python

Answer 530553372

Length 347 words

modular_arithmeticnumber_theorybrute_force

For every integer $n > 1$, the family of functions $f_{n,a,b}$ is defined by $$f_{n,a,b}(x)\equiv a x + b \pmod{n}\,\,\, \text{for } a,b,x \text{ integer and } 0 < a < n, 0\leq b < n, 0 \leq x < n$$

We will call $f_{n, a, b}$ a retraction if $f_{n, a, b}\left(f_{n, a, b} (x)\right) \equiv f_{n, a, b} (x) \pmod{n}$ for every $0 \leq x < n$.

Let $R(n)$ be the number of retractions for $n$.

Let $F(n) = \displaystyle \sum_{n = 1}^{N} R(n^4 + 4)$. We have $F(10^7)\equiv 638042271 \mod 1\,000\,000\,007$.

Find $F(10^{14})$. Give your answer modulo $1\,000\,000\,007$.

Problem 447: Retractions C

Mathematical Foundation

Theorem 1 (Retraction Characterization). The map $f(x) = ax + b$ is a retraction modulo $n$ if and only if:

$a^2 \equiv a \pmod{n}$ (idempotent multiplier), and
$ab \equiv 0 \pmod{n}$ (translation compatibility).

Proof. Composing: $f(f(x)) = a(ax + b) + b = a^2 x + (ab + b)$ . Setting $f(f(x)) \equiv f(x) = ax + b \pmod{n}$ for all $x$ : the coefficient of $x$ gives $a^2 \equiv a$ , and the constant term gives $ab + b \equiv b$ , i.e., $ab \equiv 0 \pmod{n}$ . $\square$

Theorem 2 (Product Formula). For $n = p_1^{e_1} \cdots p_r^{e_r}$ ,

R(n) = \prod_{i=1}^{r} (1 + p_i^{e_i}).

In particular, $R$ is a multiplicative arithmetic function.

Proof. The idempotent condition $a(a-1) \equiv 0 \pmod{n}$ decomposes via CRT. Since $\gcd(a, a-1) = 1$ , for each prime power $p^e \| n$ , we must have either $p^e \mid a$ or $p^e \mid (a-1)$ . This gives $2^{\omega(n)}$ idempotent values of $a$ in $\{0, 1, \ldots, n-1\}$ .

For each idempotent $a$ , the condition $ab \equiv 0 \pmod{n}$ has exactly $\gcd(a, n)$ solutions $b \in \{0, \ldots, n-1\}$ . By CRT, the total count factors over prime powers. At $p^e$ :

$a \equiv 0 \pmod{p^e}$ : $\gcd(a, p^e) = p^e$ , contributing $p^e$ valid values of $b$ .
$a \equiv 1 \pmod{p^e}$ : $\gcd(a, p^e) = 1$ , contributing $1$ valid value of $b$ .

Local factor: $p^e + 1$ . By CRT independence, $R(n) = \prod_{p^e \| n}(1 + p^e)$ . $\square$

Lemma 1 (Verification for Small Values).

$n$	Factorization	$R(n)$	Direct check
2	$2^1$	$1 + 2 = 3$	$a \in \{0,1\}$ : $\gcd(0,2)+\gcd(1,2) = 2+1 = 3$
3	$3^1$	$1 + 3 = 4$	$a \in \{0,1\}$ : $3 + 1 = 4$
4	$2^2$	$1 + 4 = 5$	$a \in \{0,1\}$ : $4 + 1 = 5$
6	$2 \cdot 3$	$(1+2)(1+3) = 12$	$a \in \{0,1,3,4\}$ : $6+1+3+2 = 12$

Proof. Direct enumeration confirms each entry. For $n = 6$ : the idempotents mod 6 are $a \in \{0, 1, 3, 4\}$ (by CRT: $a \bmod 2 \in \{0,1\}$ , $a \bmod 3 \in \{0,1\}$ ). The $\gcd$ values are $\gcd(0,6) = 6$ , $\gcd(1,6) = 1$ , $\gcd(3,6) = 3$ , $\gcd(4,6) = 2$ . Sum: $6 + 1 + 3 + 2 = 12 = (1+2)(1+3)$ . $\square$

Lemma 2 (Linear Sieve Correctness). Since $R$ is multiplicative with $R(p^e) = 1 + p^e$ , the linear sieve decomposition $n = p^e \cdot m$ with $\gcd(m, p) = 1$ and $p = \operatorname{spf}(n)$ gives the exact recurrence $R(n) = R(m) \cdot (1 + p^e)$ .

Proof. Multiplicativity of $R$ and the coprimality $\gcd(m, p^e) = 1$ (since $p = \operatorname{spf}(n)$ and $m = n/p^e$ has all prime factors $> p$ ) give $R(n) = R(p^e) \cdot R(m) = (1 + p^e) \cdot R(m)$ . $\square$

Editorial

The number of retractions R(n) for affine maps f(x) = ax + b mod n equals the number of pairs (a, b) with a^2 ≡ a (mod n) and ab ≡ 0 (mod n). Key result: R(n) = prod_{p^e || n} (1 + p^e), a multiplicative function. We compute sum_{n=2}^{N} R(n) mod (10^9 + 7) using a linear sieve. We linear sieve for smallest prime factor. We then compute R(n) using multiplicative structure. Finally, extract p^e from n.

Pseudocode

Linear sieve for smallest prime factor
Compute R(n) using multiplicative structure
Extract p^e from n

Complexity Analysis

Time: $O(N)$ . The smallest prime factor sieve runs in $O(N)$ with a linear sieve. Computing $R(n)$ for each $n$ takes $O(\log n)$ for extracting $p^e$ , but amortized over all $n$ this is $O(N)$ (each integer is divided by its smallest prime factor a bounded number of times). The summation is $O(N)$ .
Space: $O(N)$ for the arrays $\operatorname{spf}[1..N]$ and $R[1..N]$ .

Answer

\boxed{530553372}

C++ project_euler/problem_447/solution.cpp

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 447: Retractions B
 *
 * R(n) = number of affine retractions f(x) = ax + b (mod n), i.e.,
 *        pairs (a,b) with a^2 ≡ a (mod n) and ab ≡ 0 (mod n).
 *
 * Key formula: R(n) = prod_{p^e || n} (1 + p^e).
 * R is multiplicative, computed via linear sieve.
 *
 * Answer: sum_{n=2}^{10^7} R(n) mod (10^9 + 7).
 */

const long long MOD = 1e9 + 7;
const int N = 10000000;

int spf[N + 1];         // smallest prime factor
long long R_val[N + 1]; // R(n) mod MOD

void compute_spf() {
    for (int i = 0; i <= N; i++) spf[i] = i;
    for (int i = 2; (long long)i * i <= N; i++) {
        if (spf[i] == i) { // i is prime
            for (int j = i * i; j <= N; j += i) {
                if (spf[j] == j) spf[j] = i;
            }
        }
    }
}

int main() {
    compute_spf();

    R_val[1] = 1;
    long long total = 0;

    for (int n = 2; n <= N; n++) {
        int p = spf[n];
        // Extract p^e from n
        int m = n;
        long long pe = 1;
        while (m % p == 0) {
            m /= p;
            pe *= p;
        }
        // R(n) = R(m) * (1 + p^e) mod MOD
        R_val[n] = R_val[m] % MOD * ((1 + pe) % MOD) % MOD;
        total = (total + R_val[n]) % MOD;
    }

    cout << total << endl;

    // Verification for small cases
    // R(2) = 3, R(3) = 4, R(4) = 5, R(6) = 12
    assert(R_val[2] == 3);
    assert(R_val[3] == 4);
    assert(R_val[4] == 5);
    assert(R_val[6] == 12);
    assert(R_val[12] == 20);
    assert(R_val[30] == 72);

    return 0;
}

Python project_euler/problem_447/solution.py

"""
Problem 447: Retractions B

The number of retractions R(n) for affine maps f(x) = ax + b mod n equals
the number of pairs (a, b) with a^2 ≡ a (mod n) and ab ≡ 0 (mod n).

Key result: R(n) = prod_{p^e || n} (1 + p^e), a multiplicative function.

We compute sum_{n=2}^{N} R(n) mod (10^9 + 7) using a linear sieve.
"""

from math import gcd

MOD = 10**9 + 7

# --- Method 1: Linear sieve using smallest prime factor ---
def solve_linear_sieve(N: int, mod: int):
    """Compute R(n) for n=1..N via linear sieve. Return (R_array, total_sum)."""
    spf = list(range(N + 1))  # smallest prime factor
    for i in range(2, int(N**0.5) + 1):
        if spf[i] == i:  # i is prime
            for j in range(i * i, N + 1, i):
                if spf[j] == j:
                    spf[j] = i

    R = [0] * (N + 1)
    R[1] = 1  # R(1) = 1 (only a=0, b=0 trivially, but by convention)
    total = 0

    for n in range(2, N + 1):
        p = spf[n]
        # Find p^e exactly dividing n
        e = 0
        m = n
        while m % p == 0:
            m //= p
            e += 1
        # R(n) = R(m) * (1 + p^e)
        pe = p ** e
        R[n] = R[m] * ((1 + pe) % mod) % mod
        total = (total + R[n]) % mod

    return R, total

# --- Method 2: Brute force for small n (verification) ---
def R_brute(n: int):
    """Count retractions by brute force: pairs (a, b) with a^2≡a, ab≡0 mod n."""
    count = 0
    for a in range(n):
        if (a * a) % n != a % n:
            continue
        for b in range(n):
            if (a * b) % n == 0:
                count += 1
    return count

# --- Method 3: Product formula (verification) ---
def R_product(n: int):
    """Compute R(n) = prod_{p^e || n} (1 + p^e)."""
    if n <= 1:
        return 1
    result = 1
    d = 2
    temp = n
    while d * d <= temp:
        if temp % d == 0:
            pe = 1
            while temp % d == 0:
                pe *= d
                temp //= d
            result *= (1 + pe)
        d += 1
    if temp > 1:
        result *= (1 + temp)
    return result

# --- Compute answer ---
N = 10**7
R_arr, ans = solve_linear_sieve(N, MOD)

# --- Verify against brute force for small n ---
for n in range(2, 50):
    bf = R_brute(n)
    pf = R_product(n)
    assert bf == pf, f"Brute vs product mismatch at n={n}: {bf} vs {pf}"
    assert bf % MOD == R_arr[n], f"Sieve mismatch at n={n}: {R_arr[n]} vs {bf}"

# --- Verify product formula examples ---
assert R_product(2) == 3
assert R_product(6) == 12
assert R_product(12) == 20
assert R_product(30) == 72

print(ans)