Euler's totient function

Euler's totient function $\varphi(n)$ counts the integers in $[1, n]$ that are coprime to $n$ (OEIS A000010). That one-line definition undersells it. $\varphi$ is the size of the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^\times$, the count of reduced fractions with denominator $n$, the number of lattice directions a grid of size $n$ can point in, and the exponent that makes powers repeat modulo $n$ — so it turns up in problems about fractions, geometry, cryptography and towers of exponents that share no vocabulary at all. It earns a domain page rather than a formula footnote because the hard part is almost never computing $\varphi$; it is recognising that the quantity you are counting is $\varphi$, and then deciding which of its several faces you need.

The idea

Everything comes out of one closed form. $\varphi$ is multiplicative — $\varphi(ab) = \varphi(a)\varphi(b)$ when $\gcd(a,b) = 1$ — and on a prime power $\varphi(p^a) = p^{a-1}(p-1)$. Multiply those together over the factorisation of $n$:

$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right) = \prod_{i} p_i^{a_i - 1}(p_i - 1).$$

The left form is the one to internalise, because of what is missing from it: the exponents. The ratio $\varphi(n)/n$ depends only on the set of distinct primes dividing $n$ — its radical — not on their multiplicities. Every extremal question about that ratio therefore collapses into a question about which primes to include, and since $\frac{n}{\varphi(n)} = \prod_{p \mid n} \frac{p}{p-1}$ is a product of factors that shrink towards $1$ as $p$ grows, the cheapest way to push the ratio up is always to take the smallest primes, once each — a primorial. Problem 69 is that observation and nothing else; problem 243 is the same observation with a threshold attached, and problem 70 is its mirror image (minimise the ratio, so use as few and as large primes as possible — a semiprime $pq$ near $\sqrt{n}$).

Two identities do most of the remaining work:

$$\sum_{d \mid n} \varphi(d) = n, \qquad \varphi = \mu * \mathrm{id}, \quad\text{i.e.}\quad \varphi(n) = \sum_{d \mid n} \mu(d)\,\frac{n}{d}.$$

The first says the integers $1..n$ partition by their $\gcd$ with $n$: each $d \mid n$ contributes the $\varphi(n/d)$ values whose gcd is exactly $d$. That partition is why gcd- and lcm-flavoured sums keep resolving into $\varphi$ — problem 625 sums $\gcd(i,j)$ and lands on $\sum_{d \mid n} d\,\varphi(n/d)$; problem 448 does the same for $\operatorname{lcm}$. Read backwards, the same identity linearises a gcd: $\gcd(a, b) = \sum_{d \mid a,\, d \mid b} \varphi(d)$. Problem 994 counts triangles cut out by segments between two rows of points. The awkward part is a weighted double sum of $\gcd(a, b) - 1$ over lattice offsets, which counts the lattice points strictly between two cells. Substituting that sum for the gcd and swapping the order turns it into $\sum_d \varphi(d)\,F(d)\,G(d)$, where $F$ and $G$ each depend on only one side of the grid. A gcd inside a sum is rarely something to compute; it is an invitation to rewrite it as a sum over $\varphi$ and swap. The second is the Möbius view: $\varphi$ is inclusion–exclusion over the primes dividing $n$, which is exactly what "coprime to $n$" means. It also makes $\varphi$ a Dirichlet convolution of two simple functions, which is what the heavy summatory machinery below actually consumes.

Computing it

A table up to $N$: seed $\varphi[d] = d$ and apply each prime's factor to its multiples — a sieve of Eratosthenes that multiplies instead of striking. From the public problem 72:

euler_totients = list(range(max_d + 1))
for n in range(2, max_d + 1):
    if euler_totients[n] == n:              # untouched cell ⇒ n is prime
        for j in range(n, max_d + 1, n):
            euler_totients[j] = euler_totients[j] // n * (n - 1)

