sumphi

Sumphi is a term used in number theory to denote the cumulative totient function. It is defined as the sum of Euler's totient function φ(k) for k from 1 to n: S(n) = sum_{k=1}^n φ(k). The totient φ(k) counts the positive integers up to k that are coprime to k.

Sumphi connects to several classical results. A fundamental identity from the Dirichlet convolution φ * 1 = id implies that sum_{d|n} φ(d) = n for every positive n. The Farey sequence of order n has length 1 + S(n); thus sumphi(n) describes part of the structure of reduced fractions with bounded denominators.

Asymptotically, sumphi grows on the order of n^2. In particular, S(n) ~ 3 n^2 / π^2 as n → ∞, and more precisely S(n) = (3/π^2) n^2 + O(n log n).

Examples help illustrate the function. For n = 5, S(5) = φ(1) + φ(2) + φ(3) + φ(4) + φ(5) = 1 + 1 + 2 + 2 + 4 = 10. For n = 10, S(10) = 34.

Computing sumphi can be done naively by summing φ(k) for k up to n, which is straightforward for small n. For large n, algorithms use harmonic decomposition, grouping terms by ranges where floor(n/k) is constant, often combined with precomputation of φ up to a threshold. These methods yield faster evaluation, suitable for large-scale number-theory computations.

See also Euler’s totient function, Farey sequences, and divisor functions.