Fact-checked by Grok 2 weeks ago

Greedy algorithm for Egyptian fractions

The greedy algorithm for Egyptian fractions is a method to express any positive rational number as a finite sum of distinct unit fractions, where a unit fraction has a numerator of 1. It works by starting with the given fraction \frac{p}{q} (with p < q) and repeatedly selecting the largest unit fraction \frac{1}{n} such that \frac{1}{n} \leq \frac{p}{q}, where n = \lceil \frac{q}{p} \rceil, then subtracting this unit fraction from the remainder and continuing the process until the remainder is zero.^[1]^[2]^[3] This approach was formalized by the Italian mathematician Leonardo of Pisa, known as Fibonacci, in his 1202 treatise Liber Abaci, building on ancient Egyptian practices of fraction representation documented as early as the Rhind Mathematical Papyrus around 1650 BCE.^[2] Egyptian fractions themselves, sums of distinct unit fractions like \frac{2}{3} = \frac{1}{2} + \frac{1}{6}, were used in ancient Egypt for practical divisions such as allocating resources, though the systematic greedy method is a medieval innovation.^[1]^[2] The algorithm guarantees termination because each step reduces the numerator of the remainder, eventually reaching zero, and ensures distinct denominators since they strictly increase.^[3] However, it does not always yield the shortest possible expansion; for example, the greedy representation of \frac{4}{17} requires four terms (\frac{1}{5} + \frac{1}{29} + \frac{1}{1233} + \frac{1}{3\,039\,345}), whereas a three-term version exists (\frac{1}{5} + \frac{1}{30} + \frac{1}{510}).^[2] Despite potential for exponentially large denominators in some cases, such as the 10-term expansion of \frac{31}{311} with a final denominator over 500 digits, the greedy method remains a simple and efficient starting point for generating Egyptian fraction representations in computational number theory.^[3]

Background

Egyptian fractions

Egyptian fractions originated in ancient Egyptian mathematics, as evidenced by the Rhind Mathematical Papyrus, a document dating to approximately 1650 BCE that was copied by the scribe Ahmes from an earlier text. This papyrus includes practical arithmetic problems, such as dividing loaves of bread among groups of workers, where rational quantities are expressed using sums of unit fractions to ensure equitable distribution.^[4]^[5]^[2] An Egyptian fraction provides a representation of a positive rational number r > 0 as a finite sum r = \sum_{i=1}^k \frac{1}{n_i}, in which the denominators n_i are distinct positive integers.^[6] Every positive rational number admits infinitely many Egyptian fraction representations, allowing for variations in the number of terms and the sizes of the denominators. The insistence on distinct unit fractions distinguishes these expansions from simpler but repetitive forms, such as the decomposition \frac{1}{2} = \frac{1}{3} + \frac{1}{6} + \frac{1}{6}, which repeats the term \frac{1}{6} and thus violates the distinctness convention central to the Egyptian approach.^[6]^[7]

Unit fraction representations

The problem of unit fraction representations, central to Egyptian fractions, involves expressing a positive rational number \frac{p}{q} in lowest terms, where p and q are coprime positive integers, as a finite sum of distinct unit fractions: \frac{p}{q} = \sum_{i=1}^m \frac{1}{n_i} with distinct positive integers n_1 < n_2 < \cdots < n_m.^[6] A fundamental result guarantees the existence of such representations for every positive rational number, first proved by Leonardo of Pisa (Fibonacci) in his 1202 treatise Liber Abaci.^[6]^[8] Fibonacci's proof relies on an inductive construction that decomposes any proper fraction into unit fractions, ensuring the process terminates.^[9] These representations are not unique; every positive rational admits infinitely many distinct Egyptian fraction expansions, though only finitely many of a given length.^[10] Furthermore, for any fixed rational, expansions exist with arbitrarily many terms and arbitrarily large denominators, complicating the search for practical forms.^[6] The primary challenges in this area stem from the potential for lengthy expansions and the absence of a canonical form, motivating efforts to find representations that minimize the number of terms (length) or the maximum denominator, problems that remain open for many fractions, such as those with numerator at least 4.^[7] Non-greedy methods address these issues through splitting techniques, which iteratively apply algebraic identities to break down fractions into unit terms, for example, decomposing \frac{2}{n} = \frac{1}{\frac{n+1}{2}} + \frac{1}{\frac{n(n+1)}{2}} when n is odd, thereby avoiding duplicates and controlling expansion growth.