The trick worth stealing is the primality test: a cell still equal to its index has had no prime factor applied, so it is prime. The integer division comes first so the arithmetic stays exact. Cost is $O(N \log \log N)$; a linear sieve gets $O(N)$ if the $\log \log$ matters. This is the right tool when you need individual values $\varphi(n)$ for every $n$ up to some $10^7$–$10^8$, and it is what problems 72, 214 and 337 are built on.

A window $[A, A + W)$ far from the origin does not need the table from 1. Problem 531 needs $\varphi$ only on 5000 consecutive integers just above $10^6$, and the same idea scales to much higher windows. Run a segmented sieve with the primes up to $\sqrt{A + W}$. Each prime applies its factor to its multiples in the window, and you divide its powers out of a residual copy of each number. Whatever residual is left above 1 is the single large prime factor, which gets one final correction. The cost is the window plus $\sqrt{A}$, not $A$. In that problem the totients are just data, the residues of a generalised CRT system per pair. The window sieve is what keeps the data cheap enough that the quadratic pair loop dominates.

A single $\varphi(n)$ needs a factorisation, so it costs whatever factoring costs — fine for one number, hopeless for $10^{11}$ of them.

The summatory $\Phi(N) = \sum_{n \le N} \varphi(n)$ is the recurring wall. Sum the first identity over $n \le N$ and it inverts into

$$\Phi(N) = \frac{N(N+1)}{2} - \sum_{q = 2}^{N} \Phi\!\left(\left\lfloor N/q \right\rfloor\right).$$

The identity has a counting reading worth keeping: the $N(N+1)/2$ pairs $1 \le a \le b \le N$ each have exactly one reduced form, and the pairs whose gcd is $q$ are the coprime pairs below $\lfloor N/q \rfloor$. With quotient blocking (only $O(\sqrt N)$ distinct values of $\lfloor N/q \rfloor$ exist) and a sieved base case it evaluates in about $O(N^{2/3})$. That is the standard escape for problems 432, 512, 625 and 931, and the same skeleton as the Meissel–Lehmer prime count.

Problem 351 is the cleanest worked instance, and it shows three details the formula hides. First, the arguments the recursion ever reaches are exactly the quotients $\lfloor N/k \rfloor$, because $\lfloor \lfloor N/k \rfloor / d \rfloor = \lfloor N/(kd) \rfloor$. So instead of a memo dict you can keep an array indexed by $k$ and fill it from the largest $k$ down: every large value a step needs sits at index $kd$, already done. Second, the cutoff between sieve and recursion is a balance, not a constant. A sieve to $L$ costs $O(L)$, the recursion above it costs about $O(N/\sqrt{L})$, and the two meet at $L = N^{2/3}$. Third, $\Phi(N) \approx 3N^2/\pi^2$ outgrows 64 bits once $N$ passes about $5.5 \times 10^9$. The table-backed partial sums stay small, but the top-level values need wide integers (__int128 in C). Its main input is $10^8$, which is still within reach of a plain sieve. The recursion wins there anyway: it touches a table of $N^{2/3} \approx 2 \times 10^5$ entries rather than $10^8$ of them, and runs in milliseconds. When the summand is a messier multiplicative function than $\varphi$ itself, the generalisation is the Min-25 sieve or the Dirichlet hyperbola method.

Problem 512 shows the recurrence absorbing a restriction for free. Its sum of totients of powers collapses first, because $n^i$ has the same radical as $n$: $\varphi(n^i) = n^{i-1}\varphi(n)$, and modulo $n+1$ the powers of $n$ alternate in sign, so what is left is $\varphi(n)$ summed over the odd $n \le N$ only. Splitting off the odd terms looks like a fresh summatory problem, but the prime $2$ acts on $\varphi$ in a simple way: $\varphi(2m)$ is $\varphi(m)$ for odd $m$ and $2\varphi(m)$ for even $m$. Unrolling that gives $$\sum_{\substack{n \le N \\ n \text{ odd}}} \varphi(n) = \Phi(N) - \sum_{k \ge 1} \Phi\!\left(\lfloor N/2^k \rfloor\right),$$ and every $\lfloor N/2^k \rfloor$ is already one of the quotients the recursion fills in. The restriction costs $\log_2 N$ extra lookups. Before writing a new recurrence for a filtered sum, check whether the filter is a prime acting on $\varphi$, and so on arguments the table already holds.

