Reduce algebraically before coding

Before you write a loop, ask what the loop is really computing — and whether the mathematics will hand you the answer with less work, or none. Reducing algebraically before coding is the habit of spending five minutes with pen and paper on a problem's structure so the program that follows is smaller, tighter, or gone entirely. The payoff runs from the modest (one nested loop removed) to the total (an O(n) scan collapsed to a formula), but it is the same move every time: simplify the math first, because the cheapest loop is the one you never have to run. Past the first hundred problems it stops being optional — the search spaces run to $2^{669}$ subsets or $10^{24}$ index pairs, and the only program that finishes is the one written after the reduction.

The reduction, in degrees

A reduction is any algebraic step that shrinks the work before it becomes code. The problems below reach for it at four escalating strengths.

Eliminate a variable. A constraint that ties two unknowns together lets you solve for one and delete a whole dimension of search. In Special Pythagorean Triplet the sum condition $a + b + c = S$ means $c$ is never searched — it is computed, $c = S - a - b$ — so a naive three-nested-loop hunt over $(a, b, c)$ becomes a two-loop scan over $(a, b)$, $O(S^3)$ down to $O(S^2)$. Nothing clever happened; one line of algebra removed an entire loop.

Prune the domain. The same ordering $a < b < c$ that eliminates $c$ also bounds what is left: $a$ cannot exceed $S/4$ and $b$ cannot exceed $S/2$, or no valid larger values fit. Deriving the tightest bounds before the loop is written keeps the search inside the region that can actually contain an answer. The cheap-checks-first and exploit-symmetry takeaways are this same instinct pointed at the loop body and the coordinate system. A domain can also be pruned by type. Integer Ladders promises integers for the two ladders, the crossing height $h$ and the street width, but says nothing about the heights $a$ and $b$ the ladders reach. A short irrationality argument settles it: $1/a + 1/b = 1/h$ cannot hold with an integer $h$ unless both heights are integers too. That unstated fact makes each ladder a Pythagorean triple, and a problem about real geometry becomes pairs of triples that share a leg.

Exploit structure to skip work. Sometimes the sequence itself has a pattern that lets you step over most of it. Even Fibonacci Numbers never tests a single term for evenness: the parities of the Fibonacci sequence run odd, even, odd with period three forever, so every third term is even, and expanding the recurrence three times gives a direct rule $E(k+1) = 4E(k) + E(k-1)$ that walks the even terms alone. The divisibility test is not optimised — it is derived away. The same move carries GCD Sequence to $10^{15}$: writing $g(k) = k + d$ turns each step's $\gcd(j, g(j-1))$ into $\gcd(j, d-1)$ with $d$ fixed, so the long runs of $+1$ steps end exactly at the next multiple of a prime factor of $d-1$. The program jumps from event to event — a few hundred factorisations in place of a quadrillion gcds.

Close the form. At the far end, the structure is regular enough that the loop disappears into a single expression. Counting Rectangles sees that a sub-rectangle is fixed by choosing two of $H+1$ horizontal and two of $W+1$ vertical grid lines, so the count factors into $T(H)\cdot T(W)$ with $T(n) = \tfrac{n(n+1)}{2}$ — two independent triangular numbers instead of a two-dimensional enumeration. Number Spiral Diagonals sums each ring's four corners in closed form to $\tfrac{N(N(4N+3)+8)-9}{6}$, an $O(N^2)$ grid replaced by one arithmetic line. Sums of Totients of Powers defines $f(n)$ as a sum of $n$ totients of powers modulo $n+1$; with $\varphi(n^i) = n^{i-1}\varphi(n)$ and $n \equiv -1$, the terms alternate in sign and cancel, leaving $\varphi(n)$ for odd $n$ and $0$ for even — the defining sum is never evaluated at all. The same move scales a long way: Odd Triplets asks about roughly $10^{24}$ pairs $(n, k)$, but only about the parity of a subset count, and two applications of Lucas' theorem reduce that parity to $\binom{n-1}{k-1} \bmod 2$ — so each admissible $n = 4t + 1$ contributes $2^{\mathrm{popcount}(t)}$ pairs, and nothing is ever counted one at a time. This is the endpoint the closed-form-over-iteration takeaway is about; reducing before coding is the wider discipline that reaches it — and that is content to stop one step short when the algebra will not close all the way.

Reductions that change the question

