Gauss summation trick
The story goes that the young Gauss, told to add the numbers from 1 to 100, paired the first with the last, the second with the second-to-last, and so on: fifty pairs, each summing to 101, so 5050. In general, $1 + 2 + \dots + n = n(n+1)/2$, the triangular number $T_n$ (Wikipedia collects the history). It is the smallest closed form in mathematics, and it keeps coming back because so many sums in Project Euler are, at the bottom, a run of consecutive integers or of evenly spaced multiples. Each time you spot one, a loop of $n$ additions becomes three multiplications. In the four solved problems below it is never the whole solution, but it is always the step that turns a linear inner loop into $O(1)$.
The idea — pair the ends of an arithmetic series
Write the series forwards and backwards and add them term by term. Every column has the same sum, so
$$\sum_{k=a}^{b} k = \frac{(a + b)(b - a + 1)}{2},$$
"first plus last, times the count, halved". Two consequences carry most of the weight:
- Multiples of $s$ in a range. The multiples of $s$ in $(L, H]$ are $s \cdot k$ for $k = \lfloor L/s \rfloor + 1, \dots, \lfloor H/s \rfloor$. Their sum is $s$ times a Gauss sum, or with $f = \lfloor L/s \rfloor$ and $\ell = \lfloor H/s \rfloor$, $s\,(T_\ell - T_f)$.
- Higher powers. The same "telescope and solve" trick that derives $T_n$ gives Faulhaber's formulas, the next one being $\sum k^2 = n(n+1)(2n+1)/6$. The pattern stops being a two-line derivation, but it stays a closed form in $n$.
The division is always exact — one of $n$ and $n+1$ is even, and $n(n+1)(2n+1)$ is a multiple of 6 — so the formulas work in integer arithmetic with no rounding, if you divide last.
Four uses across the problems
6, sum square difference: the formula is the answer. The difference between $(\sum k)^2$ and $\sum k^2$ for $k \le n$ is $T_n^2$ minus the square-pyramidal number, both closed forms. The public Python is a single expression:
return str((n * (n + 1) // 2) ** 2 - (2 * n + 1) * (n + 1) * n // 6)
The loop it replaces is trivial at $n = 100$; the point is the habit. Once the problem is a formula, $n = 10^{9}$ costs the same as $n = 100$.
153, Gaussian integer divisors: Gauss sums inside a divisor-sum block. The problem reduces to
sums of the form $D(x) = \sum_{k \le x} k \lfloor x/k \rfloor$, the summatory divisor function. The
quotient $\lfloor x/k \rfloor$ takes only $O(\sqrt{x})$ distinct values, and on each run of $k$ where it is
constant the remaining factor is $\sum k$ over a contiguous range. That run is one Gauss sum,
q * (k + kmax) * (kmax - k + 1) // 2, so the whole of $D(x)$ is $O(\sqrt{x})$ instead of $O(x)$. Without the
closed form, quotient blocking would save nothing: you
would still add every $k$ in the block.
234, semidivisible numbers: sum of multiples in a band. Between consecutive primes $p < q$, every $n$ in $(p^2, q^2)$ has the same lower and upper prime square roots. The numbers in the band divisible by exactly one of $p$, $q$ are the multiples of $p$, plus the multiples of $q$, minus twice the multiples of $pq$ (inclusion–exclusion on a sum rather than a count). Each of those three is "multiples of $s$ in $(L, H]$", a Gauss sum. So the work is one $O(1)$ step per prime up to $\sqrt{\text{limit}}$; the bands themselves, about $10^{12}$ numbers in all, are never walked.
340, crazy function: summing a staircase. A McCarthy-91-style function, nested four calls deep below a threshold $b \approx 5.6 \times 10^{17}$, is summed over every $n \le b$. A small brute force shows the shape, and induction proves it: cut $[0, b]$ into blocks of width $a$ counted down from $b$, and $F(n)$ is $n$ plus a constant, plus a fixed step for every block $n$ sits below the top. So the sum splits in two: $\sum n$, a plain $T_b$, and the sum of the block index over all $n$, a staircase. Each full block of $a$ arguments contributes its index $a$ times, so the full blocks give $a\,(0 + 1 + \dots + (K-1)) = a\,T_{K-1}$, and the partial last block adds its index times its length. Gauss appears twice. The first time it sums the arguments, and the second time it sums the steps of a function that is constant on runs, the same move as 153's quotient blocks, except that here the runs all have the same width, so their count is the only loop left and it also folds into a closed form.
Python and C
- 6: identical arithmetic. Python's integers are exact at any $n$. C's
long longholds the intermediate $T_n^2$ only while $n \lesssim 7.7 \times 10^4$ — $T_n^2 \approx n^4/4$ must stay under $2^{63}$ — which is ample for the problem's input but not for an arbitrary one. - 153: the Gauss step is the same line in both. The difference is around it: Python memoises $D$
in a
dict, C in a hand-written open-addressing hash table, and C needs an exactisqrtll(asqrtlseed corrected by $\pm 1$) where Python hasmath.isqrt. - 234: here the languages split on width. The products inside
sum_multiplesand the running total outgrow 64 bits, so C computes them in__int128and needs its own decimal formatter, sinceprintfhas no conversion for it. Python just usesint. C also guards the band's upper end withupper > limit / upperbefore squaring, so that $q^2$ itself cannot overflow. - 340: only the last nine digits are wanted, so both languages reduce modulo $10^9$ as they go, and
Python does it too, so the two stay line for line. In C that is required, not a choice: $b$ fits in a
long longbut $b^2$ does not, so every factor is brought below $10^9$ before each multiply, keeping each product under $10^{18} < 2^{63}$.
How to reason about it
- Look for a contiguous range inside a sum. Arithmetic progressions hide behind "multiples of", "for every $k$ between", and any block where one factor is constant and the other is the index.
- Multiply before you divide, but divide before you overflow. The division by 2 or 6 is exact only on
the full product. In fixed width, either widen (
__int128) or divide the even factor first:(n / 2) * (n + 1)when $n$ is even,n * ((n + 1) / 2)otherwise. - Express a range as a difference of prefixes. $T_\ell - T_f$ is easier to get right than first-plus-last formulas with their off-by-one bounds, and it extends unchanged to $\sum k^2$.
- Under a modulus, halve before you reduce. With an odd modulus the $/2$ can become multiplication
by the modular inverse of 2. With an
even one, such as the $10^9$ of "the last nine digits" (340), 2 has no inverse. Then the only safe order
is to divide the even factor exactly first and reduce afterwards:
(x // 2 % m) * (y % m) % m. Reducing first and halving later gives the wrong residue. - It composes. Gauss sums are the leaf of bigger machinery: inclusion–exclusion over the multiples (234), quotient blocking (153), the staircase of a piecewise-shifted function (340), or modular arithmetic.