The recurrence generalises along two axes, and recent problems need both.

  • Weights. Problem 994's block sum needs $\Phi_k(x) = \sum_{d \le x} d^k\varphi(d)$ for $k = 0, 1, 2$, because $F(d)G(d)$ is a quadratic in $d$ on each quotient block. The recursion carries over unchanged once you find the right convolution partner: $(\mathrm{id}^k\varphi) * \mathrm{id}^k = \mathrm{id}^{k+1}$, so $$\Phi_k(x) = \sum_{j \le x} j^{k+1} - \sum_{i=2}^{x} i^k\,\Phi_k\!\left(\lfloor x/i \rfloor\right).$$ This is the general shape of "Du's sieve": find a $g$ with an easy prefix sum such that $f * g$ also has an easy prefix sum. A second wrinkle is that the problem has two independent bounds, $m$ and $n$, so the block ends come from two families of quotients and the large-value table is built twice.
  • Twists. Problem 787 is a game on pile pairs $(a, b)$. A move turns out to be a step to a parent in the Stern–Brocot tree, so the positions with $a + b = n$ are the $\varphi(n)$ coprime splits. The losing ones number $\bigl(\varphi(n) + e(n)\bigr)/2$, where $e = \mu * \chi_4$ is the Möbius function convolved with the non-principal Dirichlet character mod 4. Neither sum needs a recursion of its own. Both $\Phi(x) = \tfrac12\bigl(1 + \sum_d \mu(d)\lfloor x/d \rfloor^2\bigr)$ and $\sum e$ are block sums over the Mertens function, and so is the odd-only totient sum from problem 512. Computing one summatory function, $M$, on the quotient set feeds every other one. When a problem needs several $\varphi$-like sums at once, express each as $\mu * (\text{something with a closed-form prefix})$ and share the $M$ table.

How a problem reaches it

Four routes, and it is worth learning to recognise which one you are on.

Counting coprime things. The statement is about reduced fractions, visible lattice points, or directions — problems 72, 243, 245, 351, 228, 441. Nothing here needs group theory; you need the closed form and a fast table. The tell is a $\gcd(\cdot,\cdot) = 1$ condition, explicit or disguised. Problem 351 hides it as "hidden from the centre" of a hexagonal orchard. Written in the lattice's own basis, a point $(a, b)$ is visible exactly when $\gcd(a, b) = 1$. The step that makes it a totient problem is choosing coordinates: take one $60^\circ$ sector and group its points by ring $s = a + b$. Then $\gcd(a, b) = \gcd(a, s)$, so ring $s$ holds exactly $\varphi(s)$ visible points. A sector shows $\Phi(n)$ points, and the hidden count is the total minus six of those. It is also a reminder to count the coprime side and subtract, even when the question asks for the other side. Problem 228 hides it as "distinct edge directions" of a Minkowski sum, a direction $p/q$ in lowest terms being contributed by exactly the $\varphi(q)$ choices of $p$.

Order of the multiplicative group. Here $\varphi$ is not being counted, it is being used as an exponent. Euler's theorem gives $a^{\varphi(m)} \equiv 1 \pmod m$ for $\gcd(a, m) = 1$, and the generalised (lifting) form

$$a^{x} \equiv a^{(x \bmod \varphi(m)) + \varphi(m)} \pmod m \qquad (x \ge \log_2 m)$$