The four degrees above simplify a computation that is already the right one. The harder problems on the list mostly need something earlier: a reduction that changes what is computed before any of it is simplified. Eight such moves recur.

Restate the condition. The question as posed is often the awkward form of an easier one. Twenty-two Foolish Primes asks for 22 of the 25 primes to be away from home; "3 are at home" is the same event, and fixed points are what inclusion–exclusion counts well. Coresilience asks for a unit fraction, which is a divisibility, which forces $n$ to be squarefree and turns the search into a construction. A Game of Chance asks whether a deck is fair; that is a statement about the parity of the turn count, the parity factors over the deck's single-colour runs, and the run bias obeys a small recurrence that is zero at exactly one length — so "fair" becomes a pattern-avoidance count with no probability left in it. A Long Row of Dice asks which dice end on face 1; that is $d(k) \equiv 1 \pmod 6$, which forces $k = m^2$, and the residue of $\prod(2a_i + 1)$ modulo 3 forces $m = c^3 q^2$ with $\mu(q) = +1$ — a dice simulation becomes a lattice count under a hyperbola. Idempotents asks for the largest $a$ with $a^2 \equiv a \pmod n$; since $a$ and $a-1$ are coprime, every prime power of $n$ divides one or the other, so the idempotents are exactly the coprime splits $n = d \cdot e$, and a per-$n$ search becomes a sweep over pairs. Largest Prime asks for the largest prime dividing two successive terms of $n^2 + k^2$; a common divisor divides their difference $2n + 1$, which pins $n \equiv -\tfrac12 \pmod p$, and substituting back leaves the condition $p \mid 4k^2 + 1$ — a search over $n$ for every $k$ becomes the largest prime factor of one polynomial value. A condition stated over a sliding window can be differenced. Window into a Matrix II asks that every $2 \times k$ window of a 16-row binary matrix sum to $k$. Subtract two windows that overlap in all but one column and the condition becomes $c_{j+k} = c_j$ for the column sums of each pair of rows, so the columns fall into $k$ residue classes that behave independently. Flipping the bits of every other row then turns "adjacent rows sum to $K$" into "every row has the same weight", and a constraint on $10^{16}$ columns becomes one convolution of length $k$. A limit can be restated too. Prime Factor and Exponent averages a function over all integers, which is a natural density. The Chinese remainder theorem makes divisibility by distinct primes independent events, so the average becomes a series over primes, and the statement's infinite sum over $K$ is a geometric series that moves inside it. A Polynomial Modulo the Square of a Prime asks for the least root of $n^2 - 3n - 1$ modulo $p^2$; completing the square makes that a square root of 13, found modulo $p$ and lifted to $p^2$ by one Hensel step, and quadratic reciprocity turns "does 13 have a root modulo $p$?" into a lookup on $p \bmod 13$ — a scan of $p^2$ candidates becomes a few modular powers per prime. A restatement can also change the kind of collection being summed. Fibonacci Subwords sums over the $k+1$ distinct length-$k$ factors of the Fibonacci word, a set that would need deduplicating if listed; reading the factors off the arcs of a rotation of the circle makes them the $k+1$ consecutive windows of one explicit, almost-palindromic word, and a sum over sliding windows is a running total, linear in a small state vector and so walkable block by block along the Zeckendorf decomposition of $k$. Each restatement is a line of algebra, and each one is where the problem actually gets solved.