The Greedy Algorithm

Description

The greedy algorithm expresses any positive rational number as a finite sum of distinct unit fractions by iteratively subtracting the largest possible unit fraction from the current remainder without exceeding it.^[11] For a positive rational r = \frac{p}{q} in lowest terms with p, q positive integers, the steps are as follows: at each iteration, select the smallest positive integer n = \lceil q / p \rceil such that $1/n \leq p/q, append $1/n to the expansion, and replace the remainder with p/q - 1/n = (p n - q)/(q n) (reduced to lowest terms if needed); repeat until the remainder is zero. In formal notation, the greedy expansion of r is r = \sum_{k=1}^m 1/d_k, where d_1 = \lceil 1/r \rceil and, for k \geq 1, r_k = r - \sum_{i=1}^k 1/d_i, d_{k+1} = \lceil 1/r_k \rceil, with the process terminating when r_m = 0.^[12] The algorithm terminates after finitely many steps, as each subtraction yields a new remainder a'/b' in lowest terms where the numerator a' < a (the original numerator), guaranteeing that the numerators decrease until reaching zero.^[12] This procedure produces a unique expansion for any positive rational, since the choice of the largest unit fraction at each step is uniquely determined.^[2]

Examples

A simple example of the greedy algorithm is the expansion of \frac{3}{4}. The largest unit fraction not exceeding \frac{3}{4} is \frac{1}{2}, since \lceil \frac{4}{3} \rceil = 2. Subtracting gives \frac{3}{4} - \frac{1}{2} = \frac{1}{4}, which is already a unit fraction. Thus, \frac{3}{4} = \frac{1}{2} + \frac{1}{4}.^[6] For \frac{2}{3}, the largest unit fraction not exceeding \frac{2}{3} is \frac{1}{2}. Subtracting yields \frac{2}{3} - \frac{1}{2} = \frac{1}{6}, completing the expansion as \frac{2}{3} = \frac{1}{2} + \frac{1}{6}.^[6] The expansion of \frac{4}{17} demonstrates rapid growth in denominators: \frac{4}{17} = \frac{1}{5} + \frac{1}{29} + \frac{1}{1233} + \frac{1}{3039345}. This four-term representation highlights how the greedy choice can lead to very large final denominators even for modest starting fractions.^[2] To trace the algorithm explicitly, consider \frac{3}{7}. The first step finds \lceil \frac{7}{3} \rceil = 3, so subtract \frac{1}{3}: \frac{3}{7} - \frac{1}{3} = \frac{2}{21}. Next, \lceil \frac{21}{2} \rceil = 11, so subtract \frac{1}{11}: \frac{2}{21} - \frac{1}{11} = \frac{1}{231}. The remainder is the unit fraction \frac{1}{231}, yielding \frac{3}{7} = \frac{1}{3} + \frac{1}{11} + \frac{1}{231}.^[13]

Core Properties

Expansion length and efficiency

The length of a greedy Egyptian fraction expansion for a rational number p/q (with $0 < p < q and \gcd(p, q) = 1) is defined as the number of distinct unit fractions required to express it exactly as their sum.^[14] In the worst case, the greedy algorithm produces an expansion with at most p terms. This follows from the fact that at each step, the numerator of the remainder fraction strictly decreases (specifically, the new numerator is less than the previous one), eventually reaching 1, after which a single unit fraction suffices.^[14] For instance, the fraction $4/17 yields a greedy expansion of length 4:

\frac{4}{17} = \frac{1}{5} + \frac{1}{29} + \frac{1}{1233} + \frac{1}{3039345}.

Here, the numerators of the successive remainders are 4, 3, 2, and 1, illustrating the bound in action.^[2] Despite this upper bound, the greedy approach is often inefficient in terms of expansion length compared to the optimal Egyptian fraction representation, which minimizes the number of terms. The greedy choice of the largest possible unit fraction at each step can lead to remainders that require more subsequent terms than necessary. For example, $9/20 has a greedy expansion of length 3:

\frac{9}{20} = \frac{1}{3} + \frac{1}{9} + \frac{1}{180},