drops the coprimality requirement, which is what lets problem 188 peel a tetration tower one level at a time under a descending chain of moduli $m, \varphi(m), \varphi(\varphi(m)), \dots$ — a chain that reaches $1$ in $O(\log m)$ steps, so the astronomically tall tower has only a handful of effective levels. Problem 182 uses the same group in RSA's clothing, counting unconcealed messages via $\gcd(e-1, p-1)$ over each prime factor. The caveat this family teaches: $\varphi(m)$ is a multiple of the true group exponent, the Carmichael function $\lambda(m)$, not necessarily equal to it — harmless when you only need some period, fatal when the problem asks for the smallest (problem 533).

Grouping by reduced denominator. Here $\varphi$ is a multiplicity. A sum over all residues $t \bmod n$ often depends on $t/n$ only through its reduced form $u/m$, with $m \mid n$ and $\gcd(u, m) = 1$. Grouping the terms by $m$ then gives each group exactly $\varphi(m)$ members. Problem 875 counts the zeros mod $n$ of an eight-variable quadratic form. The roots-of-unity filter turns that count into $\frac1n\sum_t |G(t, n)|^8$, where $G$ is a quadratic Gauss sum. Since $|G|$ depends only on the reduced denominator, the count becomes a Dirichlet convolution $\sum_{m \mid n} (n/m)^7\,w(m)$ with $w(m) = \varphi(m)\,m^3$ up to a 2-adic correction. The hard-looking exponential sum ends as a totient sieve plus quotient blocks. The tell is a filter $[z \equiv 0 \bmod n]$ written as a sum of roots of unity. Whenever the summand depends only on the order of $e(t/n)$, $\varphi$ is the count of each order. (This is also where Ramanujan sums come from.)

$\varphi$ as the object of study. The statement asks about $\varphi$'s own behaviour: iterate it (problem 214 — $\varphi(n) < n$ always, so the chain descends to $1$, and chain length is a dynamic-programming table over the sieve, with $L(p) = 1 + L(p-1)$ for primes), invert it (problem 248 — solve $\varphi(n) = 13!$ by searching over factorisations of the target into factors $p^{a-1}(p-1)$ rather than over candidate $n$), or constrain its value's shape (problems 342, 302 and 516 want $\varphi(n)$ to be a cube, an Achilles number, or 5-smooth). These are the hardest of the three, because the sieve gives you no leverage: the search space is the structure of the factorisation, and the algorithm is usually a recursive walk over prime choices with hard pruning.

Problem 516 shows how far that structure can carry you. Because $\varphi$ is multiplicative, $\varphi(n)$ is 5-smooth exactly when each factor $p^{a-1}(p-1)$ is. For $p \le 5$ that holds at any exponent. For a larger $p$ it forces $a = 1$ and needs $p - 1$ to be 5-smooth itself. So every admissible $n$ splits uniquely into a Hamming number times a square-free product of "good" primes of the form $h + 1$. Up to $10^{12}$ there are a few thousand Hamming numbers and a few hundred good primes. The search over $10^{12}$ integers becomes a depth-first walk over subsets of a few hundred primes, each paired with a prefix sum over the Hamming numbers. The same move, putting the condition on each prime-power factor of $\varphi(n)$ and then on the primes that can supply it, is what problems 248 and 342 need, only with less forgiving targets.

Problem 342 adds the idea that makes those searches tractable when the condition does not split cleanly: the coupling between primes runs one way. It asks for $n$ with $\varphi(n^2)$ a cube, and $\varphi(n^2) = \prod p^{2e_p - 1}(p - 1)$. Each prime $p$ of $n$ sets its own exponent, but its $p - 1$ leaks exponent into strictly smaller primes. So walk the primes of $n$ from the largest down, and track only each prime's exponent mod 3. Once the search passes a prime $q$, nothing chosen later can change $q$'s residue, so any $q$ still "owed" must be settled at that point or the branch dies. The top prime receives nothing from anyone, which forces its exponent to $2 \bmod 3$ and puts every prime under $\sqrt N$. The tree that remains is output-sensitive. One warning from that search generalises. A pruning bound that multiplies in every owed prime at its forced exponent looks natural but is wrong, because a smaller owed prime can be cancelled by a later $p - 1$ instead of entering $n$. Only the largest owed prime is truly committed. Test prunes like that against brute force at small $N$.