Translate into a known object. Sometimes the restated problem is one that mathematics has already solved under another name. The Diophantine-reciprocal problems 108 and 110 become divisor counting. Cross Flips is Lights Out, and so linear algebra over $\mathbb{F}_2$. Chandelier is divisibility by a cyclotomic polynomial. March of the Penguins is a walk through Young diagrams, whose complete marches are standard Young tableaux counted by the hook length formula — so about $10^{16}$ partitions collapse to $n$ hook-length exponents. Removing Bits is a partisan game whose positions are surreal numbers that simply add — and Gold and Silver Coin Game is the same theory in disguise, blue-red Hackenbush on stalks, where "fair" means total value zero and the generating function $x^4 + x + x^{-1} + x^{-4}$ factors as $x^{-4}(1+x^3)(1+x^5)$, leaving a single binomial sum. Long Products counts $n$-tuples by product, which is the summatory function of the multiplicative $d_n$ — constant on primes, and so exactly what a Min_25 sieve sums in sublinear time. Eulercoin's record lows of $na \bmod m$ are the subtractive Euclidean algorithm run on two records, so the coins arrive in logarithmically many steps. Summation of Summations applies a linear operator, so the answer is a weighted sum of the inputs; the statement's 429 is a Catalan number, the tell that the weights are ballot numbers. Sometimes the object only shows its name after a change of variables. Exploding Sequence iterates the quadratic map $a \mapsto 6a^2 + 10a + 3$, whose terms double in length every step; completing the square with $b = 6a + 5$ turns it into $b \mapsto b^2 - 2$, the doubling rule of a Lucas sequence, so the $n$-th term is $V_{2^{n-1}}$. Modulo a prime $p$ that index only matters modulo the order of the underlying root, which divides $p - 1$ or $p + 1$, so $10^{15}$ iterations become two short exponentiations. The theory that comes with a name can include a bound. $47$-smooth Triangular Numbers looks like an open-ended search, since nothing in the statement says where smooth pairs $n, n+1$ stop; rewriting $n(n+1)$ as a Pell equation $x^2 - 2q\,y^2 = 1$, with $q$ ranging over the $2^{15}$ products of primes up to 47, brings in Størmer's theorem and Lehmer's refinement, which say only the first two dozen powers of each fundamental solution can qualify — the search is finite because a theorem says so, not because a loop happened to stop finding things. And the known object can lie outside arithmetic altogether. Solving $\mathcal{I}$-equations asks for the least common value of two nested polynomial expressions, but the operator is injective on pairs of non-negative integers, so two expressions are equal exactly when their trees match after substitution: the equation is first-order unification, solved with union-find and an occurs check, and monotonicity makes the least value the most general unifier with every free variable set to zero. No number is ever searched. A physical process can turn out to be a known object as well. Rolling Square rolls a small square around the inside of a larger one. Tracking only where its corners land near each corner of the large square reduces the whole motion to one map of the circle, $y \mapsto x - \sqrt{1 - y^2} \bmod 1$. That map is an orientation-preserving homeomorphism, so it has a rotation number. Each reduced fraction $p/q$ is realised by exactly one square, and its step count is a formula in $p$ and $q$. So a rolling simulation becomes a count of coprime pairs under a line, which Möbius inversion handles. A conflict relation between pieces is often an order or a graph. In Non-attacking Frogs two positions attack when their difference lies in the numerical semigroup $\langle a, b \rangle$. Written in the gap coordinates $g = ab - ia - jb$, "attacks" is exactly componentwise dominance of $(i, j)$, so a valid configuration is an antichain in a Young diagram, and $10^{15}$ subsets are counted by a DP over its cells. Connections II draws arcs above or below a line; two arcs on the same side collide exactly when their intervals cross, so a valid drawing is a proper 2-colouring of the overlap graph. A connected bipartite graph has just two colourings, one the mirror of the other, so the maximisation splits into independent components, each taking its larger colour class. Once the object has a name, its theory comes with it, and the code implements a theorem rather than a search.

Turn it into squares, then read the sign. A quadratic condition often becomes a statement about squares, and the sign between them decides which theory applies. Triangular numbers are the easiest case, since $8T_a + 1 = (2a+1)^2$. Expressing an Integer as the Sum of Triangular Numbers and Finding Triangles both open with that line, then part ways. Problem 621 fixes one of its three terms and lands on a sum, $(2b+1)^2 + (2c+1)^2 = 8m + 2$. The number of ways to write a number as a sum of two squares is a multiplicative function read off the prime factorisation, so the inner search is never run: it is counted, and more than $10^{13}$ pairs become a few million factorisations. In problem 955 the steps between triangles run $1, 2, 3, \dots$, so the next triangle is the least $j$ with $t(x) + t(j) = t(y)$. Here the squares land on opposite sides, and a difference factors: the equation becomes $x(x+1) = pq$ with $p = y - j$ and $q = y + j + 1$. The least $j$ is the factor pair nearest the trivial one, so the walk jumps from triangle to triangle at the cost of one divisor scan each, and the terms between are never generated. Problem 621 still has to factor every value of a quadratic, and that is cheaper than it sounds, because values of a polynomial factor better together than apart. A prime divides such a value only on at most two residue classes of the index, so one sieve over the primes replaces all the separate factorisations. A difference factors over the integers only when its coefficients are squares. Nearly Isosceles $120$ Degree Triangles asks for triangles with sides up to $10^{100}$, which no search reaches. The first step is to fix the parameter the statement keeps small, the difference $d = b - a \le 100$. Completing the square then gives $X^2 - 3Y^2 = d^2$. The coefficient 3 is not a square, so the difference does not factor over $\mathbb{Z}$, but it does factor in $\mathbb{Z}[\sqrt3]$. It is a generalised Pell equation, and because norms multiply, multiplying by the unit $2 + \sqrt3$ maps solutions to solutions. Every solution lies on the orbit of one of a few small seeds, and each orbit grows geometrically, so a bound of $10^{100}$ costs under two hundred steps per seed. The cost grows with the number of digits in the limit, not with the limit.

