Euler

More of the mathematics behind these problems traces to one man than to any other. Leonhard Euler did not just prove theorems; he built the tools we still reach for — the totient function, the theory of partitions, continued fractions, the first theorem of graph theory. The problems collected here are not a biography. They are the places where one of Euler's constructions is the shortest path to the answer, and where knowing his identity turns a search into a formula.

The thread running through almost all of them is the same instinct: replace a count you cannot enumerate with a structure you can compute. A generating function becomes a recurrence; a multiplicative function becomes a product over primes; an irrational becomes a periodic sequence of integers. Each section below is one instance of that move.

Multiplicativity: the totient

Euler's totient φ(n) counts the integers up to n that are coprime to n. Its power is that it is multiplicative and has a closed product form,

φ(n) = n · ∏ (1 - 1/p)     over the distinct primes p | n

so you never enumerate the coprime residues — you factor n and multiply. Problem 69 (Totient Maximum) is this identity read backwards: since n/φ(n) = ∏ p/(p-1), the ratio is maximised by piling in the smallest primes, so the answer under a bound is a primorial and the loop is a handful of multiplications:

result = 1
for prime_num in primes_generator():
    if (result := result * prime_num) > limit:
        result //= prime_num
        break

The same function carries Euler's theorem — a^φ(n) ≡ 1 (mod n) for gcd(a, n) = 1, the generalisation of Fermat's little theorem — which is what lets the RSA problem (182) and the hyperexponentiation problem (188) collapse an astronomical exponent down modulo φ(n).

Just as often, nobody asks for φ at all and it appears anyway. The reason is Gauss's identity Σ_{d|n} φ(d) = n: sort the fractions t/n by their reduced denominator, and exactly φ(m) of them have denominator m. So whenever a sum runs over pairs or residues and the summand depends only on a gcd, grouping by that gcd turns it into a Dirichlet convolution with φ. Problem 625 (Gcd Sum) is the plain case. Σ_{i≤j} gcd(i, j) becomes Σ_k φ(k)·T(⌊N/k⌋) with T the triangular numbers, and from there it is the totient-summatory machinery of problem 351 below. Problem 875 (Quadruple Congruence) is the same move in a less obvious place. It counts zeros of an eight-variable quadratic form mod n, and a roots-of-unity filter turns that count into a sum of quadratic Gauss sums over t mod n. A Gauss sum's size depends only on the reduced denominator of t/n, so grouping by that denominator contributes a factor φ(m). The count collapses to a convolution of two multiplicative functions, and what remains is one totient sieve. Problem 994 (Counting Triangles) gets there by geometry. It counts triangles cut out by segments between two parallel rows of points, and the only hard part is discarding triples of segments that pass through one point. Under the duality that sends a segment (i, j) to the cell (i, j) of an index grid, concurrent segments become collinear cells, and the number of lattice cells strictly between two cells at offset (a, b) is gcd(a, b) - 1. So the correction is a gcd sum again, Σ (m-a)(n-b)·gcd(a, b), and gcd = Σ_{d|·} φ(d) turns it into a sum over d of φ(d) times a weight that is a quadratic in d on each quotient block.

