# Sequence A100140: Largest Denominator of Greedy Egyptian Fraction Sum for M/N

This sequence, Sloane's A100140, gives the largest denominator in the Egyptian fraction expansion, using the "greedy" algorithm, for fractions with denominator N.

An Egyptian fraction expansion for a fraction like ^{3}/_{4} is a sum
of unit fractions like ^{1}/_{2}+^{1}/_{4}. The "greedy" algorithm is:

Given: Fraction X/Y, where X and Y are positive integers and X<Y.

1: Let A be the smallest integer such that AX ≥ Y

2: 1/A is the first (or next) term in the Egyptian fraction.

3: Compute X/Y - 1/A and reduce to lowest terms. The result is
the new X/Y. If nonzero, go back to step 1 and repeat.

A100140 is a subset of sequence
A050210, which has N-1 terms for each denominator
N. For example, terms 16 through 21 of A050210
correspond to the expansions of ^{1}/_{7} through ^{6}/_{7}.

Sequence A100140 starts:

1, 2, 6, 4, 20, 3, 231, 24, 45, 20, 4070, 12, 2145, 231, 120, 240, 3039345, 45, 2359420, 180, 1428, 4070, 1019084, 120, 53307975, 2145, 1350, 1428, 1003066152, 120, 1127619917796295, 16800, 26796, 3039345, 1104740, 72, 884004, 2359420, 1288092, 1320, 1396792694910, 1428, 185204595153417, 9548, 223380, 1019084, 6740884579520, 1680, 1218809328828, 53307975, 751944, 109252, 1458470173998990524806872692984177836808420, 1350, 2301585, 2856, 375972, 1003066152, 2246452569756, 180, 34454310087467394631, 1127619917796295, 7170345, 34240, 83128196385, 26796, 1343873519875428369036, 46264820, 15072900093293070, 1104740, 11770376583439808963536545, 50904, 8993340768034569594892420, 884004, 53307975, 7630780, 108069680298198465, 1288092, 8104050103296840, 677475120, 1167492086145, 1396792694910, 308461667853570, 1820, 253625459220, 185204595153417, 1132665082908, 124490520, 6494499543074890436870241790813851000203090, 223380, 17452649778145716451681, 3588820180, 1127619917796295, 6740884579520, 135884896858431735, 1391520, 579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665, 1218809328828, 21874545, 230409900, ...

For example, when N is 7, there are 6 possible fractions, ^{1}/_{7}
through ^{6}/_{7}. Their Egyptian fraction expansions are:

^{1}/_{7}

^{2}/_{7} = ^{1}/_{4}+^{1}/_{28}

^{3}/_{7} = ^{1}/_{3}+^{1}/_{11}+^{1}/_{231}

^{4}/_{7} = ^{1}/_{2}+^{1}/_{14}

^{5}/_{7} = ^{1}/_{2}+^{1}/_{5}+^{1}/_{70}

^{6}/_{7} = ^{1}/_{2}+^{1}/_{3}+^{1}/_{42}

The largest denominators in these six expansions are 7, 28, 231, 14,
70 and 42; these make up terms 16 through 21 of sequence
A050210. The largest of these is 231, which is the
7^{th} term of A100140.

In general when doing an Egyptian fraction expansion, you want to keep
the denominators small. The "greedy" algorithm isn't very good, as
shown by this sequence. For example, the 17^{th} term is 3039345
because the greedy algorithm turns ^{4}/_{17} into
^{1}/_{5}+^{1}/_{29}+^{1}/_{1233}+^{1}/_{3039345}. There are much
better expansions of ^{4}/_{17}, such as
^{1}/_{6}+^{1}/_{15}+^{1}/_{510}, which has fewer terms and smaller
denominators.

The problem of how to find the "best" Egyptian fraction expansion is
quite complex. There are many unsolved sub-problems, such as the
Erdos-Straus conjecture, which asserts that 4/N can always be
expressed in 3 or fewer terms, and a similar assertion for 5/N
conjectured by Sierpinski^{1}.

The following MACSYMA or maxima code prints the first 27 terms ofthis sequence:

egypt(x, a) := block([i,n,d,p,e, on, od], ( n : num(x) , d : n/x, on : n, od : d, p : 0, e : [], for i:1 while x>0 do ( n : num(x), d : n/x, p : fix((d+n-1)/n), x : x - 1/p, e : append(e, [p]) ), if 1=2 then print(on, "/", od, " = ", e), return(p) ) ); for b:2 step 1 thru 27 do ( max:2, for a:2 step 1 thru b-1 do ( if gcd(a,b)=1 then ( m : egypt(a/b, b), if m>max then max : m ) ), print("N =", b, "max denominator:", max) );The Rhind papyrus lists Egyptian fraction expansions for all fractions of the form 2/N for odd N from 5 to 101. Many of them seem to be derived from the following identity:

^{2}/_{pq} = ^{2}/_{(p+1)} × ^{(p+1)}/_{pq}

= ^{2p}/_{pq(p+1)} + ^{2}/_{pq(p+1)}

= ^{2}/_{q(p+1)} + ^{2}/_{pq(p+1)}

where the denominator N has been factored into p×q; because
N is odd, both p and q are odd and the sum reduces to two unit
fractions. For example, if N is 21=3×7, we get ^{2}/_{21} =
^{2}/_{28}+^{2}/_{84} = ^{1}/_{14}+^{1}/_{42}.

Some other sequences are discussed here.

**1 :**
http://mathworld.wolfram.com/EgyptianFraction.html
Eric W.
Weisstein, Mathworld (sponsored by Wolfram Research), "Egyptian
Fraction"

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2018 Jan 06. s.11