The largest piece that still fits

The scribes of the Rhind papyrus, about 1550 BCE, wrote every fraction as a sum of distinct unit fractions — $\tfrac25 = \tfrac13 + \tfrac1{15}$ — and the habit survived for three thousand years. Leonardo of Pisa gave a general method in 1202, and it is the simplest one imaginable: take the largest unit fraction that is still smaller than what remains, subtract, and repeat. James Joseph Sylvester proved in 1880 that the method always finishes, and studied what it does to the simplest target of all, the number 1.

Applied to 1, with the convention that the pieces must stay strictly below what is left, the rule picks $\tfrac12$, then the largest unit fraction below $\tfrac12$, which is $\tfrac13$, then the largest below $\tfrac16$, which is $\tfrac17$, then below $\tfrac1{42}$, which is $\tfrac1{43}$. The denominators continue 1807, 3263443, 10650056950807, and they are Sylvester’s sequence.

The fractions of the Stern–Brocot tree gave one way to write fractions as sums of unit fractions, by walking down the tree, and the Erdős–Straus question about $4/n$ showed how hard the most innocent questions about such sums become. This essay is about the greedy rule: why it produces this sequence for 1, why for 1 it happens to be the best possible use of each number of pieces, and why for most other fractions it is anything but.

One more than the product #

The sequence has a description that does not mention fractions at all. Start with $s_1 = 2$ and let each term be one more than the product of all the earlier ones:

$$s_{n+1} = s_1 s_2 \cdots s_n + 1.$$

So $s_2 = 2 + 1 = 3$, $s_3 = 2 \cdot 3 + 1 = 7$, $s_4 = 2 \cdot 3 \cdot 7 + 1 = 43$, $s_5 = 2 \cdot 3 \cdot 7 \cdot 43 + 1 = 1807$. Since the product up to $s_n$ is $s_n - 1$ times $s_n$, the recurrence can also be written $s_{n+1} = s_n^2 - s_n + 1$, which makes the growth plain: each term is roughly the square of the last.

The connection with the greedy rule is a telescoping identity. From $s_{n+1} - 1 = s_n(s_n - 1)$,

$$\frac{1}{s_n} = \frac{1}{s_n - 1} - \frac{1}{s_{n+1} - 1},$$

and adding these from $n = 1$ to $k$, with $s_1 - 1 = 1$, gives

$$\frac1{s_1} + \frac1{s_2} + \cdots + \frac1{s_k} = 1 - \frac{1}{s_{k+1} - 1}.$$

So after $k$ terms, what is left of 1 is itself a unit fraction, $1/(s_{k+1} - 1)$. The largest unit fraction strictly smaller than $1/m$ is $1/(m + 1)$, so the greedy rule’s next choice is $1/s_{k+1}$, and the sequence reproduces itself. The figure’s table shows ten terms; the tenth has 105 digits, and the sum of the reciprocals of the first ten falls short of 1 by a number with more than two hundred zeros after the decimal point.

Nothing comes closer #

The greedy rule is short-sighted by design: each step takes the biggest bite available, without regard for what that leaves to the steps that follow. For most problems that is a bad strategy, and a natural question is whether some other choice of $k$ unit fractions could get closer to 1 without reaching it. For two pieces, $\tfrac12 + \tfrac13 = \tfrac56$ is clearly best. For three, is there anything beating $\tfrac{41}{42}$?

D. R. Curtiss proved in 1922 that there is not: for every $k$, the sum of $k$ unit fractions that is less than 1 and as large as possible is the greedy one, $1 - 1/(s_{k+1} - 1)$. The figure checks this by exhaustive search for $k$ up to 6. Choosing the denominators in increasing order, the search abandons a branch as soon as the remaining pieces, each at most the size of the next one tried, could not bring the total above the best found so far. Everything is done in exact rational arithmetic, since the gaps involved quickly fall below what floating point can see. For six terms the search visits about 29,000 partial sums and confirms that the shortfall can be no smaller than $1/10650056950806$, the greedy one. The same search was also run separately for seven terms, where it visits seventy million partial sums in about twenty seconds and again finds only the greedy answer.

The reason the greedy rule wins here is the telescoping. Each greedy step leaves a remainder that is a unit fraction, and a unit fraction $1/m$ cannot be approached any more closely from below by one piece than by $1/(m + 1)$. A cleverer first step leaves a remainder that is not a unit fraction, and Curtiss’s proof shows that the inefficiency that creates always costs more than the first step gained. That is not true for most targets.

The theorem is a statement about approximation, and it is worth setting beside the more familiar one. How close a fraction can get to an irrational number with a denominator of a given size is governed by continued fractions, and the best approximations there are found by a rule that is also, in its way, greedy: take the whole part, invert what is left, repeat. Here the target is rational, the pieces are restricted to unit fractions, and the quantity being economised is the number of pieces rather than the size of a denominator. The answer is still a greedy rule, and the error still shrinks at a definite rate — not like the square of the denominator, as for continued fractions, but like the square of the previous error, which is why eight pieces already come within $10^{-51}$ of 1.