A gcd hides behind a geometric question more often than you would expect. In problem 787 (Bézout's Game) a move splits the vector (a, b) into two pieces of determinant ±1. That makes the pieces neighbours in the Stern–Brocot tree and (a, b) their mediant, so the positions with pile total n are exactly the φ(n) coprime splits of n. The game's losing positions turn out to be a fixed fraction of those φ(n), corrected by a small multiplicative term.

Evaluating φ at one point is the easy direction. The problems push it three other ways, and each needs a different tool:

Across a range. When a problem needs φ for every n up to a bound, sieve it (a modified Sieve of Eratosthenes seeding φ(p) = p-1, or the linear sieve below) rather than factoring each number in turn. If the range is a narrow window far from zero, as in problem 531 (Chinese Leftovers, φ on 5000 numbers just above 10⁶), segment the sieve. Run the primes up to √end across the window, applying φ ← φ - φ/p and dividing p out of a residual copy. Whatever residual is left above 1 is the one large prime factor, and it gets the last correction.
Summed, past where a sieve fits. Often the range is wanted only as a total. Problem 351 (Hexagonal Orchards) is that case in disguise: a lattice point is hidden from the centre exactly when its coordinates share a factor, so each ring of a hexagonal sector shows φ(s) points and the hidden count is the total minus six copies of the totient summatory function Φ(n) = Σ φ(s). You do not need the individual values. Every pair 1 ≤ a ≤ b ≤ v has exactly one reduced form, which gives Σ_d Φ(⌊v/d⌋) = v(v+1)/2. That identity mentions Φ only at the O(√n) distinct quotients ⌊n/k⌋, so a sieve up to n^(2/3) plus quotient blocking for the larger values brings the cost down to O(n^(2/3)). The sieve becomes the bottom tier of the algorithm instead of the whole of it. Problem 512 (Sums of Totients of Powers) reaches the same machinery from an unpromising-looking start. Because n^i has the same primes as n, φ(n^i) = n^(i-1)·φ(n), and modulo n+1 the factor n is just -1. The alternating sum then collapses to φ(n) for odd n and 0 for even n, so the task is Φ restricted to odd arguments. The restriction is also free. From φ(2m) = φ(m) for odd m and 2φ(m) for even m, the odd-only sum is Φ(N) - Σ_k Φ(⌊N/2^k⌋), and every ⌊N/2^k⌋ is a quotient the recursion has already computed.
Summed with a twist. The same quotient machinery survives a weight, a congruence condition or a character, as long as you can name the Dirichlet convolution that cancels it. Problem 994 needs Φ_k(x) = Σ d^k·φ(d) for k = 0, 1, 2. Because (d^k·φ) * id^k = id^(k+1), each Φ_k obeys the same recursion as Φ with power sums in place of triangular numbers (often called Du's sieve). Problem 935 (Rolling Square) reduces a rolling square's return time to a rotation number p/q, and the answer counts coprime pairs in a triangle with the bound depending on q mod 4. Removing coprimality by Möbius inversion is the standard move. The residue condition is what changes it: an odd common divisor keeps q in its class, a divisor 2e moves it predictably, and multiples of 4 have μ = 0. Every term becomes a sum over odd e only, and that needs an odd-only Mertens function, which has its own convolution identity. Problem 787 goes one step further. Its correction term is μ * χ₄, the Möbius function convolved with the non-principal Dirichlet character mod 4. You can only find it by tabulating small cases and reading off the prime powers. Once you have it, swapping the order of summation leaves Σ μ(d)·X(⌊N/d⌋), where X is the trivial partial sum of χ₄, and that is one more block loop over the Mertens values that Φ already needed.
Backwards. Problem 248 asks for every n with φ(n) = 13!. The product form φ(n) = ∏ p^(a-1)(p-1) turns this inversion into a factorisation of the target: a prime can occur in n only if p-1 divides it, so the alphabet is "divisors plus one that are prime" (a few hundred numbers), and a depth-first descent over that alphabet emits every solution exactly once. One subtlety catches people: φ(2) = 1, so φ(2m) = φ(m) for odd m. A descent that stops the moment the residual reaches 1 loses half the answers. Problem 516 runs the same inversion against a set of targets: it sums the n ≤ 10¹² whose φ(n) is 5-smooth. Read factor by factor, the product form decides membership. Powers of 2, 3 and 5 are always allowed. Any other prime q must appear to the first power only, and q-1 must itself be 5-smooth. The alphabet is "Hamming numbers plus one that are prime", a few hundred of them, and each admissible n splits uniquely as a Hamming number times a squarefree product from that alphabet. A depth-first walk over the products plus a prefix sum over the Hamming numbers replaces a scan of 10¹² integers.
As a constraint. Problem 245 (Coresilience) asks when (n - φ(n)) / (n - 1) is a unit fraction, with n up to 2·10¹¹, which is far beyond any sieve. Here the product form is used for proofs. If p² | n, then p divides both n and n - φ(n), so qualifying n are squarefree. With three or more prime factors, every prefix must keep φ(m)/m > 1/2, which rules out even n and prunes whole subtrees. The search then constructs candidates (solving for the largest prime given the rest) instead of filtering a range. Problem 342 (the totient of a square is a cube) puts the constraint on exponents mod 3. The useful fact there is the direction of the coupling. φ(p^e) touches only p itself and the primes of p-1, and all of those are smaller than p. Search the primes of n from the largest down, and every prime you pass is settled for good. That makes the largest prime's exponent ≡ 2 (mod 3), so every prime involved is below √N. Each smaller prime that a p-1 has left with a nonzero residue must then be balanced before the search drops past it.

The common lesson is that once the bound is too large to sieve, the multiplicative structure stops being a way to evaluate φ and becomes a way to avoid evaluating it at all.

Generating functions: partitions and the pentagonal number theorem

Euler founded the theory of integer partitions by writing the count p(n) as a generating function, ∏ 1/(1-x^k) = Σ p(n) x^n. The naïve recurrence from that product is a full convolution. His pentagonal number theorem makes it sparse: the reciprocal product has almost all coefficients zero, leaving

p(n) = Σ (-1)^(k-1) · [ p(n - g(k)) + p(n - g(-k)) ],   g(k) = k(3k-1)/2

where g(k) runs over the generalized pentagonal numbers. Only O(√n) terms per n survive, so p(n) up to N costs O(N√N) instead of O(N²). Problem 78 (Coin Partitions) is that recurrence almost verbatim — the whole solve is the inner loop over pentagonal g(k), reduced mod the divisor:

while (pent := pentagonal(k)) <= n:
    partition_value += (-1) ** (k - 1) * partitions[n - pent]
    # ... and the paired term for g(-k)
    k += 1

Problems 76 and 77 are partitions under a constraint (which parts are allowed); 45 and 76/78 are where the pentagonal (and its cousin figurate) numbers show up directly.

Generating functions also count partitions that you never get to see. In problem 1010 (March of the Penguins), the penguins' displacements form a partition and each legal step adds one box to its Young diagram, so the answer is a product of hook-length counts over roughly 10¹⁶ partitions. That product depends only on how many boxes have each hook length across all of the partitions. Marking one box cuts the diagram around it into independent pieces, each a partition that fits in a rectangle, and the count of such pieces is a coefficient of a Gaussian binomial, Euler's product cut down to a finite box. You build the polynomials with a two-term recurrence, convolve them, and read off the counts. The partitions themselves are never listed, which is the same move as the pentagonal recurrence: a statistic of the whole family, computed through its generating function.

Not every partition count has a product to expand. Problem 333 (Special Partitions) allows only parts of the form 2^i 3^j, none dividing another. Divisibility between such parts is the componentwise order on exponent pairs, so a valid partition is an antichain in the grid, and no generating function falls out. A bijection does the job instead. The odd parts are pure powers of 3, and any two of those divide each other, so a partition has at most one odd part. For even n it has none, and halving every part maps the partitions of n exactly onto those of n/2. For odd n you peel off the single 3^b, then halve the rest, with a cap on the 3-exponents. Every index on the right is below n/2, so the counts fill a table block by doubling block. The lesson Euler's own bijections teach (distinct parts ↔ odd parts) still holds: when a product formula is missing, look for a map that shrinks the problem.

Some problems optimise over partitions instead of counting them, and the useful structure there is the staircase m, m+1, …, m+k-1, the cheapest way to write k distinct parts. Problem 688 (Piles of Plates) only needs its total km + k(k-1)/2. Any leftover goes on the top pile, so the largest feasible bottom pile is a single floor, and swapping the order of summation leaves O(√N) closed-form terms. Problem 374 (Maximum Integer Partition Product) asks for the distinct-part partition with the largest product, and two exchange arguments settle it. A part 1 is better merged into the largest part, and a gap of two or more between neighbours closes profitably, because (a+1)(b-1) > ab when b - a ≥ 2. The optimum is therefore a staircase with at most one value missing. That turns f(n) into a factorial divided by the missing value, and a block of n sums to a harmonic number times a factorial. The product j!·H_j is the Stirling number [j+1, 2]. It has an integer recurrence, so the sum over 10¹⁴ values of n needs no modular inverses in its loop.

Partitions also appear as the orbits of a symmetry. Problem 564 (Maximal Polygons) averages the largest area of a polygon over random compositions of its perimeter into sides. The maximum is the cyclic polygon, and permuting its sides only reorders isosceles triangles around the centre. So the area depends on the multiset of sides, which is a partition of the excess length, and each partition stands for n!/∏ m_j! compositions. A sum over C(2n-4, n-1) orderings becomes a weighted sum over p(n-3) partitions. Whenever a statistic is symmetric in its arguments, enumerate the partitions and weight each one by a multinomial, rather than enumerating the compositions.

Continued fractions

In De fractionibus continuis Euler put continued fractions on a systematic footing: every rational terminates, quadratic irrationals become periodic, and the truncations — the convergents — are the best rational approximations for their size. His discovery that

e = [2; 1, 2, 1, 1, 4, 1, 1, 6, ...]

has a clean pattern is the whole of problem 65, where you build the n-th convergent with exact rational arithmetic and read a digit off its numerator. The √2 and Pell-equation problems (57, 64, 66) walk the periodic expansion of √D, and generate convergents with the standard recurrence hₙ = aₙ·hₙ₋₁ + hₙ₋₂ rather than re-evaluating the nested fraction each step.

The convergent recurrence is a product of 2×2 matrices, and that view also lets you do arithmetic on a continued fraction without ever turning it into a number. Problem 946 (Continued Fraction Fraction) wants the terms of β = (2α+3)/(3α+2), a Möbius transformation of a continued fraction α whose terms are only 1s and 2s, out to 10⁸ terms. Expanding a rational truncation would need integers with hundreds of millions of digits. Gosper's algorithm streams instead. It holds the map y = (ax+b)/(cx+d), ingests a term of α when the next output is still undetermined, and emits a term of β as soon as the bounds on the unread tail pin it down. Every step multiplies by a determinant-±1 matrix, so |ad - bc| never changes, and with inputs restricted to {1, 2} the coefficients stay bounded. The process becomes a finite-state machine (32 states), so a long run of identical inputs falls into a cycle that you can skip arithmetically. You only see that the state is finite because you treat the continued fraction as a product of matrices.

The rest of the reach

Euler's fingerprints are wider than number theory:

Amicable numbers. Before Euler only three amicable pairs were known; in one 1750 memoir he found fifty-eight more. Problems 21 and 95 chase the same divisor-sum function d(n) — 21 for the pairs, 95 for the longer "sociable" chains.
Graph theory. The Seven Bridges of Königsberg gave the subject its first theorem: a connected graph has an Eulerian path iff it has at most two odd-degree vertices. Problem 289 counts such trails on a grid of loops.
Eulerian numbers. Distinct from the paths, the Eulerian numbers ⟨n k⟩ count permutations by their number of ascents; they surface in problem 158.
The linear sieve. Euler's refinement of Eratosthenes crosses off each composite exactly once, via its smallest prime factor, giving both the primes and a smallest-prime-factor table in a genuine O(n) pass — the workhorse behind problems 153, 549 and 745, in 342 the table that factors every p-1 the totient search needs, and in 935 the bottom tier (a sieve of μ up to N^(2/3)) under the odd Mertens recursion.

How to reason about it

The lesson is not "memorise Euler's results" but recognising the shape that invites one:

A count that is multiplicative — factor and take a product; never enumerate. The totient is the archetype.
A sequence with a product generating function — look for a sparse recurrence. The pentagonal number theorem is the model: an infinite product whose reciprocal is almost all zeros.
A sum over pairs or residues whose summand depends only on a gcd or reduced denominator: group by it, and φ appears as the multiplicity. That gives a Dirichlet convolution, which you then sieve or sum over quotients.
A best rational approximation or a Pell equation — reach for continued fractions and their convergents. Arithmetic on a continued fraction — stream it through Gosper's matrix algorithm, and look for a finite state space when the inputs are bounded.
A partition count with no product generating function — look for a bijection (halving, peeling off a forced part) that maps n onto smaller instances.
A huge exponent modulo n — reduce the exponent mod φ(n) by Euler's theorem before you compute anything.
A sum of a multiplicative function to a bound too large to sieve — look for an identity over the quotients ⌊n/d⌋ and evaluate it sublinearly. If the sum carries a polynomial weight, a congruence condition or a character, find the convolution partner that cancels it: id^k for d^k·φ, an odd-only Mertens function for a mod-4 split.
An optimisation over partitions: use exchange arguments to pin the optimum down to a staircase, then sum the closed form block by block.
An average over orderings of a symmetric statistic: enumerate partitions instead, each weighted by its multinomial count.
A multiplicative function run backwards or used as a constraint — enumerate factorisations of the target (or of a whole family of targets, such as the smooth numbers), or derive the structural facts (squarefree, parity, a ratio bound) that let you build candidates instead of scanning for them.

The pitfall in every case is doing the brute-force version first. These identities exist precisely because the direct count is infeasible; the win comes from spotting the structure before writing the loop.

Problems48 / 71

● 0021 — Amicable Numbers
● 0031 — Coin Sums
● 0045 — Triangular, Pentagonal, and Hexagonal
● 0057 — Square Root Convergents
● 0064 — Odd Period Square Roots
● 0065 — Convergents of $e$
● 0066 — Diophantine Equation
● 0069 — Totient Maximum
● 0070 — Totient Permutation
● 0072 — Counting Fractions
● 0076 — Counting Summations
● 0077 — Prime Summations
● 0078 — Coin Partitions
● 0095 — Amicable Chains
● 0153 — Investigating Gaussian Integers
● 0158 — Lexicographical Neighbours
● 0175 — Fractions and Sum of Powers of Two
● 0180 — Golden Triplets
● 0181 — Grouping Two Different Coloured Objects
● 0182 — RSA Encryption
● 0188 — Hyperexponentiation
● 0192 — Best Approximations
● 0214 — Totient Chains
● 0228 — Minkowski Sums
● 0243 — Resilience
● 0245 — Coresilience
● 0248 — Euler's Totient Function Equals 13!
○ 0289 — Eulerian Cycles
○ 0302 — Strong Achilles Numbers
○ 0325 — Stone Game II
● 0333 — Special Partitions
○ 0337 — Totient Stairstep Sequences
● 0342 — The Totient of a Square Is a Cube
● 0351 — Hexagonal Orchards
● 0374 — Maximum Integer Partition Product
○ 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
● 0549 — Divisibility of Factorials
● 0564 — Maximal Polygons
○ 0591 — Best Approximations by Quadratic Integers
○ 0614 — Special Partitions 2
○ 0618 — Numbers with a Given Prime Factor Sum
● 0625 — Gcd Sum
○ 0629 — Scatterstone Nim
○ 0652 — Distinct Values of a Proto-logarithmic Function
○ 0656 — Palindromic Sequences
● 0688 — Piles of Plates
○ 0715 — Sextuplet Norms
● 0745 — Sum of Squares II
○ 0756 — Approximating a Sum
● 0772 — Balanceable $k$-bounded Partitions
● 0787 — Bézout's Game
○ 0799 — Pentagonal Puzzle
○ 0840 — Sum of Products
○ 0859 — Cookie Game
● 0875 — Quadruple Congruence
○ 0890 — Binary Partitions
○ 0911 — Khinchin Exceptions
○ 0931 — Totient Graph
● 0935 — Rolling Square
● 0939 — Partisan Nim
● 0946 — Continued Fraction Fraction
○ 0958 — Euclid's Labour
● 0994 — Counting Triangles
● 1010 — March of the Penguins