How to reason about it

  • Look for $\varphi$ before you look for a sieve. Most of these problems are a two-step: an awkward count collapses to $\sum \varphi$ or $\sum_{d \mid n} \varphi(d)$, and only then does the computational question begin. Getting the collapse wrong is far more expensive than getting the sieve slow.
  • Exponents are invisible to $\varphi(n)/n$, and that cuts both ways. It makes extremal searches tiny (only the radical matters, so candidates are primorial multiples), and it makes $\varphi$ badly non-injective — many $n$ share a totient, which is exactly why inverting it is a search rather than a formula.
  • Multiplicative, not completely multiplicative. $\varphi(2)\varphi(2) = 1 \ne \varphi(4) = 2$. Every convolution identity you use needs its coprimality hypothesis checked; the prime-power case must be handled separately in any recursive build.
  • Know your ceiling before you write the sieve. A list of $10^7$ totients is comfortable; $10^{11}$ is not, and the moment the bound crosses about $10^8$ the answer is a quotient-blocked recurrence or a structural search, never a bigger array. Problems 245, 432 and 448 all fail on this point first. If the problem only needs the sum $\Phi(N)$, reach for the recurrence well before that ceiling: problem 351 uses it at $10^8$, where a sieve would still fit, because a $2 \times 10^5$-entry table beats a $10^8$-entry one.
  • A modulus in the question does not license a modulus everywhere. The summatory recursions use only additions, subtractions and multiplications, so problems 625, 875 and 994 keep every table entry reduced. That is safe and keeps products within 64 bits. What must stay exact is anything that divides, compares or factors: the sieve's $\varphi \leftarrow \varphi - \varphi/p$, the halving in $N(N+1)/2$, and Faulhaber's denominators. Do those on true integers (or divide by an exact multiple, as 875's C port does by reducing $S_7$ modulo $24$ times the modulus and then dividing by $24$) before reducing.

Problems21 / 31

  • ● 0069 — Totient Maximum
  • ● 0070 — Totient Permutation
  • ● 0072 — Counting Fractions
  • ● 0180 — Golden Triplets
  • ● 0182 — RSA Encryption
  • ● 0188 — Hyperexponentiation
  • ● 0214 — Totient Chains
  • ● 0228 — Minkowski Sums
  • ● 0243 — Resilience
  • ● 0245 — Coresilience
  • ● 0248 — Euler's Totient Function Equals 13!
  • ○ 0302 — Strong Achilles Numbers
  • ○ 0337 — Totient Stairstep Sequences
  • ● 0342 — The Totient of a Square Is a Cube
  • ● 0351 — Hexagonal Orchards
  • ○ 0432 — Totient Sum
  • ○ 0441 — The Inverse Summation of Coprime Couples
  • ○ 0448 — Average Least Common Multiple
  • ● 0478 — Mixtures
  • ● 0512 — Sums of Totients of Powers
  • ● 0516 — $5$-smooth Totients
  • ● 0531 — Chinese Leftovers
  • ○ 0533 — Minimum Values of the Carmichael Function
  • ● 0625 — Gcd Sum
  • ○ 0652 — Distinct Values of a Proto-logarithmic Function
  • ○ 0715 — Sextuplet Norms
  • ○ 0756 — Approximating a Sum
  • ● 0787 — Bézout's Game
  • ● 0875 — Quadruple Congruence
  • ○ 0931 — Totient Graph
  • ● 0994 — Counting Triangles