Keep only what the answer reads. Most inputs carry far more information than the question uses, and finding the part it uses shrinks the state. $250250$ needs each $k^k$ only modulo 250, so a quarter of a million elements collapse to a census of 250 residues. A Huge Binomial Coefficient never forms a number with nine billion digits: the squarefree modulus splits by the Chinese remainder theorem into prime fields, where Lucas' theorem answers digit by digit. Digital Root Clocks shows the per-prime saving depends only on the last two digits and the digit sum, so two small tables replace any simulation. Rounded Square Roots reads $n$ only through $\lceil n/x \rceil$, so whole intervals of $n$ share a path and are processed as one. Freshman's Product has more sequences than a number with a million digits, but its carry-free product reads each decimal place independently and each input only through its digit there — a ten-entry histogram per place, raised to the $R$-th power under multiplication modulo 10. Fibonacci Tree Game plays on a tree with a 2000-digit node count, but once the game is recognised as Green Hackenbush, a move matters only through the Grundy value it leaves at the root, and those values stay small. So the moves are counted per (level, target value), a few thousand values per level, and no node is ever visited. A huge parameter can be state the answer does not read, too. The Millionth Number with at Least One Million Prime Factors looks impossible because $k = 10^6$, but the early members of the list are overwhelmingly powers of two: each odd prime that replaces a two multiplies the value by at least $3/2$, so beyond about 36 prime factors every early member shares a common power of two. Dividing it out maps the head of the list for $k$ onto the head of the list for 36 in order, and $k$ is gone — the answer is an ordinary 64-bit enumeration times one modular power. Sometimes the state shrinks to a single bit. In Pairwise Coin-Tossing Game consecutive rounds share exactly one player, so the only thing that matters after a round is whether its winner plays the next one; the game is a two-state Markov chain, the ending round has a simple geometric law, and each player's chance is an arithmetico-geometric series summed in closed form. The question to ask is: what is this result actually a function of? The answer is the real state space.

Search the answer's structure, not the input range. When the inputs are too many to visit, walk the thing that generates the answers instead. Prime Factors of $n^{15}+1$ exchanges the order of summation — instead of factorising $10^{11}$ huge numbers, it asks each of the primes below $10^8$ how many $n$ it divides, which group theory answers in $O(1)$. Euler's Totient Function Equals 13! inverts $\varphi$ by enumerating factorisations of the target into $p^{a-1}(p-1)$ pieces — a few hundred candidate primes rather than tens of billions of candidate $n$. Modular Cubes, Part 2 and Perfection Quotients likewise build $n$ from the prime factors the condition demands, and Sums of Digit Factorials inverts a chain of digit functions through the factorial number system rather than iterating it. $5$-smooth Totients reads the totient's product formula backwards: $\varphi(n)$ is 5-smooth only when $n$ is a Hamming number times distinct primes $q$ with $q - 1$ Hamming, so $10^{12}$ candidates become a few thousand Hamming numbers and the square-free products of a few hundred primes. For a Diophantine equation the generator is a parametrisation. Asymmetric Diophantine Equation reads $16x^2 + y^4 = z^2$ as a Pythagorean triple with one leg a multiple of 4 and the other a square; Euclid's formula, plus the fact that coprime factors of a square are squares, yields two two-parameter families in which $z$ grows like a fourth power — so $z \le 10^{16}$ means about $3 \times 10^7$ coprime parameter pairs, each one a solution, and no search over $(x, y)$ or square test anywhere. Euclid's formula is one case of a general method: a conic with one rational point is parametrised by the lines through that point. Angular Bisector and Tangent 2 asks when a length $CE$ is an integer; a valuation argument reduces "$CE^2$ is a square" to $g^2 - w^2 = D m^2$, a conic through the obvious point $(1 : 1 : 0)$. Each reduced slope $\beta/\alpha$ gives one primitive solution, and the perimeter is linear in the remaining scale, so each shape contributes a single floor division's worth of triangles. Some $10^{10}$ candidate triangles become a few million parameter tuples. Construction beats filtering whenever the answers are sparse and the space is not.