The greedy rule on other fractions #

For a general fraction $a/b$ the greedy rule still finishes. If $1/x$ is the largest unit fraction below $a/b$, then $1/(x - 1) \ge a/b$, which says $ax - b < a$: the numerator of the remainder $(ax - b)/(bx)$ is smaller than $a$. Numerators cannot fall for ever, so the expansion ends, with at most $a$ terms. That was Fibonacci’s observation and Sylvester’s proof.

The bound on the number of terms says nothing about their size, and the sizes can be enormous. Running the rule on all 4,375 fractions $a/b$ in lowest terms with $1 < a < b \le 121$, most need three or four terms and finish with denominators of a few digits; 711 need only two. But 153 need six terms, 18 need seven, and three need eight, and the denominators at the end of those can be huge. The classic example is $5/121$, which the greedy rule expands as

$$\frac{5}{121} = \frac1{25} + \frac1{757} + \frac1{763309} + \frac1{873960180913} + \frac{1}{1527612795642093418846225},$$

while $\tfrac1{33} + \tfrac1{121} + \tfrac1{363}$ does the same job in three terms. The worst in the range is $8/97$, whose eighth and last denominator has 150 digits.

The mechanism is visible in the 5/121 expansion: its denominators after the first are roughly the squares of one another, the same growth as Sylvester’s sequence. Each greedy step leaves a remainder just above a unit fraction, so the next step takes a piece just under it and leaves a much smaller, awkward remainder; and once the remainder’s numerator is 1 or 2 the process becomes Sylvester’s recurrence in disguise. The greedy rule is perfect for 1 precisely because 1 starts the doubly exponential cascade cleanly, and for 5/121 it is terrible because it falls into the cascade late, with a large denominator already in hand.

When the greedy choice is the right one #

Short-sighted rules that turn out to be optimal are rare enough to be worth collecting, and Curtiss’s theorem belongs with a small family of them. The cashier’s rule for making change — pay with the largest coin that fits, then repeat — gives the fewest coins for British and United States coins and fails for others, as the essay on two pounds in 73,682 ways found: with coins of 1, 3 and 4 it pays 6 as $4 + 1 + 1$ instead of $3 + 3$. For coins the question of when greedy is optimal has a complete and checkable answer, and it depends on the coins. For unit fractions with target 1 the answer is always yes, and for almost every other target it is no.

The cleanest general theory of when greedy works is the theory of matroids: if the feasible choices have the exchange property — any smaller feasible set can be enlarged by some element of any larger one — then taking the best available element at every step is optimal. That is why the greedy algorithm finds the cheapest spanning tree of a network, one edge at a time. Unit fractions summing below 1 have no such structure, which is why Curtiss’s theorem needs its own proof and why it fails for other targets. The success at 1 comes from arithmetic — the telescoping — and not from any structural reason that would extend.

There is also a distinction between being best in total and being best at every stage. The greedy expansion of 1 is the best $k$-term approximation for every $k$ simultaneously: one sequence of choices is optimal at every length. That is stronger than Curtiss’s statement for a single $k$, and it is what makes the sequence canonical. For a target such as $\tfrac{5}{121}$ the best three-term expansion, $\tfrac1{33} + \tfrac1{121} + \tfrac1{363}$, does not begin with the best one-term approximation from below, $\tfrac1{25}$; the optimal expansions at different lengths do not nest, and no single rule produces them.

A constant for the whole sequence #

Since each term is about the square of the last, $s_n$ is about a fixed number raised to the power $2^n$, and that number can be extracted by taking $2^n$-th roots. The roots fall from $\sqrt2 \approx 1.414$ for the first term and settle quickly.

The limit is $E = 1.264084735\ldots$, and the terms are exactly $\lfloor E^{2^n} + \tfrac12 \rfloor$, the eleventh term already fixing $E$ to nine places. Ilan Vardi drew attention to this formula, and the constant is named after him. It looks like a closed form for the sequence and is not one, because the only known way to compute $E$ is from the sequence itself. Similar constants describe every recurrence of the form $x_{n+1} = x_n^2 + c$, including the iteration that draws the Mandelbrot set, whose points are the values of $c$ for which the iteration from 0 stays bounded; Sylvester’s sequence is the case $c = \tfrac34$ after the substitution $x_n = s_n - \tfrac12$, since $s_{n+1} - \tfrac12 = (s_n - \tfrac12)^2 + \tfrac34$.

A proof that the primes never end #

The surprising connection is with Euclid. Any two terms of Sylvester’s sequence share no prime factor, because each term is one more than a multiple of every earlier term: a prime dividing both $s_i$ and $s_j$ with $i < j$ would divide $s_j - s_1 s_2 \cdots s_{j-1} = 1$. So each term contributes at least one prime that no earlier term had, and since the terms never end, neither do the primes.