but an optimal representation uses only 2 terms:

\frac{9}{20} = \frac{1}{4} + \frac{1}{5}.

Similarly, $5/91 requires 5 terms in the greedy expansion but only 2 in the optimal one.^[2] These discrepancies highlight how the algorithm's local optimization can result in globally suboptimal lengths, with the gap widening in certain cases tied to sequences like Sylvester's that produce particularly long greedy expansions.^[14]

Sylvester's sequence

Sylvester's sequence, named after the mathematician J. J. Sylvester, is an integer sequence defined by the initial term s_0 = 2 and the recurrence relation s_{n+1} = s_n(s_n - 1) + 1 for n \geq 0.^[15] This generates the terms 2, 3, 7, 43, 1807, 3263443, and so on, where each subsequent term is one more than the product of all previous terms: s_{n+1} = \prod_{k=0}^n s_k + 1.^[15] The sequence was introduced in the context of problems related to the representation of numbers as sums of unit fractions.^[12] In the greedy algorithm for Egyptian fractions, Sylvester's sequence plays a central role by providing the denominators for the infinite greedy underapproximation of 1, satisfying \sum_{n=0}^\infty \frac{1}{s_n} = 1.^[16] The partial sums of the reciprocals relate directly to finite greedy expansions: specifically, \sum_{k=0}^{n-1} \frac{1}{s_k} = 1 - \frac{1}{\prod_{k=0}^{n-1} s_k} = 1 - \frac{1}{s_n - 1}.^[15] Thus, the greedy Egyptian fraction expansion of the rational $1 - \frac{1}{s_n - 1}, which is a fraction just below 1 with denominator s_n - 1, consists precisely of the first n terms \sum_{k=0}^{n-1} \frac{1}{s_k}.^[12] This property highlights the sequence's significance in determining expansion lengths: the fraction $1 - \frac{1}{s_n - 1} yields a greedy expansion of maximal length n among all proper fractions with denominators up to s_n - 1.^[16] Such expansions exemplify the worst-case behavior of the greedy algorithm, where the choice of the largest possible unit fraction at each step leads to the longest possible representation for fractions approaching 1 under the given denominator constraint.^[12] The terms of Sylvester's sequence exhibit double exponential growth, approximated by s_n \approx \phi^{2^n}, where \phi = \frac{1 + \sqrt{5}}{2} is the golden ratio; more precisely, s_n = \left\lfloor E^{2^{n+1}} + \frac{1}{2} \right\rfloor with E \approx 1.2640847353.^[15] This rapid growth ensures that the denominators in the corresponding greedy expansions become extraordinarily large even for modest n, underscoring the algorithm's potential for inefficient representations in these extremal cases.^[16]

Closest unit fraction approximations