Divide out the scale. When a condition survives multiplying every variable by a constant, the solutions lie on rays, and there is a standard way to find them: write the ratio in lowest terms and let coprimality push every denominator into the scale factor. What comes out is a complete family in which each solution appears exactly once. Tangent Circles reduces tangency to $1/\sqrt{r_C} = 1/\sqrt{r_A} + 1/\sqrt{r_B}$, which forces $r_A/r_B$ to be the square of a reduced fraction $u/v$; since $u + v$ is coprime to $uv$, $(u+v)^2$ must divide the scale, and the three radii become $t$ times fixed polynomials in $u$ and $v$. Prime Triples and Geometric Sequences does the same to a common ratio $q/p$, giving $(kp^2, kpq, kq^2)$. Panaitopol Primes takes out $g = \gcd(x, y)$ from $(x^4 - y^4)/(x^3 + y^3)$; after cancelling, the denominator is coprime to what is left of the numerator, so it too must divide $g$. The step is the same each time. What differs is what the problem does with the scale, and that decides the program. In problem 510 the radii scale freely, so a family's multiples sum as a triangular number, and looping over them would bring back the linear cost the parametrisation removed. In problem 518 the members must be one below a prime, which breaks the scaling, so $k$ stays a live variable and the program filters it, testing $kq^2 - 1$ first because every $p$ shares that result. In problem 291 the scale disappears altogether. The value has become a product of three positive integers, $k(a-b)(a^2+b^2)$, and it must be prime, so $k = 1$ and $a - b = 1$. A primality condition is weak until a factorisation appears, and then it is an equation: two variables with no stated bound collapse to one, and the answers are the primes among $n^2 + (n+1)^2$.

Bound the answer, then decide the boundary. When the quantity asked for is small, prove how small it is before computing it. Distinct Rows and Columns asks for the least complexity (the number of distinct strings among the rows and columns) of an $n \times n$ binary matrix with $k$ ones, summed over all $k \le n^2$. That looks like an optimisation over $2^{n^2}$ matrices for each $k$. Two explicit constructions, a square plus one partial row and a near-square rectangle plus one partial row, reach every $k$ with complexity 4. Complexities 1 and 2 fall to a short case analysis. That leaves one yes/no question per $k$: is complexity 3 possible? With at most three row types and three column types, a matrix is a block matrix with finitely many patterns, and each pattern makes $k$ a quadratic form in the block sizes. The answer becomes the union of a few two-parameter quadratic families, marked in a flag array, and complementing the matrix ($k \mapsto n^2 - k$) halves the casework. Construction gives the upper bound and a finite classification settles the rest.

Trade the condition for a sum that collapses. A congruence condition, "the total is $0 \bmod n$", is awkward to count directly but easy to filter: the average of $\omega^{js}$ over the $n$-th roots of unity is $1$ when $n \mid s$ and $0$ otherwise. The roots-of-unity filter turns the count into $n$ sums with no condition at all, and the reduction pays when those sums turn out to be nearly all alike. In Subset Sums the modulus is prime, so every non-trivial root is primitive and the $p-1$ non-trivial terms are identical, each worth $q$; the count becomes $\bigl(\binom{qp}{p} + q(p-1)\bigr)/p$, a single binomial coefficient per prime. Quadruple Congruence filters the zeros of an eight-variable quadratic form the same way; each term becomes a power of a quadratic Gauss sum, whose modulus is classical even though its value is not, and $n^8$ tuples collapse into a Dirichlet convolution summed with a totient sieve. For a small modulus the filter needs no complex numbers at all. $B$-Trivisible Numbers counts the $n$ whose prime factors up to a bound sum to $0 \bmod 3$, and it carries all three remainders at once in the group ring $\mathbb{Z}[C_3]$: a formal $x$ with $x^3 = 1$, whose elements are just triples of integers. The condition becomes the multiplicative function $x^{S(n)}$, which a Dirichlet convolution turns into a sum over square-free divisors. One more reduction finishes it. The small primes' share of that function is periodic in $n$, so a prefix table answers it in $O(1)$, and only the large primes go through the divisor sum, which cuts it from about $7 \times 10^7$ terms to $1.4 \times 10^6$. The transform costs a sum over $n$ roots and buys a structure that counting never exposes.

