Project Euler Problem 447

Solution

Answer: 530553372

Step 1 — Characterise retractions

$f(f(x)) = a(ax+b)+b = a^2x + ab + b$.

The condition $f(f(x)) \equiv f(x) \pmod{n}$ for all $x$ requires:

$$n \mid a(a-1) \quad \text{and} \quad n \mid ab.$$

Condition 1 — $a$ must be idempotent in $\mathbb{Z}/n\mathbb{Z}$: $a^2 \equiv a$.

Because $\gcd(a,a-1)=1$, for each prime power $p^k | n$ we need $p^k \mid a$ or $p^k \mid (a-1)$. By CRT, the idempotents of $\mathbb{Z}/n\mathbb{Z}$ are exactly the elements obtained by choosing, independently for each prime-power component $p_i^{k_i}$, whether $a \equiv 0$ or $a \equiv 1 \pmod{p_i^{k_i}}$. There are $2^{\omega(n)}$ idempotents (including $0$), hence $2^{\omega(n)}-1$ nonzero idempotents in $0 < a < n$.

Condition 2 — given valid $a$, count $b$.

$n \mid ab$ iff $b \equiv 0 \pmod{n/\gcd(a,n)}$. There are exactly $\gcd(a,n)$ such $b$ in $[0,n)$.

For idempotent $a$ built from subset $S$ of prime-power components (those where $a \equiv 0$): $$\gcd(a,n) = \prod_{p^k \in S} p^k.$$

Step 2 — Closed form for R(n)

$$R(n) = \sum_{\substack{S \subsetneq {p_1^{k_1},\ldots,p_m^{k_m}}}} \prod_{p^k \in S} p^k = \prod_{i=1}^{m}(1 + p_i^{k_i}) - \prod_{i=1}^{m} p_i^{k_i} = \sigma^*(n) - n$$

where $\sigma^*(n) = \prod_{p^k | n}(1+p^k)$ is the unitary divisor sum (a multiplicative function).

Verification: $n=6=2\cdot3$, $\sigma^*(6)=(1+2)(1+3)=12$, $R(6)=6$. Direct count: $a\in{1,3,4}$, $b$-counts $1,3,2$ sum to $6$. ✓

Step 3 — Reduce F(N)

$$F(N) = \sum_{n=2}^{N}(\sigma^*(n) - n) = G(N) - \frac{N(N+1)}{2}$$

where $G(N) = \sum_{n=1}^{N}\sigma^*(n)$.

Step 4 — Compute G(N) via Möbius inversion

A unitary divisor $d$ of $n$ satisfies $d \mid n$ and $\gcd(d, n/d)=1$. So:

$$G(N) = \sum_{d=1}^{N} d \cdot #{n \le N : d | n} = \sum_{d=1}^{N} d \cdot #{m \le N/d : \gcd(m,d)=1}.$$

Applying Möbius inversion and writing $d = ek$:

$$G(N) = \sum_{e=1}^{\lfloor\sqrt{N}\rfloor} \mu(e)\cdot e \cdot S!\left(\left\lfloor\frac{N}{e^2}\right\rfloor\right)$$

where $S(M) = \sum_{k=1}^{M} k\left\lfloor\frac{M}{k}\right\rfloor = \sum_{m=1}^{M}\sigma(m)$.

Step 5 — Compute S(M) in O(√M)

Group $k$ by equal values of $q = \lfloor M/k\rfloor$. Each group is a contiguous range $[k_0, k_1)$ with $k_1 = \lfloor M/q\rfloor + 1$, contributing $q \cdot (k_0+k_1-1)(k_1-k_0)/2$. The while-loop runs $O(\sqrt{M})$ iterations.

Python implementation

from math import isqrt

MOD = 10**9 + 7

def solve(N):
    sqN = isqrt(N)

    # Linear sieve: Mobius function up to sqrt(N)
    mu = [0] * (sqN + 1)
    mu[1] = 1
    primes = []
    is_comp = bytearray(sqN + 1)
    for i in range(2, sqN + 1):
        if not is_comp[i]:
            primes.append(i)
            mu[i] = -1
        for p in primes:
            ip = i * p
            if ip > sqN:
                break
            is_comp[ip] = 1
            if i % p == 0:
                mu[ip] = 0
                break
            mu[ip] = -mu[i]

    def S(M):
        total = 0
        k = 1
        while k <= M:
            q = M // k
            nk = M // q + 1
            cnt = nk - k
            s = (k + nk - 1) * cnt // 2 % MOD
            total = (total + q * s) % MOD
            k = nk
        return total

    G = 0
    for e in range(1, sqN + 1):
        if mu[e] == 0:
            continue
        M = N // (e * e)
        if M == 0:
            break
        G = (G + mu[e] * e % MOD * S(M)) % MOD

    tri = N % MOD * ((N + 1) % MOD) % MOD * pow(2, MOD - 2, MOD) % MOD
    return (G - tri) % MOD

assert solve(10**7) == 638042271
print(solve(10**14))  # → 530553372

Complexity: $O(\sqrt{N}\log N)$ — sieve $O(\sqrt{N})$; main loop $\sum_{e \le \sqrt{N}} O(\sqrt{N/e^2}) = O(\sqrt{N}\log\sqrt{N})$.

Answer

$$\boxed{530553372}$$