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 7th 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 17th 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 Sierpinski1.
The following MACSYMA or maxima code prints the first 27 terms of this 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 2014 Dec 07.
s.27