How to reason about it

Reach for a reduction whenever the quantities you are about to iterate over are related by a rule rather than being arbitrary data — a linear constraint, an ordering, a recurrence, a symmetry, a counting structure. The tell is that you can write down an equation the answer must satisfy. Spend the algebra there: each equation you solve is a loop you delete, a dimension you drop, or a bound you tighten. A second tell is a search space that dwarfs the answer — $2^{669}$ subsets when only the totals matter, as in Prime Subset Sums, or $40!$ fill orders when the state that matters is a step count, a segment count and two boundary flags, as in Tidying Up A. That gap means the problem has a smaller state hiding in it, and finding that state is the reduction.

Three cautions keep the habit honest:

Know when to stop. Not every problem closes into a formula, and forcing one produces fragile, wrong code. Counting Rectangles reduces the count to $T(H)\cdot T(W)$ but still searches grid shapes for the one nearest a target, because that outer question has no closed form — the honest reduction is partial, and that is fine. A reduction that removes one loop of three is already a win. Most of the later reductions end the same way — in a smaller computation, not a formula: a generating-function DP over board positions in Overtakes, a four-wide table over depth in Pythagorean Tree.
Derive, then verify. An algebraic reduction is only as good as its derivation, and an off-by-one in a bound or a dropped term fails silently. Keep the brute-force version as an oracle and check the two against each other on small inputs — Number Spiral Diagonals ships exactly that, running an $O(N^2)$ spiral simulation under --show purely to confirm its formula. The check matters most when the reduction is a guess. Chandelier is the warning: "every balanced set is a union of regular polygons" is a theorem when $n$ has at most two prime factors and false for 360, which has three — already in $\mathbb{Z}_{30}$ there are 525 balanced 6-subsets against 495 polygon unions. Overtakes shows the honest version: its characterisation was conjectured, then checked against a breadth-first brute force for every $n \le 7$ before any fast code was trusted. Summation of Summations found its ballot-number weights by simulating unit vectors, and Gold and Silver Coin Game checked its surreal values by playing every arrangement out for $n \le 7$. A reduction often predicts something checkable on its own: problem 615's says that past the threshold, raising $k$ by one exactly doubles the unreduced answer, and a brute force confirms it does. Beyond brute-force range, a reduction can still be tested at full size. Problem 621 has a second route it never computes through: Gauss's theorem ties its count to a class number, and the class number formula predicts the sieve's result to about two parts per million. Problem 967 has a free parameter, the point where small primes end and large ones begin, and moving it rearranges the whole calculation without changing the answer. And small edge cases hide in correct derivations too: in Euler's Totient Function Equals 13! the factor contributed by the prime 2 at exponent 1 is $1$, so a search that stops when the residual target reaches 1 silently drops half the solutions.
Mind the arithmetic you introduce. Reductions multiply before they divide and can form intermediates far larger than the answer — an overflow risk in C, and a reason to keep the algebra in exact integers (compute $c = S - a - b$, not $\sqrt{a^2+b^2}$) so equality checks stay reliable. See exact-arithmetic-for-equality. An alternating inclusion–exclusion sum, as in Twenty-two Foolish Primes, cancels catastrophically, so it stays in exact integers until the final division. Reducing modulo the requested digits is safe only when the reduced formula uses addition and multiplication alone — true of the subset-sum table in Prime Subset Sums, and something to check rather than assume once a division appears. Pairwise Coin-Tossing Game shows the fix when it does: its closed form must be reduced to lowest terms, the common factor $g$ need not be invertible modulo $10^8$, so the product is computed modulo $10^8 g^2$ and divided exactly by $g^2$ — and $g$ itself comes from $\gcd(n, 2^n \bmod n - 1)$, never from the thirty-million-digit $2^n - 1$.

The discipline underneath all of it is order of operations, in the human sense: do the mathematics first. A loop written before the algebra is a loop you will optimise later; a loop written after it is often a loop you never write at all.

Problems208 / 208