That is Euclid’s argument, run as a fixed machine rather than applied to an arbitrary list of known primes — exactly the machine that the essay on Euclid’s proof followed through the Euclid–Mullin sequence, where 1807 also appears and stops being prime. Sylvester’s sequence makes the argument completely explicit: the $n$-th term has a prime factor that is at least the $n$-th prime, since all $n$ terms up to it have distinct prime factors. But the terms are not primes themselves, and whether infinitely many of them are prime is unknown, like almost every question of that kind about a rapidly growing sequence.

The pairwise coprimality has a second use. Because the reciprocals of Sylvester’s numbers add up to 1 less something tiny, they solve, for every $k$, the equation $\tfrac1{x_1} + \cdots + \tfrac1{x_k} + \tfrac1{x_1 x_2 \cdots x_k} = 1$, and solutions of equations of that kind are what Znám’s problem is built from — a question about sets of whole numbers each of which divides the product of the others plus one, cousins of the divisor-sum conditions that define perfect numbers. The sequence is, in a precise sense, the most efficient way to use distinct unit fractions to almost fill a whole, and that efficiency makes it extremal in a family of problems that look unrelated: the closest approach to 1 by $k$ unit fractions, the largest solutions of these unit-fraction equations, and bounds on how large the smallest solution of some Diophantine systems can be.

Where the harmonic series fits #

The opposite extreme from the greedy rule is the harmonic series, which takes every unit fraction in turn: $1 + \tfrac12 + \tfrac13 + \cdots$ exceeds every number eventually, and steps over every whole number without landing on one. Sylvester’s sequence takes as few unit fractions as possible, each as large as allowed, and never reaches even 1. The harmonic series spends unit fractions slowly and gets everywhere; the greedy rule spends them as fast as it can and gets almost nowhere, approaching 1 with a gap that squares at every step.

Between the two lies the classical problem of Egyptian fractions proper, which asks for short expansions with small denominators. That problem is hard. The Erdős–Straus conjecture, that every $4/n$ needs only three unit fractions, has been checked very far and not proved, and a question as simple as the fewest unit fractions needed for $a/b$ with given $a$ and $b$ can usually be answered only by search. The greedy rule is a guarantee of termination and nothing more, except at 1.

Six terms of a theorem about all of them #

The search for the closest $k$-term sums stops at six in the figure and seven in a separate run; Curtiss’s theorem for all $k$ is quoted, not checked. The census of greedy expansions covers fractions with denominators up to 121, and the record of 150 digits is the record in that range only; denominators grow without bound as the fractions vary, and no figure can show how. The hero’s bar is to scale, and that is exactly why the pieces after 1/43 are invisible on it: the logarithmic plot below it is the only way to see them.

Vardi’s constant is computed from the first eleven terms. That it determines every term by rounding is a theorem about the recurrence; that the eleventh term fixes it to nine places is a computation, and the figure shows the convergence rather than proving its rate.

Searched to seven, Curtiss quoted for the rest #

Computed here: the first twelve terms in exact integers, with the product identity and pairwise coprimality checked for the first ten and eight; the greedy expansion of 1 to six terms; the exact search for the closest sums of one to six unit fractions below 1, and in a separate run seven; the greedy expansions of all 4,375 fractions with denominators to 121, with the worst cases; the $2^n$-th roots for eleven terms; and the smallest prime factors of the first seven terms.

Quoted: the history from the Rhind papyrus through Fibonacci and Sylvester; Curtiss’s theorem; Vardi’s formula; the connection with Znám’s problem; and the status of the questions about primes and square factors in the sequence.

Still open: primes and squares in Sylvester’s sequence #

Are infinitely many terms of Sylvester’s sequence prime? The first four are, and the sixth, but beyond that the terms are too large to test far, and heuristics based on how often numbers of that size are prime suggest only finitely many primes, but nobody can prove either answer. Is every term squarefree? No term is known to be divisible by the square of a prime, and it is conjectured that none is; a proof would need control over the primes dividing $s_n^2 - s_n + 1$ that nothing in number theory currently supplies.

A question closer to the greedy rule itself is how large its denominators can be for a fraction with denominator $b$. The bound from the shrinking numerators gives at most $a$ terms, and the squaring gives denominators of size roughly $b^{2^a}$, but how close real expansions come to that, and how it grows with $b$, is known only in the form of examples like 8/97 and explicit families.

Greedy, and for once right #

Taking the largest unit fraction that fits, starting from 1, gives Sylvester’s sequence 2, 3, 7, 43, 1807, …, each term one more than the product of all before it, and the shortfall after $k$ terms is exactly $1/(s_{k+1} - 1)$. No $k$ unit fractions get closer to 1 from below — Curtiss’s theorem, confirmed here by exact search to seven terms — while for other fractions the same rule can be ruinous, ending 8/97 with a 150-digit denominator.

The difference is a telescoping identity that leaves every remainder a unit fraction when the target is 1 and not otherwise. The same numbers, pairwise coprime, rerun Euclid’s proof that the primes never end, and their growth is governed by a single constant that the sequence is the only way to compute.