In the greedy algorithm for Egyptian fractions, at each step the largest possible unit fraction $1/n not exceeding the current remainder r (where $0 < r < 1) is selected, making $1/n the closest unit fraction to r from below among all such options.$$] This criterion ensures that the immediate approximation error |r - 1/n| is minimized at that stage, as any smaller unit fraction $1/m with m > n would leave a larger residual difference. The approximation quality follows from the definition of n = \lceil 1/r \rceil, which implies $1/n \leq r < 1/(n-1). Thus, the error satisfies $0 \leq r - 1/n < 1/(n-1) - 1/n = 1/(n(n-1)), providing a tight bound on how closely $1/n underapproximates r while guaranteeing the greedy choice advances toward an exact representation.[$$ This local minimization of error contributes to the algorithm's convergence, though it does not always yield the shortest overall expansion. The greedy unit fractions align with semi-convergents of the continued fraction expansion of the original rational in some cases, where the selected $1/n corresponds to an intermediate convergent that best approximates the remainder from below using a single denominator.$$] For example, consider $4/17 \approx 0.23529: the greedy algorithm selects $1/5 = 0.2 as the first term, the closest unit fraction below $4/17, leaving a remainder of $4/17 - 1/5 = 3/85 \approx 0.03529.[$$

Special Expansions and Conditions

Maximum-length expansions

The maximum-length expansions in the greedy algorithm for Egyptian fractions refer to representations where the number of terms equals the numerator m of the fraction \frac{m}{n}. A necessary and sufficient condition for the greedy expansion of \frac{m}{n} to have exactly m terms is that n = k \cdot m! + s \cdot m + 1, where k is a non-negative integer and s belongs to the set S_m, a recursively defined set of residues modulo (m-1)! with S_3 = {0} and subsequent sets built to satisfy specific congruence conditions ensuring termination in m terms. Freitag and Phillips (1999) established this characterization, which highlights how such expansions arise from remainders that align precisely with unit fractions after m-1 steps.^[12] This condition connects directly to Sylvester's sequence, defined by e_0 = 2 and e_n = 1 + \prod_{i=0}^{n-1} e_i for n ≥ 1, yielding terms 2, 3, 7, 43, 1807, and so on. The partial sum S_k = \sum_{i=0}^k \frac{1}{e_i} = 1 - \frac{1}{e_{k+1} - 1} has a greedy expansion consisting exactly of those k+1 unit fractions, achieving length k+1 with the minimal possible maximum denominator e_k among all such (k+1)-term expansions approaching 1 from below. Under a bound D on the maximum denominator, the longest possible greedy expansion has length equal to the largest m such that e_{m-1} ≤ D, as any expansion of length m+1 would require a denominator at least e_m > D by the minimality property of the sequence. For instance, with D = 7, the maximum length is 3 (m=3, e_2=7 ≤7, e_3=43>7), achieved by \frac{41}{42} = \frac{1}{2} + \frac{1}{3} + \frac{1}{7}.^[12] Examples of maximum-length expansions for small m illustrate the rapid growth in denominators. For m=3, \frac{3}{7} = \frac{1}{3} + \frac{1}{11} + \frac{1}{231}, where the parameters are k=1, s=0. For m=4, \frac{4}{17} = \frac{1}{5} + \frac{1}{29} + \frac{1}{1233} + \frac{1}{3039345}, corresponding to k=0, s=4 in S_4 = {0,4}. These cases demonstrate how the condition forces the remainders to produce unit fractions only at the m-th step, often resulting in exponentially large final denominators. For D=10, the maximum length remains 3 (as e_3=43 >10), but certain fractions like scaled variants or those near Sylvester partial sums can approach this bound while keeping intermediate denominators small.^[12]^[17] These expansions tie into broader problems posed by Erdős, particularly the Erdős-Straus conjecture, which posits that \frac{4}{n} always admits a 3-term Egyptian fraction representation for n ≥ 2. The greedy algorithm typically yields at most 3 terms for \frac{4}{n}, but produces 4 terms (the maximum for numerator 4) precisely when n satisfies the congruence condition n ≡ 1 or 17 mod 24, such as n=25, 49, or 73; numerical verification supports the conjecture up to n=10^{14}, with these maximal cases providing insight into exceptions where longer expansions occur under the greedy rule. Chun (2011) links this to the general theory of maximal lengths, showing how Sylvester's sequence underpins the boundary between short and maximal expansions.^[12]

Congruence conditions for uniqueness

The uniqueness of the greedy Egyptian fraction expansion for a rational p/q (with p < q and \gcd(p,q)=1) occurs under specific modular arithmetic conditions that prevent alternative representations with the same number of terms, particularly when the minimal length is achieved solely by the greedy choice. A key theorem states that for fractions of the form $2/q, the greedy expansion has exactly two terms and is the unique two-term representation if and only if q \equiv 1 \pmod{2} (i.e., q is odd). In such cases, solving the equation $1/a + 1/b = 2/q with a < b yields only the greedy solution a = \lceil q/2 \rceil + 1, b = q(a-1), as other factorizations of the resulting Diophantine equation do not produce distinct integer solutions.^[12] For example, consider $2/5: the greedy algorithm selects $1/3 (the largest unit fraction ≤ 2/5), leaving remainder $1/15, so $2/5 = 1/3 + 1/15. This is the unique two-term representation, as the equation $1/a + 1/b = 2/5 reduces to (2a-5)(2b-5) = 25, whose positive integer factor pairs (1,25) and (5,5) yield only the greedy pair a=3, b=15 for distinct terms (the (5,5) pair gives repeated fractions).^[12] In contrast, while $2/3 = 1/2 + 1/6 is the unique two-term representation (via similar analysis of (2a-3)(2b-3) = 9, yielding only a=2, b=6), longer representations exist, such as $2/3 = 1/4 + 1/5 + 1/6 + 1/20, illustrating that overall uniqueness across all lengths is rare, but the greedy provides the unique minimal-length form under the congruence.^[12] More generally, the greedy expansion is unique (as the sole minimal-length representation) if at each step the remainder r_k / q_k satisfies r_k q_k \equiv 1 \pmod{d_k}, where d_k is the denominator chosen at that step; this ensures no alternative unit fraction selection is possible without exceeding the remainder or violating distinctness, preventing "splitting" into other combinations. This condition characterizes cases where q is not divisible by small primes in ways that allow shorter or alternative decompositions, often aligning with q avoiding certain residues modulo factorials like p!. For instance, extensions to higher p (e.g., p=3, q \equiv 1 \pmod{6}) yield similar uniqueness for three-term expansions when no two-term alternative exists.^[12]^[18] The proof outline relies on induction over the steps of the algorithm: assume the partial expansion up to step k-1 is unique; then the congruence r_k q_k \equiv 1 \pmod{d_k} implies d_k is the smallest integer such that $1/d_k \leq r_k / q_k < 1/(d_k - 1), and the greedy denominators behave like "primes" in the Egyptian fraction sense—no decomposition of $1/d_k into smaller distinct unit fractions fits the remainder without overlap or excess, blocking alternative paths. This is verified by showing that any potential split $1/d_k = 1/a + 1/b with a, b > d_k would require residues incompatible with the modular condition on the remainder.^[12]

Applications

Polynomial root approximations

Stratemeyer (1930) and Salzer (1947) introduced a method to approximate roots of polynomials using the greedy algorithm for Egyptian fractions, extending the technique from rational numbers to algebraic irrationals. The approach begins with an initial rational approximation r_0 to the root \alpha of a polynomial p(x) = 0. The greedy algorithm is then applied to r_0, decomposing it into a sum of distinct unit fractions. To continue the approximation beyond this rational, an auxiliary polynomial is constructed to represent the remaining value exactly, allowing computation of subsequent unit fractions without relying on floating-point arithmetic. This iterative process generates a series \alpha \approx \sum_{k=1}^\infty \frac{1}{d_k}, where each d_k is chosen as the smallest integer such that \frac{1}{d_k} is the largest unit fraction less than the current remainder, verified using evaluations of the auxiliary polynomial to ensure p(\sum_{i=1}^k \frac{1}{d_i}) > 0 or similar sign conditions. For quadratic polynomials of the form x^2 - s x - 1 = 0, where s is a positive integer, the method applied to convergents of the continued fraction expansion of the root yields a sequence of greedy terms that successively refine the approximation. The positive root \alpha = \frac{s + \sqrt{s^2 + 4}}{2} is approached by partial sums of the Egyptian fraction expansion, leveraging the polynomial to determine each denominator precisely. This is particularly effective for irrationals like the golden ratio, the root of x^2 - x - 1 = 0 with s = 1, \alpha = \phi \approx 1.6180339887. Starting with the initial approximation r_0 = 3/2 = 1.5, the greedy decomposition is $3/2 = 1/1 + 1/2, and continuing with the auxiliary polynomial derived from the original yields the expansion \phi = 1/1 + 1/2 + 1/9 + 1/145 + 1/37986 + \cdots (OEIS A117116). The partial sums provide rational approximations to \phi, such as $1/1 + 1/2 = 1.5 (error ≈ 0.118), $1/1 + 1/2 + 1/9 \approx 1.611 (error ≈ 0.007), and further terms reduce the error dramatically.^[19] The convergence of these partial sums to the root \alpha is remarkably rapid, with the error decreasing doubly exponentially due to the super-exponential growth of the denominators d_k, akin to the behavior in Sylvester's sequence where each d_{k+1} > d_k^2. Specifically, after k terms, the remainder satisfies $0 < \alpha - \sum_{i=1}^k \frac{1}{d_i} < \frac{1}{d_k d_{k+1}} < \frac{1}{d_k^3}, ensuring that additional terms yield approximations with precision far surpassing that of continued fractions for the same number of steps. This property makes the method valuable for high-precision computations of algebraic irrationals, though the growing denominators can lead to computationally intensive steps for large k.

Generated integer sequences

The greedy algorithm applied to the rational number 1 produces an infinite sequence of denominators known as Sylvester's sequence, where each term is the smallest integer greater than the previous such that the sum of the reciprocals equals 1 exactly. This sequence arises directly from iteratively selecting the largest unit fraction less than or equal to the current remainder, starting with the remainder 1. The first few terms are 2, 3, 7, 43, 1807, 3263443, and 10650056950807.^[20] Sylvester's sequence is defined recursively by e_1 = 2 and e_{n+1} = e_n(e_n - 1) + 1 for n \geq 1, or equivalently, e_{n+1} = 1 + \prod_{i=1}^n e_i. These terms grow doubly exponentially, with \log e_n \sim \phi^{n} where \phi is the golden ratio, leading to extremely large values even for small n. The terms are pairwise coprime, and their reciprocals sum precisely to 1: \sum_{n=1}^\infty \frac{1}{e_n} = 1. This property connects the sequence to number-theoretic questions, such as the infinitude of primes, since the coprimality implies that infinitely many terms must be prime or contain distinct prime factors. Applying the greedy algorithm to other rational numbers p/q < 1 generates finite integer sequences of denominators that terminate when the remainder reaches zero. These sequences often exhibit rapid growth in their later terms, similar to the exponential expansion in Sylvester's sequence, and are studied in number theory for their length and maximal denominator sizes. For instance, the expansion of $4/5 yields the denominators 2, 4, 20, corresponding to $4/5 = 1/2 + 1/4 + 1/20. For starting fractions of the form $1/k with integer k > 1, the sequence is trivial, consisting of the single term k, as $1/k is already a unit fraction; however, non-trivial sequences emerge when expanding more general rationals involving such terms, such as remainders in multi-step decompositions. These generated sequences extend the applications of Sylvester's construction to finite cases, highlighting the algorithm's role in producing distinct denominator sets with minimal overlap.^[12]

Weak and underapproximation variants

The weak greedy algorithm modifies the standard greedy approach for approximating rational numbers with Egyptian fraction partial sums by selecting, at each step, the largest unit fraction \frac{1}{n} such that the greedy denominator for the remaining fraction after subtraction is at most n. Formally, for a target \theta \in (0,1], the algorithm chooses n_k as the smallest integer n such that G(\theta - \sum_{i=1}^{k-1} \frac{1}{n_i} - \frac{1}{n}) \leq n, where G(\phi) = \lfloor 1/\phi \rfloor + 1 denotes the greedy choice for \phi.^[21] This variant, introduced by Hung Viet Chu, ensures convergence to \theta while bounding the growth of denominators, addressing cases where the standard greedy method produces exponentially large terms.^[22] In contrast to the standard greedy algorithm, which can lead to rapid denominator blow-up (e.g., for \theta = 4/17, yielding denominators up to 41,080,345), the weak greedy maintains more controlled sequences, with ratios b_{n+1}/b_n approaching t/(t-1) for a parameter t > 1 in certain implementations.^[21] Chu demonstrates that this approach sometimes yields better approximations than the standard method in terms of controlled growth.^[21] Further analysis in the same work establishes the approximation quality, showing that weak greedy expansions achieve sums within O(1/n^2) of \theta after n terms under specific conditions.^[22] Underapproximation variants focus on building partial sums strictly below \theta using greedy selections, often yielding unique optimal n-term representations for certain rationals.^[23] Melvyn B. Nathanson constructs an infinite set of rationals where the greedy underapproximation is the best possible n-term Egyptian fraction sum for every n, while also identifying counterexamples where it fails optimality.^[23] This builds on the greedy underapproximation algorithm, which iteratively adds the largest unit fraction less than the current remainder without exceeding \theta. Recent developments include explorations of odd greedy expansions, restricted to unit fractions with odd denominators. In a 2025 study, Louwsma and Martino characterize all positive rationals whose odd greedy expansion terminates in exactly two terms, identifying families such as $4 / (3 + 8t) for integers t \geq 0, which provide insights into bounded-length representations under denominator parity constraints.^[24] These variants collectively mitigate the denominator explosion in standard greedy expansions, offering practical alternatives for approximation tasks where term size is a concern.^[21]

Broader conjectures and comparisons

One prominent open conjecture related to the greedy algorithm for Egyptian fractions is the Erdős–Graham conjecture from the 1980s, which posits that every positive rational number admits a best Egyptian fraction expansion that is eventually greedy—meaning that, after finitely many terms, the remaining partial sums follow the greedy choice rule.^[25] This conjecture remains unproven as of 2025.^[25] A recent generalization, published in 2025, extends this idea to best Egyptian underapproximations, assuming the original claim and exploring non-constructive implications for rational representations.^[25] Comparisons between the greedy algorithm and optimal Egyptian fraction expansions highlight efficiency differences in length. The greedy method yields expansions of length O(\log q) for a rational with denominator q, whereas the shortest possible representation has length at most O(\sqrt{\log q \log \log q}), with Erdős conjecturing an optimal bound of O(\log \log q).^[9] Thus, the greedy approach can require significantly more terms than the theoretical optimum, potentially by a factor involving \log q / \log \log q. In contrast, the Engel expansion, a greedy-like algorithm producing sums of unit fractions via increasing partial products of denominators, often yields shorter representations for rationals compared to the standard greedy Egyptian method, though it prioritizes minimal partial quotients over unit steps. Unlike the Egyptian fraction requirement for distinct unit fractions, the Engel expansion uses a greedy process on partial products, often resulting in fewer terms but with rapidly growing denominators. Recent advancements from 2020 to 2025 include new algorithms that improve upon the greedy method in specific contexts, such as representations with restricted denominators. For instance, a 2025 algorithm enumerates all Egyptian fraction expansions using a given finite multiset of denominators, enabling comparisons to greedy outcomes and ties to optimal approximations under constraints.^[26] These developments underscore the greedy algorithm's role as a baseline for benchmarking more efficient methods. Broader implications of such conjectures connect to the density of rationals possessing unique greedy expansions. Studies suggest that the set of rationals with a unique greedy Egyptian fraction representation has positive density among all rationals, linking uniqueness properties to probabilistic models of denominator growth in greedy processes.^[27]

References

[1]
[PDF] Egyptian Fractions - Mathematics
Such sums are called Egyptian fractions. Figure 1: Egyptian fractions ... More generally, given any fraction p/q, apply the Greedy algorithm to obtain.
[2]
Egyptian Fractions
Fibonacci's Greedy algorithm to find Egyptian fractions with a sum of 1 is as follows: Choose the largest unit fraction we can, write it down and subtract itEgyptian Fractions · Fibonacci's Greedy Algorithm... · Egyptian Fractions for 1
[3]
Algorithms for Egyptian Fractions - UC Irvine
The greedy method produces an Egyptian fraction representation of a number q by letting the first unit fraction be the largest unit fraction less than q, and ...
[4]
Egyptian mathematics - University of St Andrews
The Rhind papyrus is named after the Scottish Egyptologist A Henry Rhind, who purchased it in Luxor in 1858. The papyrus, a scroll about 6 metres long and ...
[5]
The Rhind Papyrus and Ancient Egyptian Math - Ancient Origins
Dec 14, 2019 · In ancient Egypt, fractions were also represented differently than they are today. For example, 2/5 was written as 1/3 + 1/15. The fractions ...
[6]
Egyptian Fraction -- from Wolfram MathWorld
An Egyptian fraction is a sum of positive (usually) distinct unit fractions. The famous Rhind papyrus, dated to around 1650 BC contains a table of ...
[7]
[PDF] Two-term Egyptian fractions
every rational number admits a proper Egyptian fraction representation, and secondly, every ra- tional number has infinitely many proper representations.
[8]
[PDF] FROM ANCIENT EGYPTIAN FRACTIONS TO MODERN ALGEBRA
An Egyptian fraction is a finite sum of distinct rational numbers of the form ... the sum of (possibly a different number of) distinct unit fractions, and ...
[9]
[PDF] Representation via Egyptian Fractions - a. w. walker
It is not clear that every rational number even has an Egyptian fraction. The first proof of this result is due to Leonardo of Pisa (Fibonacci) and appears ...
[10]
Ten Algorithms for Egyptian Fractions | The Notebook Archive
Oct 2, 2018 · Any number has infinitely many Egyptian fraction representations, although there are only finitely many having a given number of terms [Ste92].
[11]
[PDF] Paul Erd˝os and Egyptian Fractions - UCSD Math
In particular, there are only finitely many numbers which cannot be the second-largest denominator in an Egyptian fraction representation of 1. Martin suggests ...
[12]
[PDF] Egyptian fractions, Sylvester's sequence, and the Erdős ... - OSU Math
Aug 1, 2011 · The greedy algorithm is a method that will convert any fraction into an Egyptian fraction. m n. = 1 d n m e. +. −n (mod m) nd n m e . If ...
[13]
[PDF] EGYPTIAN FRACTIONS
Answer: Fibonacci's Method guarantees that every proper fraction can be expanded into an infinite number of distinct unit fractions. 1.2 The value of k.
[14]
[PDF] Egyptian fractions
Taken together, these positive results about finding solutions to (3) in short intervals and arbitrary congruence classes can be seen as showing ...<|control11|><|separator|>
[15]
Sylvester's Sequence -- from Wolfram MathWorld
The sequence defined by e_0=2 and the quadratic recurrence equation e_n=1+product_(i=0)^(n-1)e_i=e_(n-1)^2-e_(n-1)+1. (1) This sequence arises in Euclid's ...Missing: paper | Show results with:paper
[16]
[PDF] arXiv:2503.12277v4 [math.NT] 21 Mar 2025
Mar 21, 2025 · λ = 1 x1. +. 1 x2. + ททท +. 1. xN−1. +. 1. xN − 1 is an Egyptian fraction obtained through the greedy algorithm. (2) The Infinite Greedy ...
[17]
http://www.mrob.com/pub/seq/a100140.html
[18]
A117116 - OEIS
A117116 - OEIS. (Greetings from The On-Line Encyclopedia of Integer Sequences!) Denominators of an Egyptian Fraction for phi = (1+sqrt(5))/2. For each term, ...Missing: greedy golden ratio
[19]
A000058 - OEIS
Another version of this sequence is given by A129871, which starts with 1, 2, 3, 7, 43, 1807, ... . The greedy Egyptian representation of 1 is 1 = 1/2 + 1/3 + 1 ...
[20]
[PDF] An algorithm for Egyptian fraction representations with restricted ...
Greedy algorithm. The most straightforward way to find an Egyptian fraction representation of a rational number r is the greedy algorithm: determine the largest.
[21]
Approximation by Egyptian Fractions and the Weak Greedy Algorithm
Feb 1, 2023 · We then investigate when a given weak greedy approximation (b_n) can be produced by the WGAA. Furthermore, we show that for any non-decreasing ( ...
[22]
Approximation by Egyptian fractions and the weak greedy algorithm
The idea is that at the n th step of our weak algorithm, we pick a n based on the “greedy choice up to a constant”. Specifically, fix ...
[23]
[2202.00191] Underapproximation by Egyptian fractions - arXiv
An infinite set of rational numbers is constructed for which the greedy underapproximations are best, and numbers for which the greedy algorithm ...Missing: Ball | Show results with:Ball
[24]
[PDF] Rational Numbers with Two-Term Odd Greedy Expansion
May 28, 2025 · Given a positive rational number, its greedy Egyptian expan- sion begins with the largest unit fraction at most this number, adds the largest ...
[25]
Generalizing a conjecture of Erdős and Graham via best Egyptian ...
Oct 13, 2025 · V. Kovač, On eventually greedy best underapproximations by Egyptian fractions, J. Number Theory, 268 (2025), 39–48. Z.
[26]
Engel expansion - Wikipedia
If x is rational, its Engel expansion provides a representation of x as an Egyptian fraction. ... expansion generated by the greedy algorithm for Egyptian ...
[27]
An algorithm for Egyptian fraction representations with restricted ...
The subscription price for 2025 is US $270/year for the electronic version, and $360/year (+$50, if shipping outside the US) for print and electronic.
[28]
Density and Finiteness Results on Sums of Fractions - ResearchGate
Aug 6, 2025 · ... Egypt, Egyptian fractions have been con-. tinuously and extensively studied. In 1202, Fibonacci gave a greedy algorithm. to obtain an Egyptian ...<|control11|><|separator|>