● 0002 — Even Fibonacci Numbers
● 0009 — Special Pythagorean Triplet
● 0027 — Quadratic Primes
● 0028 — Number Spiral Diagonals
● 0029 — Distinct Powers
● 0030 — Digit Fifth Powers
● 0032 — Pandigital Products
● 0034 — Digit Factorials
● 0038 — Pandigital Multiples
● 0039 — Integer Right Triangles
● 0041 — Pandigital Prime
● 0045 — Triangular, Pentagonal, and Hexagonal
● 0051 — Prime Digit Replacements
● 0052 — Permuted Multiples
● 0058 — Spiral Primes
● 0068 — Magic 5-gon Ring
● 0069 — Totient Maximum
● 0070 — Totient Permutation
● 0071 — Ordered Fractions
● 0079 — Passcode Derivation
● 0080 — Square Root Digital Expansion
● 0082 — Path Sum: Three Ways
● 0085 — Counting Rectangles
● 0086 — Cuboid Route
● 0088 — Product-sum Numbers
● 0089 — Roman Numerals
● 0091 — Right Triangles with Integer Coordinates
● 0100 — Arranged Probability
● 0101 — Optimum Polynomial
● 0104 — Pandigital Fibonacci Ends
● 0106 — Special Subset Sums: Meta-testing
● 0108 — Diophantine Reciprocals I
● 0109 — Darts
● 0110 — Diophantine Reciprocals II
● 0111 — Primes with Runs
● 0113 — Non-bouncy Numbers
● 0120 — Square Remainders
● 0123 — Prime Square Remainders
● 0127 — abc-hits
● 0128 — Hexagonal Tile Differences
● 0131 — Prime Cube Partnership
● 0132 — Large Repunit Factors
● 0133 — Repunit Nonfactors
● 0134 — Prime Pair Connection
● 0135 — Same Differences
● 0136 — Singleton Difference
● 0137 — Fibonacci Golden Nuggets
● 0138 — Special Isosceles Triangles
● 0139 — Pythagorean Tiles
● 0140 — Modified Fibonacci Golden Nuggets
● 0141 — Square Progressive Numbers
● 0142 — Perfect Square Collection
● 0144 — Laser Beam Reflections
● 0145 — Reversible Numbers
● 0147 — Rectangles in Cross-hatched Grids
● 0152 — Sums of Square Reciprocals
● 0153 — Investigating Gaussian Integers
● 0154 — Exploring Pascal's Pyramid
● 0157 — Base-10 Diophantine Reciprocal
● 0158 — Lexicographical Neighbours
● 0160 — Factorial Trailing Digits
● 0162 — Hexadecimal Numbers
● 0163 — Cross-hatched Triangles
● 0169 — Sums of Powers of Two
● 0170 — Pandigital Concatenating Products
● 0173 — Hollow Square Laminae I
● 0175 — Fractions and Sum of Powers of Two
● 0176 — Common Cathetus Right-angled Triangles
● 0180 — Golden Triplets
● 0182 — RSA Encryption
● 0188 — Hyperexponentiation
● 0190 — Maximising a Weighted Product
● 0195 — $60$-degree Triangle Inscribed Circles
● 0196 — Prime Triplets
● 0201 — Subsets with a Unique Sum
● 0202 — Laserbeam
● 0203 — Squarefree Binomial Coefficients
● 0206 — Concealed Square
● 0207 — Integer Partition Equations
● 0209 — Circular Logic
● 0210 — Obtuse Angled Triangles
● 0216 — The Primality of $2n^2 - 1$
● 0217 — Balanced Numbers
● 0221 — Alexandrian Integers
● 0222 — Sphere Packing
● 0225 — Tribonacci Non-divisors
● 0226 — A Scoop of Blancmange
● 0227 — The Chase
● 0228 — Minkowski Sums
● 0230 — Fibonacci Words
● 0232 — The Race
● 0233 — Lattice Points on a Circle
● 0234 — Semidivisible Numbers
● 0235 — An Arithmetic Geometric Sequence
● 0236 — Luxury Hampers
● 0237 — Tours on a $4 \times N$ Playing Board
● 0238 — Infinite String Tour
● 0239 — Twenty-two Foolish Primes
● 0240 — Top Dice
● 0241 — Perfection Quotients
● 0242 — Odd Triplets
● 0243 — Resilience
● 0245 — Coresilience
● 0246 — Tangents to an Ellipse
● 0247 — Squares Under a Hyperbola
● 0248 — Euler's Totient Function Equals 13!
● 0249 — Prime Subset Sums
● 0250 — $250250$
● 0251 — Cardano Triplets
● 0253 — Tidying Up A
● 0254 — Sums of Digit Factorials
● 0255 — Rounded Square Roots
● 0257 — Angular Bisectors
● 0269 — Polynomials with at Least One Integer Root
● 0272 — Modular Cubes, Part 2
● 0277 — A Modified Collatz Sequence
● 0288 — An Enormous Factorial
● 0291 — Panaitopol Primes
● 0293 — Pseudo-Fortunate Numbers
● 0297 — Zeckendorf Representation
● 0301 — Nim
● 0309 — Integer Ladders
● 0313 — Sliding Game
● 0315 — Digital Root Clocks
● 0319 — Bounded Sequences
● 0321 — Swapping Counters
● 0331 — Cross Flips
● 0346 — Strong Repunits
● 0357 — Prime Generating Integers
● 0365 — A Huge Binomial Coefficient
● 0381 — $(\text{prime}-k)$ Factorial
● 0395 — Pythagorean Tree
● 0400 — Fibonacci Tree Game
● 0407 — Idempotents
● 0420 — $2 \times 2$ Positive Integer Matrix
● 0421 — Prime Factors of $n^{15}+1$
● 0443 — GCD Sequence
● 0452 — Long Products
● 0457 — A Polynomial Modulo the Square of a Prime
● 0464 — Möbius Function and Intervals
● 0478 — Mixtures
● 0484 — Arithmetic Derivative
● 0487 — Sums of Power Sums
● 0492 — Exploding Sequence
● 0493 — Under the Rainbow
● 0504 — Square on the Inside
● 0510 — Tangent Circles
● 0512 — Sums of Totients of Powers
● 0516 — $5$-smooth Totients
● 0518 — Prime Triples and Geometric Sequences
● 0545 — Faulhaber's Formulas
● 0581 — $47$-smooth Triangular Numbers
● 0582 — Nearly Isosceles $120$ Degree Triangles
● 0605 — Pairwise Coin-Tossing Game
● 0615 — The Millionth Number with at Least One Million Prime Factors
● 0621 — Expressing an Integer as the Sum of Triangular Numbers
● 0635 — Subset Sums
● 0641 — A Long Row of Dice
● 0650 — Divisors of Binomial Product
● 0659 — Largest Prime
● 0674 — Solving $\mathcal{I}$-equations
● 0694 — Cube-full Divisors
● 0700 — Eulercoin
● 0720 — Unpredictable Permutations
● 0725 — Digit Sum Numbers
● 0726 — Falling Bottles
● 0739 — Summation of Summations
● 0743 — Window into a Matrix
● 0755 — Not Zeckendorf
● 0757 — Stealthy Numbers
● 0764 — Asymmetric Diophantine Equation
● 0767 — Window into a Matrix II
● 0768 — Chandelier
● 0772 — Balanceable $k$-bounded Partitions
● 0778 — Freshman's Product
● 0779 — Prime Factor and Exponent
● 0782 — Distinct Rows and Columns
● 0820 — $N$thDigit of Reciprocals
● 0834 — Add and Divide
● 0843 — Periodic Circles
● 0853 — Pisano Periods 1
● 0860 — Gold and Silver Coin Game
● 0862 — Larger Digit Permutation
● 0872 — Recursive Tree
● 0875 — Quadruple Congruence
● 0882 — Removing Bits
● 0883 — Remarkable Triangles
● 0885 — Sorted Digits
● 0918 — Recursive Sequence Summation
● 0926 — Total Roundness
● 0932 — $2025$
● 0934 — Unlucky Primes
● 0935 — Rolling Square
● 0938 — Exhausting a Colour
● 0940 — Two-Dimensional Recurrence
● 0951 — A Game of Chance
● 0955 — Finding Triangles
● 0962 — Angular Bisector and Tangent 2
● 0967 — $B$-Trivisible Numbers
● 0971 — Modular Polynomial Composition
● 0980 — The Quaternion Group I
● 0988 — Non-attacking Frogs
● 0995 — A Particular Pair of Polynomials
● 0996 — Overtakes
● 1000 — Problem $1000$
● 1002 — Connections II
● 1006 — Fibonacci Subwords
● 1010 — March of the Penguins