Calculate a Triangle Number
The sum of the first n integers, the shape that gives it its name, and the one-line formula that replaces an entire loop.
- What a triangle number is, visually and numerically
- The loop-based approach
- Gauss’s shortcut: a closed-form formula
- Code in Python, JavaScript, and Pascal
- Checking whether a number is triangular
- Overflow and precision in the closed form
- Where triangle numbers turn up in practice
What a triangle number is, visually and numerically
A triangle number is the sum of every positive integer from 1 up to some value n. The first few are 1, 3, 6, 10, 15, 21 — each one built by adding the next counting number onto the last. The name comes from a simple visual fact: if you arrange that many dots into rows, with one dot in the first row, two in the second, three in the third, and so on, the dots form a perfect equilateral triangle.
Ten dots, four rows — the fourth triangle number is 10.
Formally, the n-th triangle number, usually written T(n), is defined as 1 + 2 + 3 + ... + n. It’s one of the first sequences most people encounter that has both a simple recursive definition — T(n) = T(n-1) + n — and a simple closed-form formula, which makes it an unusually good teaching example for the idea that a loop and a formula can compute the exact same thing at very different costs.
The loop-based approach
The most direct translation of the definition into code is a simple accumulating loop: start a running total at zero, and add each integer from 1 to n onto it in turn.
def triangle_number(n): if n < 0: raise ValueError("triangle number undefined for negative n") total = 0 for i in range(1, n + 1): total += i return total
This runs in time proportional to n — perfectly fine for small inputs, and arguably the clearest possible expression of what a triangle number actually means. The trouble starts only when n gets large or when the function is called repeatedly inside a tighter loop, at which point recomputing the same sum from scratch every time becomes wasteful for a problem that, as it turns out, doesn’t need a loop at all.
Gauss’s shortcut: a closed-form formula
There’s a well-known story about a young Carl Friedrich Gauss being asked by a schoolteacher to add up the numbers from 1 to 100 — and producing the answer almost immediately by noticing a pairing trick. Pair the first number with the last, the second with the second-to-last, and so on: 1 + 100, 2 + 99, 3 + 98 — each pair sums to 101, and there are exactly 50 such pairs, giving 50 × 101 = 5050 without adding a single number individually.
That pairing trick generalizes into a closed-form formula for any n: T(n) = n(n + 1) / 2. The formula computes the exact same value as the loop above, but does it in constant time — no matter whether n is 10 or 10 billion, the formula performs exactly one multiplication, one addition, and one division.
// O(1) — same answer as the loop, no iteration required function triangleNumber(n) { if (n < 0) { throw new Error("triangle number undefined for negative n"); } return (n * (n + 1)) / 2; }
The formula works because n and n + 1 are always one apart, which means exactly one of them is even — so the product n × (n + 1) is always evenly divisible by 2, and the division never introduces a fractional remainder.
A third version: Pascal, for contrast
Older procedural languages express the same formula with very little ceremony, which is part of why this problem has stayed a popular teaching example across decades of changing language fashions.
function TriangleNumber(n: Integer): Integer; begin if n < 0 then raise Exception.Create('triangle number undefined for negative n'); TriangleNumber := (n * (n + 1)) div 2; end;
Note the explicit div rather than a plain slash — Pascal distinguishes integer division from real-number division at the syntax level. When you know a division is guaranteed to be exact, as it is here, writing it in a way that makes that guarantee visible helps the next reader trust the result without re-deriving the math.
Checking whether a number is triangular
A related problem is the reverse question: given some number, is it a triangle number at all? Rearranging the closed-form formula as a quadratic equation and solving it gives a direct test — a number x is triangular exactly when 8x + 1 is a perfect square. Compute the integer square root of 8x + 1, square it again, and check whether the result matches exactly.
import math def is_triangular(x): if x < 0: return False candidate = 8 * x + 1 root = math.isqrt(candidate) return root * root == candidate
This is a good example of how closed-form math, once derived, often makes a problem that looks like it needs a search — “try every triangle number until one matches” — collapse into a single check with no loop at all.
Overflow and precision in the closed form
- Multiply before you divide. Computing
n * (n + 1) / 2in that order, with integer division applied last, avoids the fractional truncation that can happen if division is performed first in a language with integer-only division. - Watch the multiplication for overflow.
n * (n + 1)can exceed a 32-bit integer range well beforenitself looks dangerously large — fornaround 65,536, the product is already past two billion. - Negative input. The triangle number sequence is only defined for non-negative integers; validate before computing rather than after.
- Floating-point versions. If a triangle number is computed using floating-point division anywhere in the formula, double-check rounding near large values — the guarantee that the division is always exact only holds for true integer arithmetic.
Where triangle numbers turn up in practice
Beyond the classic dot-arrangement and bowling-pin examples, triangle numbers appear constantly in algorithm analysis. Counting the number of comparisons made by a naive nested loop that compares every pair of elements in a list of size n — the kind of loop found at the heart of bubble sort and several other simple algorithms — produces exactly the (n-1)-th triangle number of comparisons. That’s the reason simple pairwise-comparison algorithms are described as running in quadratic time: a triangle number is itself roughly proportional to n².
Triangle numbers also appear in combinatorics as a special case of the binomial coefficient — T(n) is exactly “n+1 choose 2,” the number of ways to pick two items out of n+1. In game design, triangle numbers govern the total number of connections in a fully-connected network of n nodes, or the total tiles needed to build a triangular game board of a given size.