(*^
::[ Information =
"This is a Mathematica Notebook file. It contains ASCII text, and can be
transferred by email, ftp, or other text-file transfer utility. It should
be read or edited using a copy of Mathematica or MathReader. If you
received this as email, use your mail application or copy/paste to save
everything from the line containing (*^ down to the line containing ^*)
into a plain text file. On some systems you may have to give the file a
name ending with ".ma" to allow Mathematica to recognize it as a Notebook.
The line below identifies what version of Mathematica created this file,
but it can be opened using any other version as well.";
FrontEndVersion = "Macintosh Mathematica Notebook Front End Version 2.2";
MacintoshStandardFontEncoding;
fontset = title, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeTitle, center, M7, bold, e8, 24, "Times";
fontset = subtitle, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeTitle, center, M7, bold, e6, 18, "Times";
fontset = subsubtitle, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeTitle, center, M7, italic, e6, 14, "Times";
fontset = section, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeSection, grayBox, M22, bold, a20, 18, "Times";
fontset = subsection, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeSection, blackBox, M19, bold, a15, 14, "Times";
fontset = subsubsection, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeSection, whiteBox, M18, bold, a12, 12, "Times";
fontset = text, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times";
fontset = smalltext, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 10, "Times";
fontset = input, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeInput, M42, N23, bold, L-5, 12, "Courier";
fontset = output, output, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, L-5, 12, "Courier";
fontset = message, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, R65535, L-5, 12, "Courier";
fontset = print, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, L-5, 12, "Courier";
fontset = info, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, B65535, L-5, 12, "Courier";
fontset = postscript, PostScript, formatAsPostScript, output, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeGraphics, M7, l34, w282, h287, 12, "Courier";
fontset = name, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, italic, 10, "Geneva";
fontset = header, inactive, noKeepOnOnePage, preserveAspect, M7, 12, "Times";
fontset = leftheader, inactive, L2, 12, "Times";
fontset = footer, inactive, noKeepOnOnePage, preserveAspect, center, M7, 12, "Times";
fontset = leftfooter, inactive, L2, 12, "Times";
fontset = help, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 10, "Times";
fontset = clipboard, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times";
fontset = completions, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times";
fontset = special1, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times";
fontset = special2, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times";
fontset = special3, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times";
fontset = special4, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times";
fontset = special5, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times";
paletteColors = 128; automaticGrouping; currentKernel;
]
:[font = title; inactive; preserveAspect; startGroup]
Algorithms for Egyptian Fractions
:[font = text; inactive; preserveAspect]
\-
This Mathematica notebook has been formatted for use with nb2html and filter. Unfortunately, this makes it less directly readable as a notebook, especially in the references... Lines beginning with backslashes control the filtration of this source into separate HTML files. (This includes lines with HTML controls marked with at-signs, to be translated to less-greater brackets once safely past nb2html's translation tables.) The embedded HTML cross-references assume that these files have names corresponding to the following keywords:
intro - Introduction (with pointers to other sections)
approx - Methods Based on Approximation
conflict - Conflict Resolution Methods
binary - Methods Based on the Binary Number System
cfrac - Continued Fraction Methods
greed - Reverse Greedy Methods
force - Brute Force Methods
smallnum - Small Numerators
refs - References
\+
\@HR
\-
\!intro
;[s]
3:0,0;8,1;19,0;890,-1;
2:2,16,12,Times,0,12,0,0,0;1,16,12,Times,2,12,0,0,0;
:[font = section; inactive; Cclosed; preserveAspect; startGroup]
Introduction
:[font = text; inactive; preserveAspect]
When we use fractional numbers today, there are two ways we usually represent them: as fractions (ratios of integers) such as 5/6, and as decimal numbers such as 0.8333.
Computers typically use binary versions of either of these two representations. But these are not the only possibilities. The ancient Egyptians used a third method: instead of writing down a single fraction, they would write a sum of several distinct
\@I
unit fractions,
\@/I
each having numerator one. For instance the Egyptians would have written 5/6 as 1/2 + 1/3 (of course, they would have used hieroglyphics instead of Arabic numerals). Today such sums are known as
\@I
Egyptian fractions.
\@/I
(We will see another important modern representation,
\@I
continued fractions,
\@/I
later.)
;[s]
7:0,0;428,1;442,0;650,1;668,0;733,1;752,0;767,-1;
2:4,16,12,Times,0,12,0,0,0;3,16,12,Times,2,12,0,0,0;
:[font = text; inactive; preserveAspect]
Any number has infinitely many Egyptian fraction representations, although there are only finitely many having a given number of terms
\@A HREF="refs.html#Ste92"
\.[Ste92]
\@/A
. It is not known how the Egyptians found their representations, but today many algorithms are known for this problem, each behaving differently in terms of the number of unit fractions produced, the size of the denominators of the fractions, and the time taken to find the representations. For a good but brief introduction to Egyptian fraction algorithms and their implementation in
\@I
Mathematica,
\@/I
see Wagon's book
\@A HREF="refs.html#Wag91"
\.[Wag91]
\@/A
. Here we examine a number of algorithms in more detail, implement them, and analyze their performance. We also include some investigations into how many unit fractions are needed to represent rational numbers having small numerators.
;[s]
3:0,0;567,1;578,0;880,-1;
2:2,14,10,Times,0,12,0,0,0;1,14,10,Times,2,12,0,0,0;
:[font = text; inactive; preserveAspect]
We will represent Egyptian fractions as lists of unit fractions. The original rational number represented by such a list can be recovered by Plus@@%. Throughout we use q to denote the rational number we are trying to represent, or x/y when we want to talk about its numerator and denominator separately.
;[s]
3:0,0;142,1;150,0;306,-1;
2:2,16,12,Times,0,12,0,0,0;1,18,12,Courier,0,12,0,0,0;
:[font = text; inactive; preserveAspect; endGroup]
An earlier version of this notebook was published as "Ten Algorithms for Egyptian Fractions" in
\@I
Mathematica in Education and Research.
\@/I
I have since improved the
\@A HREF="binary.html#binrem"
\.binary remainder method
\@/A
, and added the
\@A HREF="greed.html"
\.reverse greedy
\@/A
,
\@A HREF="force.html"
\.generalized remainder, and small multiple
\@/A
methods.
\@A HREF="approx.html"
\!approx
;[s]
3:0,0;100,1;137,0;407,-1;
2:2,16,12,Times,0,12,0,0,0;1,16,12,Times,2,12,0,0,0;
:[font = section; inactive; Cclosed; preserveAspect; startGroup]
Methods Based on Approximation
:[font = text; inactive; preserveAspect]
\!intro
The most natural and obvious method of finding an Egyptian fraction representation for a given number is to approximate the number as closely as possible by a single unit fraction, and then to use the same method to represent the remainder. For instance, the largest unit fraction less than 5/6 is 1/2, and removing 1/2 from 5/6 leaves 1/3, so this idea leads to the representation 1/2+1/3 mentioned above. There are several ways of translating this idea into a specific algorithm.
:[font = subsection; inactive; preserveAspect; startGroup]
The Greedy Method
:[font = text; inactive; preserveAspect]
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 then continuing in the same manner to represent the remaining value. If q>1, we first separate out the integer part Floor[q] before representing the remaining fraction. Our implementation works by first computing a list of the fractions left after subtracting each successive term in the greedy representation, and then subtracting a shifted copy of this list from itself.
;[s]
7:0,0;75,1;76,0;151,1;152,0;275,1;283,0;533,-1;
2:4,16,12,Times,0,12,0,0,0;3,18,12,Courier,0,12,0,0,0;
:[font = input; initialization; preserveAspect]
*)
GreedyPart[q_Integer] := 0;
GreedyPart[Rational[1,y_]] := 0;
GreedyPart[q_Rational] :=
q - If[q < 0 || q > 1, Floor[q],
Rational[1,1+Quotient[1,q]]];
SubtractShifted[l_] := Drop[l,-2] - Take[l,{2,-2}];
EgyptGreedy[q_] :=
SubtractShifted[FixedPointList[GreedyPart,q]]
(*
:[font = text; inactive; preserveAspect]
Let us now make sure that this routine correctly finds an Egyptian fraction representation, and analyze its performance. If we start with x/y, the remaining value after one step is
(y mod x) / y(Ceiling[y/x]), which has a smaller numerator. Similarly, the numerator decreases after each further step, so the algorithm always halts. The resulting sequence of fractions clearly adds to the original input, so the only way this method could go wrong would be if two of the fractions were equal (this is not allowed in Egyptian fractions). But this can't happen, since the denominators of the fractions must be strictly increasing: if we had two successive terms 1/a and 1/b with b ² a, we could have chosen 1/(a-1) instead of 1/a.
:[font = text; inactive; preserveAspect]
Since the numerator decreases after each step, the number of terms in the representation of x/y is at most x. In many cases we could expect each successive numerator to be randomly distributed modulo the previous numerator; if this were really true we would instead only expect to see O(Log x) terms. The denominator is at most squared each step, so the largest denominator is at most y^(2^x) or more generally y^(2^k) where k is the number of terms. The number of operations performed by the algorithm is proportional to k, but some of these operations might involve arithmetic on very large numbers. We demonstrate this method with a simple example.
:[font = input; preserveAspect; startGroup]
EgyptGreedy[18/23]
:[font = output; output; inactive; preserveAspect; endGroup]
{1/2, 1/4, 1/31, 1/2852}
;[o]
1 1 1 1
{-, -, --, ----}
2 4 31 2852
:[font = text; inactive; preserveAspect]
That example was fairly well behaved; Wagon
\@A HREF="refs.html#Wag91"
\.[Wag91]
\@/A
suggests trying this method on 31/311, which produces a representation with 10 terms, the maximum denominator having over 500 digits. (As we will see later, other methods produce much better representations for 31/311.)
:[font = text; inactive; preserveAspect]
We can easily modify our code to test the assertion that the numerators of the fractions remaining at each step do indeed decrease.
:[font = input; initialization; preserveAspect]
*)
EgyptGreedyNumerators[q_] :=
Numerator[Drop[FixedPointList[GreedyPart,q],-2]]
(*
:[font = input; preserveAspect; startGroup]
EgyptGreedyNumerators[18/23]
:[font = output; output; inactive; preserveAspect; endGroup; endGroup]
{18, 13, 3, 1}
;[o]
{18, 13, 3, 1}
:[font = subsection; inactive; preserveAspect; startGroup]
The Harmonic Method
:[font = text; inactive; preserveAspect]
The greedy method treats the integer and fractional parts of a number differently. Instead, we can always remove the largest unit fraction that is smaller than both x/y and the previously removed unit fraction, even if x/y is larger than one. We treat this separately from the greedy method as it must be implemented somewhat differently Ð FixedPointList now needs two values, the remaining fraction and the bound on the denominator. Once we have found the sequence of remaining fractions, we remove the denominator bounds by Transpose (faster than applying First to each member of the list) and subtract the shifted list from itself as before. Our function takes two arguments, the first being the number we want to represent and the second being the largest denominator already included in the representation. The same method can also be used to generate Egyptian fractions in which the first term is arbitrarily small, simply by supplying a large integer in the second argument.
;[s]
7:0,0;342,1;356,0;529,1;538,0;561,1;566,0;987,-1;
2:4,16,12,Times,0,12,0,0,0;3,18,12,Courier,0,12,0,0,0;
:[font = input; initialization; preserveAspect]
*)
HarmonicPart[{0,d_}] := {0,d};
HarmonicPart[{Rational[1,y_],d_}] := {0,d};
HarmonicPart[{q_,d_}] :=
Max[d,1+Quotient[1,q]] //
{q-1/#,#+1} &;
(*
:[font = input; initialization; preserveAspect]
*)
EgyptHarmonic[q_,d_] :=
Transpose[FixedPointList[HarmonicPart,{q,d}]][[1]] //
SubtractShifted
(*
:[font = text; inactive; preserveAspect]
The algorithm constructs a fragment of the harmonic series 1/2+1/3+1/4+1/5+... until this would produce a result larger than the original input, at which point the algorithm switches to the Greedy method for the remainder. This switch must happen after at most Exp[O(x/y+Log d)] terms, because the Harmonic series diverges (the sum up to 1/k is roughly Log k). Therefore the correctness of the algorithm follows from the same analysis we saw before. However it may produce many more terms, with larger denominators, than the greedy method. Each step at most squares the denominator, so when the switch happens, the denominator of the remaining fraction can be at most doubly exponentially small with respect to x/y, and the eventual number of terms is doubly exponential in x/y (singly exponential in d). By the same analysis as the greedy algorithm, the largest denominator of the eventual representation is then at most quadruply exponential in x/y and triply exponential in d. As for the greedy method, this is only the worst case, and we can expect in practice to see one fewer level of exponentials in both the number of terms and the largest denominator. Even so, this algorithm tends to produce large representations.
:[font = input; preserveAspect; startGroup]
EgyptHarmonic[18/23,5]
:[font = output; output; inactive; preserveAspect; endGroup]
{1/5, 1/6, 1/7, 1/8, 1/9, 1/28, 1/794, 1/23010120}
;[o]
1 1 1 1 1 1 1 1
{-, -, -, -, -, --, ---, --------}
5 6 7 8 9 28 794 23010120
:[font = text; inactive; preserveAspect; endGroup]
\@A NAME="odd"
:[font = subsection; inactive; preserveAspect; startGroup]
The Odd Greedy Method
:[font = text; inactive; preserveAspect]
\@/A
Each x/y with y odd is known to have an Egyptian fraction representation in which each denominator is odd
\@A HREF="refs.html#Bre54"
\.[Bre54
\@/A
,
\@A HREF="refs.html#Ste54"
\.Ste54]
\@/A
. Conversely, if y is even, at least one of the terms in its representation must also be even. The most straightforward method of finding an odd-denominator representation seems to be to modify the greedy method to only use odd denominators, but it is not known whether this really works.
:[font = input; initialization; preserveAspect]
*)
OddGreedyPart[{0,d_}] := {0,d};
OddGreedyPart[{Rational[1,y_],d_}] := {0,d};
OddGreedyPart[{q_,d_}] :=
Max[d,1+Quotient[1,q]] //
If[OddQ[#],#,#+1] & //
{q-1/#,#+1} &;
EgyptOddGreedy[q_,d_:3] :=
Transpose[FixedPointList[OddGreedyPart,{q,d}]][[1]] //
SubtractShifted
(*
:[font = text; inactive; preserveAspect]
Unlike the greedy method, the numerators of the remaining fractions do not decrease at each step.
There are two reasons: first, like the harmonic method, we use a parameter d to make sure that the fractions we generate are distinct; d is used until the series 1/3+1/5+1/7+1/9+... becomes larger than q, at which point it becomes unimportant, but in this stage the numerators will in general increase. Second, whenever parity forces us to use a larger denominator than the greedy method, the denominator will again increase. We now give an example with q<1/3 to demonstrate the second phenomenon.
:[font = input; initialization; preserveAspect]
*)
EgyptOddGreedyNumerators[q_,d_:3] :=
Transpose[FixedPointList[OddGreedyPart,{q,d}]][[1]] //
Numerator[Drop[#,-2]] &
(*
:[font = input; preserveAspect; startGroup]
EgyptOddGreedy[10/39]
:[font = output; output; inactive; preserveAspect; endGroup]
{1/5, 1/19, 1/265, 1/196365}
;[o]
1 1 1 1
{-, --, ---, ------}
5 19 265 196365
:[font = input; preserveAspect; startGroup]
EgyptOddGreedyNumerators[10/39]
:[font = output; output; inactive; preserveAspect; endGroup]
{10, 11, 14, 1}
;[o]
{10, 11, 14, 1}
:[font = text; inactive; preserveAspect]
Proving whether this method always halts remains an important open problem in the theory of Egyptian fractions
\@A HREF="refs.html#Guy81"
\.[Guy81
\@/A
,
\@A HREF="refs.html#KW91"
\.KW91]
\@/A
. A heuristic argument shows that the answer is likely to be positive. After enough fractions have been generated for d to become unimportant, each step reduces the remaining fraction from some value x/y to a smaller fraction in which the numerator is between 1 and 2x-1. If each successive numerator were randomly distributed in this range, we would expect to see the numerators decrease by a factor of Exp[Integrate[Log[x],{x,0,2}]/2] Å 0.73576 per step. Therefore we should expect the algorithm to produce roughly (Log n)/(1-Log 2) Å 3.26 Log n unit fractions before halting, where n is the numerator of the remaining fraction at the point that d becomes unimportant. Of course nothing here is actually random, which is why this argument is not rigorous. (Also it ignores the possibility that the numerator and denominator of the fraction remaining after some steps may have a common factor, but that only serves to reduce the number of terms.) To test this argument, we compare it with the actual performance of our algorithm.
;[s]
5:0,0;599,1;631,0;632,1;633,0;1231,-1;
2:3,16,12,Times,0,12,0,0,0;2,18,12,Courier,0,12,0,0,0;
:[font = input; preserveAspect]
TestOddGreedy[q_] :=
EgyptOddGreedyNumerators[q] //
ListPlot[Log[#]/(1-Log[2]),
PlotJoined->True,
AxesOrigin->{0,0}]&
:[font = input; preserveAspect; startGroup]
TestOddGreedy[1999999991/123412340001]
:[font = postscript; PostScript; formatAsPostScript; output; inactive; preserveAspect; pictureLeft = 34; pictureWidth = 282; pictureHeight = 174; endGroup]
%!
%%Creator: Mathematica
%%AspectRatio: .61803
MathPictureStart
%% Graphics
/Courier findfont 10 scalefont setfont
% Scaling calculations
0.0238095 0.0634921 0.0147151 0.00843347 [
[(2)] .15079 .01472 0 2 Msboxa
[(4)] .27778 .01472 0 2 Msboxa
[(6)] .40476 .01472 0 2 Msboxa
[(8)] .53175 .01472 0 2 Msboxa
[(10)] .65873 .01472 0 2 Msboxa
[(12)] .78571 .01472 0 2 Msboxa
[(14)] .9127 .01472 0 2 Msboxa
[(10)] .01131 .09905 1 0 Msboxa
[(20)] .01131 .18338 1 0 Msboxa
[(30)] .01131 .26772 1 0 Msboxa
[(40)] .01131 .35205 1 0 Msboxa
[(50)] .01131 .43639 1 0 Msboxa
[(60)] .01131 .52072 1 0 Msboxa
[(70)] .01131 .60506 1 0 Msboxa
[ -0.001 -0.001 0 0 ]
[ 1.001 .61903 0 0 ]
] MathScale
% Start of Graphics
1 setlinecap
1 setlinejoin
newpath
[ ] 0 setdash
0 g
p
p
.002 w
.15079 .01472 m
.15079 .02097 L
s
P
[(2)] .15079 .01472 0 2 Mshowa
p
.002 w
.27778 .01472 m
.27778 .02097 L
s
P
[(4)] .27778 .01472 0 2 Mshowa
p
.002 w
.40476 .01472 m
.40476 .02097 L
s
P
[(6)] .40476 .01472 0 2 Mshowa
p
.002 w
.53175 .01472 m
.53175 .02097 L
s
P
[(8)] .53175 .01472 0 2 Mshowa
p
.002 w
.65873 .01472 m
.65873 .02097 L
s
P
[(10)] .65873 .01472 0 2 Mshowa
p
.002 w
.78571 .01472 m
.78571 .02097 L
s
P
[(12)] .78571 .01472 0 2 Mshowa
p
.002 w
.9127 .01472 m
.9127 .02097 L
s
P
[(14)] .9127 .01472 0 2 Mshowa
p
.001 w
.04921 .01472 m
.04921 .01847 L
s
P
p
.001 w
.0746 .01472 m
.0746 .01847 L
s
P
p
.001 w
.1 .01472 m
.1 .01847 L
s
P
p
.001 w
.1254 .01472 m
.1254 .01847 L
s
P
p
.001 w
.17619 .01472 m
.17619 .01847 L
s
P
p
.001 w
.20159 .01472 m
.20159 .01847 L
s
P
p
.001 w
.22698 .01472 m
.22698 .01847 L
s
P
p
.001 w
.25238 .01472 m
.25238 .01847 L
s
P
p
.001 w
.30317 .01472 m
.30317 .01847 L
s
P
p
.001 w
.32857 .01472 m
.32857 .01847 L
s
P
p
.001 w
.35397 .01472 m
.35397 .01847 L
s
P
p
.001 w
.37937 .01472 m
.37937 .01847 L
s
P
p
.001 w
.43016 .01472 m
.43016 .01847 L
s
P
p
.001 w
.45556 .01472 m
.45556 .01847 L
s
P
p
.001 w
.48095 .01472 m
.48095 .01847 L
s
P
p
.001 w
.50635 .01472 m
.50635 .01847 L
s
P
p
.001 w
.55714 .01472 m
.55714 .01847 L
s
P
p
.001 w
.58254 .01472 m
.58254 .01847 L
s
P
p
.001 w
.60794 .01472 m
.60794 .01847 L
s
P
p
.001 w
.63333 .01472 m
.63333 .01847 L
s
P
p
.001 w
.68413 .01472 m
.68413 .01847 L
s
P
p
.001 w
.70952 .01472 m
.70952 .01847 L
s
P
p
.001 w
.73492 .01472 m
.73492 .01847 L
s
P
p
.001 w
.76032 .01472 m
.76032 .01847 L
s
P
p
.001 w
.81111 .01472 m
.81111 .01847 L
s
P
p
.001 w
.83651 .01472 m
.83651 .01847 L
s
P
p
.001 w
.8619 .01472 m
.8619 .01847 L
s
P
p
.001 w
.8873 .01472 m
.8873 .01847 L
s
P
p
.001 w
.9381 .01472 m
.9381 .01847 L
s
P
p
.001 w
.96349 .01472 m
.96349 .01847 L
s
P
p
.001 w
.98889 .01472 m
.98889 .01847 L
s
P
p
.002 w
0 .01472 m
1 .01472 L
s
P
p
.002 w
.02381 .09905 m
.03006 .09905 L
s
P
[(10)] .01131 .09905 1 0 Mshowa
p
.002 w
.02381 .18338 m
.03006 .18338 L
s
P
[(20)] .01131 .18338 1 0 Mshowa
p
.002 w
.02381 .26772 m
.03006 .26772 L
s
P
[(30)] .01131 .26772 1 0 Mshowa
p
.002 w
.02381 .35205 m
.03006 .35205 L
s
P
[(40)] .01131 .35205 1 0 Mshowa
p
.002 w
.02381 .43639 m
.03006 .43639 L
s
P
[(50)] .01131 .43639 1 0 Mshowa
p
.002 w
.02381 .52072 m
.03006 .52072 L
s
P
[(60)] .01131 .52072 1 0 Mshowa
p
.002 w
.02381 .60506 m
.03006 .60506 L
s
P
[(70)] .01131 .60506 1 0 Mshowa
p
.001 w
.02381 .03158 m
.02756 .03158 L
s
P
p
.001 w
.02381 .04845 m
.02756 .04845 L
s
P
p
.001 w
.02381 .06532 m
.02756 .06532 L
s
P
p
.001 w
.02381 .08218 m
.02756 .08218 L
s
P
p
.001 w
.02381 .11592 m
.02756 .11592 L
s
P
p
.001 w
.02381 .13278 m
.02756 .13278 L
s
P
p
.001 w
.02381 .14965 m
.02756 .14965 L
s
P
p
.001 w
.02381 .16652 m
.02756 .16652 L
s
P
p
.001 w
.02381 .20025 m
.02756 .20025 L
s
P
p
.001 w
.02381 .21712 m
.02756 .21712 L
s
P
p
.001 w
.02381 .23399 m
.02756 .23399 L
s
P
p
.001 w
.02381 .25085 m
.02756 .25085 L
s
P
p
.001 w
.02381 .28459 m
.02756 .28459 L
s
P
p
.001 w
.02381 .30145 m
.02756 .30145 L
s
P
p
.001 w
.02381 .31832 m
.02756 .31832 L
s
P
p
.001 w
.02381 .33519 m
.02756 .33519 L
s
P
p
.001 w
.02381 .36892 m
.02756 .36892 L
s
P
p
.001 w
.02381 .38579 m
.02756 .38579 L
s
P
p
.001 w
.02381 .40265 m
.02756 .40265 L
s
P
p
.001 w
.02381 .41952 m
.02756 .41952 L
s
P
p
.001 w
.02381 .45326 m
.02756 .45326 L
s
P
p
.001 w
.02381 .47012 m
.02756 .47012 L
s
P
p
.001 w
.02381 .48699 m
.02756 .48699 L
s
P
p
.001 w
.02381 .50386 m
.02756 .50386 L
s
P
p
.001 w
.02381 .53759 m
.02756 .53759 L
s
P
p
.001 w
.02381 .55446 m
.02756 .55446 L
s
P
p
.001 w
.02381 .57132 m
.02756 .57132 L
s
P
p
.001 w
.02381 .58819 m
.02756 .58819 L
s
P
p
.002 w
.02381 0 m
.02381 .61803 L
s
P
P
0 0 m
1 0 L
1 .61803 L
0 .61803 L
closepath
clip
newpath
.004 w
.0873 .60332 m
.15079 .5802 L
.21429 .55235 L
.27778 .44148 L
.34127 .42326 L
.40476 .43552 L
.46825 .44934 L
.53175 .28058 L
.59524 .2567 L
.65873 .22462 L
.72222 .23964 L
.78571 .24803 L
.84921 .25598 L
.9127 .25951 L
.97619 .01472 L
s
% End of Graphics
MathPictureEnd
:[font = text; inactive; preserveAspect; endGroup; endGroup]
Our code normalizes the vertical axis to match our heuristic prediction of the number of steps remaining. At least for this example, the numerators seem to decrease much more quickly than our prediction, so the number of terms generated (15) is considerably smaller than the 70 we would expect. It is also interesting to note the large drops made by the numerator in the third, seventh, and final steps. A closer inspection reveals that these phenomena are due to cancellation between common factors of the numerators and denominators of intermediate terms: these three steps involve common factors of 63, 45, and 5739, and two other steps involve factors of three.
It is not clear to me why such large cancellations should occur.
\-
\!intro
\@/A
\@A HREF="conflict.html"
\!conflict
:[font = section; inactive; Cclosed; preserveAspect; startGroup]
Conflict Resolution Methods
:[font = text; inactive; preserveAspect]
\!intro
We next examine two methods for Egyptian fraction representation that employ the following simple idea: from a fraction x/y we can form a representation in unit fractions by making x copies of 1/y. This is not an Egyptian fraction since the unit fractions are not distinct. However we can now search for
\@I
conflicting pairs
\@/I
(two copies of the same fraction) and resolve the conflict by replacing the pair with some other fractions adding to the same value. The methods differ in the way they choose the replacement fractions. It is trivial to prove that such methods give correct representations, but it may be harder to prove that they always halt or to analyze how well they perform.
\@A NAME="pair"
;[s]
3:0,0;318,1;335,0;721,-1;
2:2,16,12,Times,0,12,0,0,0;1,16,12,Times,2,12,0,0,0;
:[font = subsection; inactive; preserveAspect; startGroup]
The Pairing Method
:[font = text; inactive; preserveAspect]
\@/A
This method uses the conflict resolution idea above. Whenever we have a conflicting pair (two copies of some fraction 1/y), we replace them either by a single fraction 2/y if y is even, or by 2/(y+1)+2/(y(y+1)) if y is odd. (Note that in all cases, the fractions simplify to have unit numerators.) The order in which this is done does not matter. Note that this process may combine pairs of fractions to form integers; e.g. this happens with sufficiently many copies of 1/7. If this happens, we allow integers to be combined to make larger integers.
This type of method is a natural fit to the pattern-matching capabilities of
\@I
Mathematica,
\@/I
so our implementation defines a function DoPairing in such a way that
\@I
Mathematica
\@/I
repeatedly transforms its argument list using the replacement defined above.
;[s]
7:0,0;642,1;653,0;701,2;710,0;734,1;745,0;828,-1;
3:4,16,12,Times,0,12,0,0,0;2,16,12,Times,2,12,0,0,0;1,18,12,Courier,0,12,0,0,0;
:[font = input; initialization; preserveAspect]
*)
DoPairing[p___,q:Rational[1,y_],q_,r___] :=
If[OddQ[y], DoPairing[p,2/(y+1), 2/(y(y+1)),r],
DoPairing[p,2/y,r]];
DoPairing[p___,q_Integer,r_Integer,s___] :=
DoPairing[p,q+r,s];
SetAttributes[DoPairing, Orderless];
EgyptPairList[l_] := Reverse[List @@ DoPairing @@ l];
EgyptPairing[Rational[x_,y_]] :=
EgyptPairList[Table[1/y, {x}]]
(*
:[font = text; inactive; preserveAspect]
Each replacement of 1/y+1/y by 2/y reduces the number of terms, initially x, by one, which can happen at most x times. Each other replacement leaves the number of terms the same but reduces the list of terms in lexicographic order; one can only perform such reductions a finite number of times. Therefore the algorithm eventually halts, with a representation having at most x terms.
Next let us determine the largest denominator that can arise. One of the fractions must be at least 1/y, and in general if the remainder after the first few terms is a/b, the next largest fraction in the representation must be at least a/xb. So if we remove the fractions from the final representation in order by size, then at each step the denominator is at most increased to its square times x, and the largest denominator is at most (xy)^(2^x). But this seems somewhat pessimistic Ñ with the heuristic assumption that equal fractions are not usually generated from different starting pairs, we get at most x replacements and in this case the largest denominator is roughly y^x (or even fewer if some denominators of intermediate terms are divisible by two).
:[font = input; preserveAspect; startGroup]
EgyptPairing[18/23]
:[font = output; output; inactive; preserveAspect; endGroup]
{1/2, 1/6, 1/12, 1/35, 1/276, 1/2415}
;[o]
1 1 1 1 1 1
{-, -, --, --, ---, ----}
2 6 12 35 276 2415
:[font = text; inactive; preserveAspect]
Perhaps more important than the direct use of this method for finding Egyptian fractions is the following fact, which shows that if we want to find a representation with few terms, it suffices to represent the given number as a sum of unit fractions without worrying about distinctness.
:[font = text; inactive; preserveAspect; endGroup]
\@B
Theorem:
\@/B
Let q be represented as a sum of t unit fractions, not necessarily distinct.
Then q has a t-term Egyptian fraction representation.
\@BLOCKQUOTE
\@B
Proof:
\@/B
apply the function EgyptPairList defined above to the given representation.
Each step leaves the sum of the fractions unchanged, and either shrinks the list by one fraction or leaves its length unchanged. The fact that this halts can be shown by the same argument given for the termination of EgyptPairing.
\@/BLOCKQUOTE
Stefan Bartels has informed me that this was first proven by Tanzo Takenouchi
\@A HREF="refs.html#Tak21"
\.[Tak21]
\@/A
. It would be of interest to bound the number of replacement steps performed by EgyptPairList and EgyptPairing.
\@A NAME="split"
;[s]
9:0,0;197,1;210,0;472,1;484,0;701,1;714,0;719,1;731,0;750,-1;
2:5,14,10,Times,0,12,0,0,0;4,14,10,Courier,0,12,0,0,0;
:[font = subsection; inactive; preserveAspect; startGroup]
The Splitting Method
:[font = text; inactive; preserveAspect]
\@/A
The next method we describe is similar to the pairing method, but less clever: we keep a list of unit fractions as before, and resolve conflicts by replacing fractions with smaller fractions adding to the same quantity. However, instead of replacing 2/y with 2/(y+1) + 2/(y(y+1)), we replace it with 1/y + 1/(y+1) + 1/(y(y+1)). In other words, when two fractions conflict, we leave one of them in place and split the other one, creating a list with one more fraction than before.
:[font = input; initialization; preserveAspect]
*)
DoSplitting[p___,q:Rational[1,y_],q_,r___] :=
DoSplitting[p,q,1/(y+1),1/(y(y+1)),r];
SetAttributes[DoSplitting, Orderless];
EgyptSplitting[Rational[x_,y_]] :=
Reverse[List @@ DoSplitting @@ Table[1/y, {x}]]
(*
:[font = text; inactive; preserveAspect]
It is not obvious that this method halts, but this has been proven by Graham and Jewett
\@A HREF="refs.html#Wag91"
\.[Wag91]
\@/A
; see also Beeckmans
\@A HREF="refs.html#Bee93"
\.[Bee93]
\@/A
. If no fraction arises in two different ways (once as 1/(y+1) and once as 1/(y(y+1)), we could analyze the algorithm on input x/y as having x-1 levels of splitting, each of which essentially doubles the number of terms in the representation. The total number of terms produced would then be O(2^x), and the largest denominator would be O(y^(2^x)). This is a best-case analysis; in practice the results will be even worse.
:[font = input; preserveAspect; startGroup]
EgyptSplitting[5/6]
:[font = output; output; inactive; preserveAspect; endGroup]
{1/6, 1/7, 1/8, 1/9, 1/10, 1/42, 1/43, 1/44, 1/45, 1/56,
1/57, 1/58, 1/72, 1/73, 1/90, 1/1806, 1/1807, 1/1808,
1/1892, 1/1893, 1/1980, 1/3192, 1/3193, 1/3306, 1/5256,
1/3263442, 1/3263443, 1/3267056, 1/3581556, 1/10192056,
1/10650056950806}
;[o]
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
{-, -, -, -, --, --, --, --, --, --, --, --, --, --, --,
6 7 8 9 10 42 43 44 45 56 57 58 72 73 90
1 1 1 1 1 1 1 1 1
----, ----, ----, ----, ----, ----, ----, ----, ----,
1806 1807 1808 1892 1893 1980 3192 3193 3306
1 1 1 1 1 1
----, -------, -------, -------, -------, --------,
5256 3263442 3263443 3267056 3581556 10192056
1
--------------}
10650056950806
:[font = text; inactive; preserveAspect; endGroup; endGroup]
\-
\!intro
\@/A
\@A HREF="binary.html"
\!binary
:[font = section; inactive; Cclosed; preserveAspect; startGroup]
Methods Based on the Binary Number System
:[font = text; inactive; preserveAspect]
\!intro
:[font = subsection; inactive; preserveAspect; startGroup]
The Binary Method
:[font = text; inactive; preserveAspect]
An Egyptian fraction representation can be formed from the binary representation of a number; e.g. 27/22 = 1.0(0111010001)*. (The star indicates that the parenthesized digits repeat in blocks of ten after these initial bits.) The initial nonrepeating part gives fractions 1/2^a, and the repeating part gives fractions 1/(2^a (2^b - 1)), where b is the length of the repetition. We must take some care that the a in the second type of fraction is nonnegative, so we modify the representation above so that there are as many nonrepeating terms as repeating terms:
27/22 = 1.001110100(0101110100)*.
A similar technique works for some other bases than binary. For instance the only digit that causes any trouble in a base 6 representation is 5, but 5/6 = 3/6+2/6 so we can still use this method with base 6. On the other hand this method does not work well with decimal notation as we can not represent 4, 7, 8, or 9 as sums of distinct divisors of 10, so numbers with those digits in their decimal representation would cause a problem for a decimal version of this method.
;[s]
9:0,0;98,1;99,0;111,2;121,0;564,1;565,0;585,2;595,0;1076,-1;
3:5,16,12,Times,0,12,0,0,0;2,16,12,Times,1,12,0,0,0;2,16,12,Times,4,12,0,0,0;
:[font = text; inactive; preserveAspect]
To implement the binary method, we first define a function to find the binary (or other base) representation of q, returned as two lists of digits. The first member of the first list is the integer part of q, the rest of the first list is the nonrepeating part of the representation, and the second list is the repeating part. It turns out to be easier to find, instead of the digits themselves, certain values mod y from which the digits can be computed. This makes it easier to detect repeating blocks of digits, since they occur exactly when the same value mod y arises twice.
:[font = input; initialization; preserveAspect]
*)
RationalDigits[q_Integer, base_] := {{q},{0}};
RationalDigits[Rational[a_,b_], base_Integer] :=
Module[{nextunit,addunit,units,
reppos,breakpt,finddigit,digitize},
nextunit = (Mod[base Last[#], b]&);
addunit = (Module[{c=nextunit[#]},
If[MemberQ[#,c],
#, Append[#,c]]]&);
units = FixedPoint[addunit, {Mod[a,b]}];
reppos = Position[units, nextunit[units]];
breakpt = reppos[[1]][[1]]-1;
finddigit = (Floor[base # / b]&);
digitize = (finddigit /@ # &);
{Prepend[digitize[Take[units,breakpt]],Floor[a/b]],
digitize[Drop[units,breakpt]]}];
(*
:[font = text; inactive; preserveAspect]
Once we have found the repeating binary representation of a fraction, it is simple to turn the nonzero digits of the representation into terms in an Egyptian fraction representation. Most of the complication in our implementation is due to the point noted earlier, that we should have at least as many nonrepeating digits as repeating digits.
:[font = input; initialization; preserveAspect]
*)
EgyptBinary[q_Integer] := {q};
EgyptBinary[q_Rational] :=
Module[{l = RationalDigits[q,2],
tpow = ({2 #1[[1]], #2}&),
invprod = (#[[2]]/#[[1]]&),
tplist,invlist,
firstlen,firstlist,firstpart,
mul,seclist,secpart,full},
tplist = (FoldList[tpow, {1,#[[1]]}, Drop[#,1]]&);
invlist = (invprod /@ tplist[#])&;
firstlen = Max[Length[l[[1]]],Length[l[[2]]]];
firstlist = Take[Apply[Join,l],firstlen];
firstpart = invlist[firstlist];
mul = 2^Length[l[[2]]]-1;
seclist = RotateRight[l[[2]], Length[l[[1]]]];
secpart = (#/mul& /@ invlist[seclist]);
full = (If[#==0,{ }, #]& /@
Join[firstpart,secpart]);
Flatten[full]];
(*
:[font = text; inactive; preserveAspect]
The correctness of this algorithm is straightforward. The fact that it halts for input q=x/y follows from the fact that the list units computed in RationalDigits is a list of distinct values modulo y, so can have length at most y. The lists of binary digits for x/y have between them at most y elements, and the padding to make the repetition start far enough along at most doubles this. At most y/2 elements on the list can correspond to binary ones, so the eventual Egyption fraction has at most y terms. All denominators are at most 2^(2y).
;[s]
5:0,0;148,2;162,0;262,1;263,0;548,-1;
3:3,16,12,Times,0,12,0,0,0;1,16,12,Times,1,12,0,0,0;1,18,12,Courier,0,12,0,0,0;
:[font = input; preserveAspect; startGroup]
EgyptBinary[27/22]
:[font = output; output; inactive; preserveAspect; endGroup]
{1, 1/8, 1/16, 1/32, 1/128, 1/2046, 1/8184, 1/16368,
1/32736, 1/130944}
;[o]
1 1 1 1 1 1 1 1 1
{1, -, --, --, ---, ----, ----, -----, -----, ------}
8 16 32 128 2046 8184 16368 32736 130944
:[font = text; inactive; preserveAspect; endGroup]
\@A NAME="binrem"
:[font = subsection; inactive; preserveAspect; startGroup]
The Binary Remainder Method
:[font = text; inactive; preserveAspect]
\@/A
Let p be a power of two such that (xp mod y) < 2p. (In particular this is satisfied if y<2p.) By dividing xp by y we find r and s satisfying x p = s y + r. Then we can represent r/p and s/p as sums of inverse powers of two; but x/y = s/p + r/(p y) so by concatenating the representation of s/p with 1/y times the representation of r/p we get a representation of x/y. The division by y ensures that no overlap occurs between the fractions from the two parts of the representation. For convenience of implementation we call EgyptBinary to find the binary representations of r/p and s/p.
;[s]
5:0,0;134,2;135,0;532,1;543,0;595,-1;
3:3,16,12,Times,0,12,0,0,0;1,18,12,Courier,0,12,0,0,0;1,16,12,Times,1,12,0,0,0;
:[font = input; initialization; preserveAspect]
*)
EBRPower[x_,y_,b_] :=
If[(x*b)~Mod~y < 2*b, b,EBRPower[x,y,2*b]];
EgyptBinRem[Rational[x_,y_]] :=
Module[{p, r, s},
p = EBRPower[x,y,2];
r = Mod[x p, y];
s = Quotient[x p, y];
Join[If[s==0,{},EgyptBinary[s/p]],
If[r==0,{},(#/y&) /@ EgyptBinary[r/p]]]]
(*
:[font = text; inactive; preserveAspect]
The method produces at most Log x + Log y terms; in practice it will typically produce half that many. Each denominator is at most y^2.
:[font = input; preserveAspect; startGroup]
EgyptBinRem[18/23]
:[font = output; output; inactive; preserveAspect; endGroup]
{1/2, 1/4, 1/46, 1/92}
;[o]
1 1 1 1
{-, -, --, --}
2 4 46 92
:[font = input; preserveAspect; startGroup]
EgyptBinRem[31/311]
:[font = output; output; inactive; preserveAspect; endGroup]
{1/16, 1/32, 1/311, 1/622, 1/1244, 1/4976, 1/9952}
;[o]
1 1 1 1 1 1 1
{--, --, ---, ---, ----, ----, ----}
16 32 311 622 1244 4976 9952
:[font = text; inactive; preserveAspect; endGroup; endGroup]
The binary remainder method appears in a paper of Stewart
\@A HREF="refs.html#Ste54"
\.[Ste54]
\@/A
, where he uses it to find representations with all denominators even. Similar methods that replace the term p=2^k by some other value have proven useful in many recent results about Egyptian fractions. Breusch
\@A HREF="refs.html#Bre54"
\.[Bre54]
\@/A
and Stewart
\@A HREF="refs.html#Ste54"
\.[Ste54]
\@/A
set p to small multiples of 3^k, to show that every odd-denominator fraction has a representation with all denominators odd. Tenenbaum and Yokota
\@A HREF="refs.html#TY90"
\.[TY90]
\@/A
use factorial values of p to find representations with (1+o(1))(Log y) / (Log Log y) terms having all denominators bounded by O(y (Log y)^2 / (Log Log y)). Vose
\@A HREF="refs.html#Vos85"
\.[Vos85]
\@/A
uses an even more complicated value of p to show that any x/y has a representation with only O(Sqrt Log[y]) terms. In the
\@A HREF="force.html#genrem"
\.generalized remainder method
\@/A
, discussed later, we show how to apply some of these ideas to find short representations.
\-
\!intro
\@/A
\@A HREF="cfrac.html"
\!cfrac
:[font = section; inactive; Cclosed; preserveAspect; startGroup]
Continued Fraction Methods
:[font = text; inactive; preserveAspect]
\!intro
\@A NAME="cfrac"
:[font = subsection; inactive; preserveAspect; startGroup]
The Continued Fraction Method
:[font = text; inactive; preserveAspect]
\@/A
One can derive a good Egyptian fraction algorithm from
\@I
continued fractions:
\@/I
the algorithm is quick, generates reasonably few terms, and uses fractions with very small denominators
\@A HREF="refs.html#Ble72"
\.[Ble72]
\@/A
.
Any real number q can be represented as a continued fraction:
;[s]
3:0,0;64,1;83,0;301,-1;
2:2,16,12,Times,0,12,0,0,0;1,16,12,Times,2,12,0,0,0;
:[font = output; output; inactive; preserveAspect]
x=a[0]+(a[1] + (a[2] + (a[3] + (a[4]...)^(-1))^(-1))^(-1))^(-1)
;[o]
1
x = a[0] + ----------------------------
1
a[1] + ---------------------
1
a[2] + --------------
1
a[3] + -------
a[4]...
:[font = text; inactive; preserveAspect]
in which all the values a[i] are integers. This terminates in a finite sequence if and only if q is rational.
:[font = text; inactive; preserveAspect]
The
\@I
convergents
\@/I
of q are formed by truncating the sequence; they are alternately above and below q, and are useful for finding good rational approximations to the original number.
(For instance the famous approximation 355/113 Å pi can be found as a convergent in this way.) Successive convergents have differences that are unit fractions. The sequence of these differences gives something like an Egyptian fraction representation of q, but unfortunately every other fraction in the sequence is negative.
If h[i]/k[i] denotes the ith convergent, we can define a sequence of
\@I
secondary convergents:
\@/I
;[s]
5:0,0;8,1;19,0;590,1;611,0;618,-1;
2:3,16,12,Times,0,12,0,0,0;2,16,12,Times,2,12,0,0,0;
:[font = output; output; inactive; preserveAspect]
(h[i-1]+j h[i])/(k[i-1]+j k[i])
;[o]
h[i - 1] + j h[i]
-----------------
k[i - 1] + j k[i]
:[font = text; inactive; preserveAspect]
As j ranges from 0 to a[n+1] the secondary convergents give an increasing sequence ranging from the (i-1)st convergent to the (i+1)st convergent
\@A HREF="refs.html@NZ80"
\.[NZ80]
\@/A
. As with the primary convergents, successive secondary convergents differ by a unit fraction. If we interleave the sequence of every other primary convergent, connected by the appropriate sequences of secondary convergents, the differences of this interleaved sequence give an Egyptian fraction representation of q.
;[s]
3:0,0;500,1;501,0;503,-1;
2:2,16,12,Times,0,12,0,0,0;1,18,12,Courier,0,12,0,0,0;
:[font = text; inactive; preserveAspect]
We first find the continued fraction representation of q=x/y.
\@I
Mathematica
\@/I
provides a package for continued fractions, but one must supply a bound on the number of terms to compute. We don't need or want such a bound, so we use our own code. In order to use this method, the continued fraction must have an odd number of terms, so if necessary we replace the last term a[i] with two terms a[i]-1 and 1.
;[s]
3:0,0;66,1;77,0;413,-1;
2:2,16,12,Times,0,12,0,0,0;1,16,12,Times,2,12,0,0,0;
:[font = input; initialization; preserveAspect]
*)
CFNextTerm[q_Integer] := 0;
CFNextTerm[q_Rational] := 1/(q-Floor[q])
ContinuedFractionList[q_] :=
Floor /@ Drop[FixedPointList[CFNextTerm, q],-2];
CFMakeOdd[l_] :=
If[OddQ[Length[l]],l,Join[Drop[l,-1],{Last[l]-1,1}]]
(*
:[font = text; inactive; preserveAspect]
We next find the primary and secondary sequences of unit fractions from these continued fraction representations.
:[font = input; initialization; preserveAspect]
*)
CFPSAux[{a_,b_},c_] := {b + a c, a};
CFPrimarySeq[l_] :=
Transpose[Drop[FoldList[CFPSAux,{0,1},l],1]][[1]];
CFSecondarySeq[l_] :=
If[Length[l] < 3, l,
Table[l[[1]] + i l[[2]],
{i, 0, (l[[3]]-l[[1]])/l[[2]]-1}] ~Join~
CFSecondarySeq[Drop[l,2]]]
(*
:[font = text; inactive; preserveAspect]
As described above, our final representation is formed by hooking together secondary sequences. We first separate out the integer part of the input, which we leave as is. The remaining fractions are formed by multiplying pairs of values in the secondary sequence.
:[font = input; initialization; preserveAspect]
*)
EgyptContinuedFraction[q_] :=
CFSecondarySeq[CFPrimarySeq[CFMakeOdd[
ContinuedFractionList[q]]]] //
1/(Drop[#,1] Drop[#,-1])& //
If[Floor[q]==0, #, Prepend[#, Floor[q]]]&
(*
:[font = text; inactive; preserveAspect]
Termination of the algorithm follows from the termination of the continued fraction representation algorithm, which is essentially the same as Euclid's algorithm for integer GCD's. It is clear from the construction of the secondary sequence, and from the fact that the final result has denominators that are products of pairs of numbers in the secondary sequence, that all fractions are distinct. The fact that the sum of the fractions is the original input number
is a straightforward but tedious exercise in algebraic manipulation. The number of terms in the Egyptian fraction representation of x/y is the sum of the odd terms after the first in the continued fraction list, which is at most x. Each fraction is a difference between two secondary convergents with denominator at most y, so each fraction has denominator at most y^2.
:[font = input; preserveAspect; startGroup]
EgyptContinuedFraction[18/23]
:[font = output; output; inactive; preserveAspect; endGroup]
{1/2, 1/6, 1/12, 1/36, 1/207}
;[o]
1 1 1 1 1
{-, -, --, --, ---}
2 6 12 36 207
:[font = text; inactive; preserveAspect; endGroup]
\@A NAME="grouped"
:[font = subsection; inactive; preserveAspect; startGroup]
The Grouped Continued Fraction Method
:[font = text; inactive; preserveAspect]
\@/A
The worst case for the continued fraction method above occurs when the continued fraction representation has only three terms producing a long secondary sequence. In this case the Egyptian fraction representation will involve long sequences of fractions of the form
1/(a+b i)(a+b(i+1)). If we add k consecutive values in such a sequence, we get
k/(a+b i)(a + b(i + k)); it may happen that this can be simplified to a unit fraction again. By performing several simplifications, we both reduce the number of terms in the overall representation and also reduce some denominators. For instance, the continued fraction method for 7/15 gives
:[font = output; output; inactive; preserveAspect]
{1/3, 1/15, 1/35, 1/63, 1/99, 1/143, 1/195}
;[o]
1 1 1 1 1 1 1
{-, --, --, --, --, ---, ---}
3 15 35 63 99 143 195
:[font = text; inactive; preserveAspect]
But 1/15 + 1/35 + 1/63 = 1/9, and 1/99 + 1/143 + 1/195 = 1/45, so we can replace these triples and find the shorter representation
:[font = output; output; inactive; preserveAspect]
{1/3,1/9,1/45}
;[o]
1 1 1
{-, -, --}
3 9 45
:[font = text; inactive; preserveAspect]
This phenomenon is not unusual, and Bleicher
\@A HREF="refs.html#Ble72"
\.[Ble72]
\@/A
showed how to take advantage of it to dramatically reduce the number of terms produced by the continued fraction method. Some care is required: if in the above list we instead group the last five terms, we get
:[font = output; output; inactive; preserveAspect]
{1/3,1/15,1/15}
;[o]
1 1 1
{-, --, --}
3 15 15
:[font = text; inactive; preserveAspect]
which is not an Egyptian fraction representation.
:[font = text; inactive; preserveAspect]
Our implementation finds all shortest representations rather than a single representation, so if they had distinct fractions we would return both representations above. We partition the secondary sequence into blocks of arithmetic progressions and find groupings separately within each progression; this is safe as the sum of all fractions from one progression is smaller than half of any fraction in a previous progression. Within a progression, we determine which groups of terms can be combined to form a unit fraction, and represent each group as an edge in a graph, labelled with the corresponding unit fraction. For the example above, the graph has eight vertices and ten edges, as follows:
:[font = postscript; PostScript; formatAsPostScript; output; inactive; preserveAspect; pictureLeft = 34; pictureWidth = 337; pictureHeight = 102]
%!
%%Creator: Mathematica
%%AspectRatio: .30488
MathPictureStart
%% Graphics
/Courier findfont 10 scalefont setfont
% Scaling calculations
0.121951 0.121951 0.182927 0.121951 [
[ 0 0 0 0 ]
[ 1 .30488 0 0 ]
] MathScale
% Start of Graphics
1 setlinecap
1 setlinejoin
newpath
[ ] 0 setdash
0 g
p
P
0 0 m
1 0 L
1 .30488 L
0 .30488 L
closepath
clip
newpath
p
p
.004 w
.12195 .18293 m
.12195 .18293 .0122 0 365.73 arc
F
.2439 .18293 m
.2439 .18293 .0122 0 365.73 arc
F
.36585 .18293 m
.36585 .18293 .0122 0 365.73 arc
F
.4878 .18293 m
.4878 .18293 .0122 0 365.73 arc
F
.60976 .18293 m
.60976 .18293 .0122 0 365.73 arc
F
.73171 .18293 m
.73171 .18293 .0122 0 365.73 arc
F
.85366 .18293 m
.85366 .18293 .0122 0 365.73 arc
F
.97561 .18293 m
.97561 .18293 .0122 0 365.73 arc
F
P
p
.004 w
.12195 .18293 m
.2439 .18293 L
s
.2439 .18293 m
.36585 .18293 L
s
.36585 .18293 m
.4878 .18293 L
s
.4878 .18293 m
.60976 .18293 L
s
.60976 .18293 m
.73171 .18293 L
s
.73171 .18293 m
.85366 .18293 L
s
.85366 .18293 m
.97561 .18293 L
s
P
p
.004 w
.2439 .18293 m
.30488 .30488 L
.54878 .30488 L
.60976 .18293 L
s
.60976 .18293 m
.67073 .30488 L
.91463 .30488 L
.97561 .18293 L
s
.36585 .18293 m
.42683 .06098 L
.91463 .06098 L
.97561 .18293 L
s
P
p
[(1/3)] .18293 .15854 0 0 Mshowa
[(1/15)] .30488 .15854 0 0 Mshowa
[(1/35)] .42683 .15854 0 0 Mshowa
[(1/63)] .54878 .15854 0 0 Mshowa
[(1/99)] .67073 .15854 0 0 Mshowa
[(1/143)] .79268 .15854 0 0 Mshowa
[(1/195)] .91463 .15854 0 0 Mshowa
[(1/9)] .42683 .28049 0 0 Mshowa
[(1/45)] .79268 .28049 0 0 Mshowa
[(1/15)] .67073 .03659 0 0 Mshowa
P
P
% End of Graphics
MathPictureEnd
:[font = text; inactive; preserveAspect]
Each edge is directed from left to right. The horizontal edges represent the original terms produced by the continued fraction method, while the longer edges represent the groupings that result in unit fractions. Our task then becomes one of finding the shortest path through this graph, with the restriction that we cannot use two edges with the same label.
Unfortunately finding paths without repeated labels is NP-complete, so an efficient algorithm for this subproblem is unlikely to exist. Fortunately most of the time our graphs have few repeated labels and the problem is not as hard as its worst case. We use the following heuristic: for increasing values of k, find all paths of k or fewer edges, and filter out the paths with repeated labels; if not all paths are filtered out, return the remaining list of paths. The theoretically fastest algorithm for listing all short paths takes constant time per path, after preprocessing time proportional to the time to find a single shortest path
\@A HREF="refs.html#Epp94"
\.[Epp94]
\@/A
, however for ease of implementation we use a simpler method invented by Byers and Waterman
\@A HREF="BW84"
\.[BW84]
\@/A
. (The motivation of both papers was not Egyptian fractions, but rather comparison of DNA and protein sequences; this also turns out to be equivalent to a certain shortest path problem.)
:[font = text; inactive; preserveAspect]
First we include code to make an adjacency matrix for a graph, containing in each entry either the fraction corresponding to an edge in the graph, or the empty set if no such edge exists (i.e. if the corresponding sum of terms does not reduce to a unit fraction). The input to this routine is the secondary sequence of the continued fraction.
:[font = input; initialization; preserveAspect]
*)
ECFMakeGraph[l_] :=
Table[If[ib,{},(Prepend[#,g[[i,j]]]&) /@
ECFBoundedPaths[g,b-#,j,l,v]]&),
{j,i+1,l}]]
(*
:[font = text; inactive; preserveAspect]
We next include code for removing from the list those paths that contain a duplicated fraction.
It is not clear that the paths will have the fractions listed in sorted order, so we sort them first.
:[font = input; initialization; preserveAspect]
*)
ECFContainsDupl[{___,q_,q_,___}] := True;
ECFContainsDupl[l_] := False;
ECFFilterDuplSub[x_] :=
If[ECFContainsDupl[x],{},{x}];
(*
:[font = input; initialization; preserveAspect]
*)
ECFFilterDupls[l_] :=
Join @@ (ECFFilterDuplSub[Reverse[Sort[#]]]&) /@ l;
ECFShortFilter[g_] := ECFShortFilter[g,ECFPathLengths[g],0];
ECFShortFilter[g_,v_,b_] :=
ECFFilterDupls[ECFBoundedPaths[g,b,1,Length[g],v]] //
(If[#==={},ECFShortFilter[g,v,b+1],#]&);
(*
:[font = text; inactive; preserveAspect]
The next function applies all of the above steps for three-term continued fractions. The final algorithm applies this to several three-term subsequences of the whole continued fraction.
:[font = input; initialization; preserveAspect]
*)
ECFArithSeq[a_,b_,c_]:=ECFShortFilter[
ECFMakeGraph[CFSecondarySeq[{a,b,c}]]]
(*
:[font = text; inactive; preserveAspect]
The next function takes two lists of lists, and forms all pairwise concatenations of one item from the first list and one from the second. The obvious approach of using Outer[Join,...] doesn't work since Outer interprets lists of lists as tensors, so we use an alternate method based on Distribute.
;[s]
8:0,0;170,2;185,1;186,0;205,2;210,0;288,2;298,0;300,-1;
3:4,16,12,Times,0,12,0,0,0;1,16,12,Times,1,12,0,0,0;3,18,12,Courier,0,12,0,0,0;
:[font = input; initialization; preserveAspect]
*)
OuterJoin[ll_,mm_] :=
Distribute[{ll,mm},List,List,List,Join];
(*
:[font = text; inactive; preserveAspect]
We are finally ready to define the overall modified continued fraction method, which breaks the primary sequence into subsequences and calls ECFArithSeq on each one.
;[s]
3:0,0;141,1;152,0;166,-1;
2:2,16,12,Times,0,12,0,0,0;1,18,12,Courier,0,12,0,0,0;
:[font = input; initialization; preserveAspect]
*)
ECFSecondaryPaths[l_] :=
If[Length[l]<3,{{}},
OuterJoin[ECFArithSeq[l[[1]],l[[2]],l[[3]]],
ECFSecondaryPaths[Drop[l,2]]]]
(*
:[font = input; initialization; preserveAspect]
*)
EgyptGroupedCF[q_] :=
ECFSecondaryPaths[CFPrimarySeq[
CFMakeOdd[ContinuedFractionList[q]]]]
(*
:[font = text; inactive; preserveAspect]
Every step involves a fixed number of nested loops with indices bounded by the length of the secondary sequence, so (with the possible exception of finding a short repetition-free path) the overall time is polynomial in the numerator of the original rational number given as input.
It is not hard to see that the algorithm produces sequences of fractions formed by grouping the results of the continued fraction method, so the sum of the sequence is correct. It remains to verify that no fraction is duplicated. This is checked explicitly within each subsequence, and the entire sum of any subsequence is less than half any single fraction in previous subsequences, so no two separate subsequences can produce duplications.
As in the continued fraction method, the largest denominator in the representation of x/y is O[y^2]. The number of terms is still O[x] but it can also be analyzed in terms of y.
Bleicher [Ble72] shows that by choosing a prime p with gcd(a,p)=1 and p=O(log a),
and using groups with sizes equal to powers of p, one can find a representation with
O(p Log[b]/Log[p]) = O(Log[x]Log[y]/Log Log[y]) terms.
Since the actual representation is chosen to have minimum length, it can be no longer than this.
It remains unclear whether the implementation above really takes polynomial time, or whether there can be sufficiently many repeated labels that the algorithm for listing short paths has to list a large number of paths and slows down to exponential. However in practice this method seems to work well. (Bleicher's method of grouping can apparently be done in polynomial time.)
:[font = input; preserveAspect; startGroup]
EgyptGroupedCF[31/311]
:[font = output; output; inactive; preserveAspect; endGroup]
{{1/11, 1/121, 1/2541, 1/9933, 1/93611}}
;[o]
1 1 1 1 1
{{--, ---, ----, ----, -----}}
11 121 2541 9933 93611
:[font = text; inactive; preserveAspect; endGroup]
The graph constructed for 31/311 is too complicated to depict here. It has two paths of length five; however one of the paths is eliminated because it has two copies of the label 1/231.
:[font = subsection; inactive; preserveAspect; startGroup]
A Hybrid Pairing / Continued Fraction Method
:[font = text; inactive; preserveAspect]
We can use potentially even fewer terms than the grouped continued fraction method, at the expense of possibly increasing the maximum denominator in the representation. We simply find shortest paths in the same graph constructed by that method, ignoring the possibility of repeated labels, and then make the unit fractions in the resulting representation distinct by applying
\@A HREF="conflict.html#pair"
\.EgyptPairList
\@/A
.
;[s]
3:0,0;409,1;422,0;430,-1;
2:2,16,12,Times,0,12,0,0,0;1,18,12,Courier,0,12,0,0,0;
:[font = input; initialization; preserveAspect]
*)
EHArithSeq[a_,b_,c_] := ECFBoundedPaths[
ECFMakeGraph[CFSecondarySeq[{a,b,c}]],0]
EHSecondaryPaths[l_] :=
If[Length[l]<3,{{}},
OuterJoin[EHArithSeq[l[[1]],l[[2]],l[[3]]],
EHSecondaryPaths[Drop[l,2]]]]
EgyptHybrid[q_] := EgyptPairList /@
EHSecondaryPaths[CFPrimarySeq[
CFMakeOdd[ContinuedFractionList[q]]]];
(*
:[font = text; inactive; preserveAspect]
This method uses O(Log[x]Log[y]/Log Log[y]) terms to represent any number x/y. In the following example, we see representations corresponding to both shortest paths in the graph constructed for 31/311.
:[font = input; preserveAspect; startGroup]
EgyptHybrid[31/311]
:[font = output; output; inactive; preserveAspect; endGroup]
{{1/11, 1/116, 1/9933, 1/26796, 1/93611},
{1/11, 1/121, 1/2541, 1/9933, 1/93611}}
;[o]
1 1 1 1 1
{{--, ---, ----, -----, -----},
11 116 9933 26796 93611
1 1 1 1 1
{--, ---, ----, ----, -----}}
11 121 2541 9933 93611
:[font = text; inactive; preserveAspect; endGroup; endGroup]
\-
\!intro
\@/A
\@A HREF="greed.html"
\!greed
:[font = section; inactive; Cclosed; preserveAspect; startGroup]
Reverse Greedy Methods
:[font = text; inactive; preserveAspect]
\!intro
:[font = subsection; inactive; preserveAspect; startGroup]
The Basic Reverse Greedy Method
:[font = text; inactive; preserveAspect]
The idea behind this algorithm (due to K.S. Brown in an email forwarded to me by Milo Gardner) is to generate the Egyptian fraction in "reverse" order, from larger denominators to smaller. At each step, we expand our fraction x/y = x'/y' + 1/u in an attempt to make the new denominator y' as small as possible. We always know y' < y is possible from the continued fraction method. In general this method reduces the denominator faster than continued fractions and hopefully produces fewer terms.
The basic idea is to first choose d=xy'-x'y, then solve for y' and x'. Some analysis simplifies the search for d. First, suppose some prime p divides d and doesn't divide y. Then since u=yy'/d, we know that p divides y'. Further, since x'=(xy'-d)/y, p divides x' and x'/y' is not in least terms. We can ignore such solutions. Similarly, if p divides y exactly c times, and p divides d 2c+k times, we know that p^(c+k) divides y' and p^k divides x'. So it is always safe to assume d is a divisor of y^2. Conversely, every divisor of y^2 leads to a unit fraction 1/u, but for some of them x'/y' is negative or y' is zero. We filter those divisors to include only those d leading to a valid fraction x'/y'.
:[font = input; initialization; preserveAspect]
*)
ERGChoices[x_,y_] :=
Select[Divisors[y*y],
((# * PowerMod[x,-1,y]) ~Mod~ y) * x > # &];
EgyptReverseGreedy[q_Integer] := If[q==0,{},{q}];
EgyptReverseGreedy[Rational[x_,y_]] :=
If[x==1,{x/y},
EgyptPairList[Append[EgyptReverseGreedy[x/y-#],#]]& @
((# * x) ~Mod~ y / (# * y) & @
Min[(ERGChoices[x,y]*PowerMod[x,-1,y]) ~Mod~ y])];
(*
:[font = text; inactive; preserveAspect]
\@A HREF="conflict.html#pair"
\.EgyptPairList
\@/A
is needed to avoid duplicate fractions; for instance otherwise this method would produce 1/11+1/231+1/231 for 23/231. Because of this, it is hard to bound the denominators in the representations this method produces. The number of terms is clearly O[y]; it produces fewer terms in practice but it is unclear whether one can prove bounds on the number of terms that are even as good as the continued fraction method.
:[font = input; preserveAspect; startGroup]
EgyptReverseGreedy[31/311]
:[font = output; output; inactive; preserveAspect; endGroup; endGroup]
{1/16, 1/28, 1/688, 1/93611}
;[o]
1 1 1 1
{--, --, ---, -----}
16 28 688 93611
:[font = subsection; inactive; preserveAspect; startGroup]
Small-Unit Reverse Greedy
:[font = text; inactive; preserveAspect]
One simple variation on the reverse greedy strategy is to choose the unit fraction with smallest denominator to remove at each step, among those unit fractions reducing the denominator of the remainder.
:[font = input; initialization; preserveAspect]
*)
ERGFrac[x_,y_,d_] :=
d/((d*PowerMod[x,-1,y]) ~Mod~ y)
EgyptSmallUnit[q_Integer] := If[q==0,{},{q}];
EgyptSmallUnit[Rational[x_,y_]] :=
If[x==1,{x/y},
EgyptPairList[Append[EgyptSmallUnit[(x-#)/y],#/y]]& @
Max[ERGFrac[x,y,#]& /@ ERGChoices[x,y]]];
(*
:[font = text; inactive; preserveAspect]
This leads to representations with smaller denominators, but also may reduce the number of terms.
:[font = input; preserveAspect; startGroup]
EgyptReverseGreedy[10/143]
:[font = output; output; inactive; preserveAspect; endGroup]
{1/15, 1/435, 1/1247, 1/6149}
;[o]
1 1 1 1
{--, ---, ----, ----}
15 435 1247 6149
:[font = input; preserveAspect; startGroup]
EgyptSmallUnit[10/143]
:[font = output; output; inactive; preserveAspect; endGroup]
{1/36, 1/60, 1/65, 1/99}
;[o]
1 1 1 1
{--, --, --, --}
36 60 65 99
:[font = text; inactive; preserveAspect; endGroup]
\@A NAME="smallden"
:[font = subsection; inactive; preserveAspect; startGroup]
Small Denominator Reverse Greedy
:[font = text; inactive; preserveAspect]
\@/A
One drawback of the small unit method (as a way of generating fractions with small denominators) is that it can sometimes choose a unit fraction very close to x/y, leaving a relatively small remainder. It seems more appropriate in this case to balance the two denominators of u and y'.
:[font = input; initialization; preserveAspect]
*)
ArgMin[l_,f_] := (Position[#,Min[#]]& @ (f /@ l))[[1,1]];
ERGMaxDen[x_,y_,l_] :=
l[[ ArgMin[l,Max[Denominator[#/y],
Denominator[(x-#)/y]]&] ]];
EgyptSmallDen[q_Integer] := If[q==0,{},{q}];
EgyptSmallDen[Rational[x_,y_]] :=
If[x==1,{x/y},
EgyptPairList[Append[EgyptSmallDen[(x-#)/y],#/y]]& @
ERGMaxDen[x,y,ERGFrac[x,y,#]& /@ ERGChoices[x,y]]];
(*
:[font = text; inactive; preserveAspect]
This can often do a good job of keeping all denominators small.
:[font = input; preserveAspect; startGroup]
EgyptSmallUnit[17/180]
:[font = output; output; inactive; preserveAspect; endGroup]
{1/12, 1/90}
;[o]
1 1
{--, --}
12 90
:[font = input; preserveAspect; startGroup]
EgyptSmallDen[17/180]
:[font = output; output; inactive; preserveAspect; endGroup]
{1/15, 1/36}
;[o]
1 1
{--, --}
15 36
:[font = text; inactive; preserveAspect; endGroup]
\@A NAME="smallnum"
:[font = subsection; inactive; preserveAspect; startGroup]
Small Numerator Reverse Greedy
:[font = text; inactive; preserveAspect]
\@/A
This idea combines the reverse greedy method (which reduces denominators) with the standard greedy method (which reduces numerators). The idea is simply to choose, among all the choices of x/y=x'/y'+1/u, the one with the smallest value of x'. To break ties we choose the smallest value of u since that seems to lead to better representations.
:[font = input; initialization; preserveAspect]
*)
ERGGoodNum[x_,y_,l_] :=
l[[ ArgMin[l,Numerator[(x-#)/y] - #/y &] ]];
EgyptSmallNum[q_Integer] := If[q==0,{},{q}];
EgyptSmallNum[Rational[x_,y_]] :=
If[x==1,{x/y},
EgyptPairList[Append[EgyptSmallNum[(x-#)/y],#/y]]& @
ERGGoodNum[x,y,ERGFrac[x,y,#]& /@ ERGChoices[x,y]]];
(*
:[font = input; preserveAspect; startGroup]
EgyptSmallNum[10/143]
:[font = output; output; inactive; preserveAspect; endGroup; endGroup]
{1/22, 1/65, 1/110}
;[o]
1 1 1
{--, --, ---}
22 65 110
:[font = subsection; inactive; preserveAspect; startGroup]
Big Divisor Reverse Greedy
:[font = text; inactive; preserveAspect]
Another variant of the reverse greedy method simply chooses the largest value in ERGChoices. Heuristically this is likely to lead to much cancellation and a unit fraction with small denominator.
:[font = input; initialization; preserveAspect]
*)
EgyptBigDiv[q_Integer] := If[q==0,{},{q}];
EgyptBigDiv[Rational[x_,y_]] :=
If[x==1,{x/y},
EgyptPairList[Append[EgyptSmallNum[(x-#)/y],#/y]]& @
ERGFrac[x,y,Last[ERGChoices[x,y]]]];
(*
:[font = text; inactive; preserveAspect]
This is often the same as EgyptSmallUnit, but occasionally differs, and even sometimes results in smaller denominators.
:[font = input; preserveAspect; startGroup]
EgyptReverseGreedy[23/231]
:[font = output; output; inactive; preserveAspect; endGroup]
{1/11, 1/116, 1/26796}
;[o]
1 1 1
{--, ---, -----}
11 116 26796
:[font = input; preserveAspect; startGroup]
EgyptSmallUnit[23/231]
:[font = output; output; inactive; preserveAspect; endGroup]
{1/21, 1/40, 1/56, 1/110}
;[o]
1 1 1 1
{--, --, --, ---}
21 40 56 110
:[font = input; preserveAspect; startGroup]
EgyptSmallNum[23/231]
:[font = output; output; inactive; preserveAspect; endGroup]
{1/15, 1/35, 1/231}
;[o]
1 1 1
{--, --, ---}
15 35 231
:[font = input; preserveAspect; startGroup]
EgyptSmallDen[23/231]
:[font = output; output; inactive; preserveAspect; endGroup]
{1/22, 1/33, 1/42}
;[o]
1 1 1
{--, --, --}
22 33 42
:[font = input; preserveAspect; startGroup]
EgyptBigDiv[23/231]
:[font = output; output; inactive; preserveAspect; endGroup]
{1/22, 1/33, 1/42}
;[o]
1 1 1
{--, --, --}
22 33 42
:[font = text; inactive; preserveAspect; endGroup; endGroup]
\-
\!intro
\@/A
\@A HREF="force.html"
\!force
:[font = section; inactive; Cclosed; preserveAspect; startGroup]
Brute Force Methods
:[font = text; inactive; preserveAspect]
\!intro
\@A NAME="genrem"
:[font = subsection; inactive; preserveAspect; startGroup]
The Generalized Remainder Method
:[font = text; inactive; preserveAspect]
\@/A
This is closely related to the
\@A HREF="binary.html#binrem"
\.binary remainder method
\@/A
, and to similar methods cited in the discussion there. We find a number p with many divisors, compute xp=qy+r, represent q and r as sums of divisors of p, and use these representations to expand x/y=q/p + r/yp.
Here we assume a value p given by the user, and use a close-to-brute-force dynamic programming technique to represent numbers as sums of divisors of p. We then use
\@A HREF="conflict.html#pair"
\.EgyptPairList
\@/A
because our technique does not necessarily avoid duplicate fractions (and because the chief goal here is to minimize the number of terms in the expansion).
:[font = input; initialization; preserveAspect]
*)
SumDivisors[n_,p_] :=
DivisorSums[n,p,
Table[If[p ~Mod~ i == 0, {{i}}, {}],{i,n}]];
DivisorSums[n_,p_,t_] :=
If [t[[n]] != {}, t[[n]],
DivisorSums[n,p,ExtendDivTable[t,p,n]]];
ExtendTableEntry[e_,d_] :=
Append[#,d]& /@
Select[e,Last[#] <= d&];
ExtendDivTable[t_,p_,n_] :=
Table[If[t[[i]] != {}, t[[i]],
Join @@
( ExtendTableEntry[t[[i-#]],#]& /@
Select[Divisors[p], #*= 1/q. However if the terms are in sorted order u > v > ..., and there are a total of k terms, then the largest term 1/u must be at least q/k. So this gives upper and lower bounds for u; we simply try all possibilities and continue recursively. (In the recursive call we have a further bound on the fractions from the assumption that they are generated in sorted order.) Incidentally, since we have a k-level recursion, and each call generates a finite number of recursive calls, the whole call tree must be finite and there are only finitely many k-term representations of q.
:[font = text; inactive; preserveAspect]
To make this method less slow (and perhaps even more important, to make it use less memory), we speed up the case for k=2. We wish to solve the equation x/y=1/a + 1/b; this can be rewritten (ax-y)(bx-y)=y^2, and letting the two factors of y^2 be r and s we can solve a=(r+y)/x, b=(s+y)/x. We try all factors r of y^2 for which r= minden*x & ]
(*
:[font = input; initialization; preserveAspect]
*)
EgyptShort[q_,k_] := EShortRecur[q,k,1,{}];
EShortRecur[q_,k_,b_,a_] :=
If [q == 0, {a},
If [k <= 2, EgyptTwoTerm[q, b, a],
Join @@
Table[EShortRecur[q-1/i,k-1,i+1,Append[a,1/i]],
{i,Max[b,Ceiling[1/q]],Floor[k/q]}]]];
(*
:[font = text; inactive; preserveAspect]
This method is quite slow, taking four minutes on my Powerbook 540c to solve the following example.
\@A HREF="efrac.c"
\.A C++ version
\@/A
that I also coded up performs much more quickly ("solving" the same problem in less than a minute) but because it is less careful than Mathematica about arithmetic overflow it gets the wrong answers.
;[s]
3:0,0;276,1;287,0;341,-1;
2:2,14,10,Times,0,12,0,0,0;1,14,10,Times,2,12,0,0,0;
:[font = input; preserveAspect; startGroup]
EgyptShort[31/311,4]
:[font = output; output; inactive; preserveAspect; endGroup]
{{1/11, 1/115, 1/13570, 1/46422970},
{1/11, 1/115, 1/13662, 1/1931310},
{1/11, 1/115, 1/13684, 1/1573660},
{1/11, 1/116, 1/6728, 1/23016488},
{1/11, 1/116, 1/6842, 1/396836},
{1/11, 1/118, 1/3421, 1/403678},
{1/11, 1/119, 1/2772, 1/190332},
{1/12, 1/62, 1/4628, 1/66927822},
{1/12, 1/62, 1/4650, 1/964100},
{1/12, 1/62, 1/4665, 1/578460},
{1/12, 1/62, 1/4743, 1/190332},
{1/12, 1/63, 1/2124, 1/770658},
{1/12, 1/63, 1/2142, 1/190332},
{1/12, 1/63, 1/2177, 1/78372},
{1/12, 1/63, 1/2799, 1/8708},
{1/12, 1/64, 1/1392, 1/577216},
{1/12, 1/68, 1/612, 1/190332},
{1/12, 1/68, 1/622, 1/31722},
{1/12, 1/69, 1/540, 1/1931310},
{1/12, 1/72, 1/408, 1/190332},
{1/12, 1/78, 1/284, 1/287053},
{1/12, 1/86, 1/212, 1/4252614},
{1/12, 1/102, 1/153, 1/190332},
{1/12, 1/119, 1/126, 1/190332},
{1/13, 1/44, 1/35580, 1/791174670},
{1/13, 1/44, 1/35581, 1/486890404},
{1/13, 1/44, 1/35596, 1/71957314},
{1/13, 1/44, 1/35607, 1/44295108},
{1/13, 1/44, 1/35620, 1/30464005},
{1/13, 1/44, 1/35646, 1/18760764},
{1/13, 1/44, 1/35772, 1/6573918},
{1/13, 1/44, 1/35893, 1/4059172},
{1/13, 1/44, 1/36036, 1/2801799},
{1/13, 1/44, 1/36076, 1/2579434},
{1/13, 1/44, 1/36322, 1/1737868},
{1/13, 1/44, 1/36387, 1/1601028},
{1/13, 1/44, 1/40612, 1/287053},
{1/13, 1/44, 1/41052, 1/266838},
{1/13, 1/44, 1/43758, 1/190332},
{1/13, 1/44, 1/44473, 1/177892},
{1/13, 1/44, 1/48516, 1/133419},
{1/13, 1/44, 1/56602, 1/95788},
{1/13, 1/52, 1/284, 1/287053},
{1/14, 1/36, 1/2124, 1/770658},
{1/14, 1/36, 1/2142, 1/190332},
{1/14, 1/36, 1/2177, 1/78372},
{1/14, 1/36, 1/2799, 1/8708},
{1/15, 1/54, 1/69, 1/1931310},
{1/16, 1/27, 1/7072, 1/59383584},
{1/16, 1/27, 1/7074, 1/17600112},
{1/16, 1/27, 1/7344, 1/190332},
{1/16, 1/27, 1/7464, 1/134352},
{1/16, 1/27, 1/8397, 1/44784},
{1/16, 1/28, 1/683, 1/23790256},
{1/16, 1/28, 1/688, 1/93611},
{1/18, 1/23, 1/1555, 1/643770},
{1/18, 1/23, 1/1564, 1/190332},
{1/18, 1/24, 1/408, 1/190332},
{1/18, 1/28, 1/119, 1/190332},
{1/18, 1/34, 1/68, 1/190332}}
;[o]
1 1 1 1 1 1 1 1
{{--, ---, -----, --------}, {--, ---, -----, -------},
11 115 13570 46422970 11 115 13662 1931310
1 1 1 1 1 1 1 1
{--, ---, -----, -------}, {--, ---, ----, --------},
11 115 13684 1573660 11 116 6728 23016488
1 1 1 1 1 1 1 1
{--, ---, ----, ------}, {--, ---, ----, ------},
11 116 6842 396836 11 118 3421 403678
1 1 1 1 1 1 1 1
{--, ---, ----, ------}, {--, --, ----, --------},
11 119 2772 190332 12 62 4628 66927822
1 1 1 1 1 1 1 1
{--, --, ----, ------}, {--, --, ----, ------},
12 62 4650 964100 12 62 4665 578460
1 1 1 1 1 1 1 1
{--, --, ----, ------}, {--, --, ----, ------},
12 62 4743 190332 12 63 2124 770658
1 1 1 1 1 1 1 1
{--, --, ----, ------}, {--, --, ----, -----},
12 63 2142 190332 12 63 2177 78372
1 1 1 1 1 1 1 1
{--, --, ----, ----}, {--, --, ----, ------},
12 63 2799 8708 12 64 1392 577216
1 1 1 1 1 1 1 1
{--, --, ---, ------}, {--, --, ---, -----},
12 68 612 190332 12 68 622 31722
1 1 1 1 1 1 1 1
{--, --, ---, -------}, {--, --, ---, ------},
12 69 540 1931310 12 72 408 190332
1 1 1 1 1 1 1 1
{--, --, ---, ------}, {--, --, ---, -------},
12 78 284 287053 12 86 212 4252614
1 1 1 1 1 1 1 1
{--, ---, ---, ------}, {--, ---, ---, ------},
12 102 153 190332 12 119 126 190332
1 1 1 1 1 1 1 1
{--, --, -----, ---------}, {--, --, -----, ---------},
13 44 35580 791174670 13 44 35581 486890404
1 1 1 1 1 1 1 1
{--, --, -----, --------}, {--, --, -----, --------},
13 44 35596 71957314 13 44 35607 44295108
1 1 1 1 1 1 1 1
{--, --, -----, --------}, {--, --, -----, --------},
13 44 35620 30464005 13 44 35646 18760764
1 1 1 1 1 1 1 1
{--, --, -----, -------}, {--, --, -----, -------},
13 44 35772 6573918 13 44 35893 4059172
1 1 1 1 1 1 1 1
{--, --, -----, -------}, {--, --, -----, -------},
13 44 36036 2801799 13 44 36076 2579434
1 1 1 1 1 1 1 1
{--, --, -----, -------}, {--, --, -----, -------},
13 44 36322 1737868 13 44 36387 1601028
1 1 1 1 1 1 1 1
{--, --, -----, ------}, {--, --, -----, ------},
13 44 40612 287053 13 44 41052 266838
1 1 1 1 1 1 1 1
{--, --, -----, ------}, {--, --, -----, ------},
13 44 43758 190332 13 44 44473 177892
1 1 1 1 1 1 1 1
{--, --, -----, ------}, {--, --, -----, -----},
13 44 48516 133419 13 44 56602 95788
1 1 1 1 1 1 1 1
{--, --, ---, ------}, {--, --, ----, ------},
13 52 284 287053 14 36 2124 770658
1 1 1 1 1 1 1 1
{--, --, ----, ------}, {--, --, ----, -----},
14 36 2142 190332 14 36 2177 78372
1 1 1 1 1 1 1 1
{--, --, ----, ----}, {--, --, --, -------},
14 36 2799 8708 15 54 69 1931310
1 1 1 1 1 1 1 1
{--, --, ----, --------}, {--, --, ----, --------},
16 27 7072 59383584 16 27 7074 17600112
1 1 1 1 1 1 1 1
{--, --, ----, ------}, {--, --, ----, ------},
16 27 7344 190332 16 27 7464 134352
1 1 1 1 1 1 1 1
{--, --, ----, -----}, {--, --, ---, --------},
16 27 8397 44784 16 28 683 23790256
1 1 1 1 1 1 1 1
{--, --, ---, -----}, {--, --, ----, ------},
16 28 688 93611 18 23 1555 643770
1 1 1 1 1 1 1 1
{--, --, ----, ------}, {--, --, ---, ------},
18 23 1564 190332 18 24 408 190332
1 1 1 1 1 1 1 1
{--, --, ---, ------}, {--, --, --, ------}}
18 28 119 190332 18 34 68 190332
:[font = text; inactive; preserveAspect]
Many of these expansions could have also been obtained by EgyptRemainder, using the following numbers as bases:
:[font = input; preserveAspect; startGroup]
Union[((LCM@@ Denominator/@ #) / 311)& /@ %]
:[font = output; output; inactive; preserveAspect; endGroup]
{204, 252, 432, 572, 612, 1224, 1276, 1298, 1716, 1860,
2070, 3692, 4004, 4284, 4816, 5060, 5148, 5568, 6210,
7344, 9300, 11076, 12420, 14076, 14868, 16588, 18972,
27348, 36036, 40612, 47124, 56592, 68310, 72644, 74008,
76496, 87516, 142428, 143572, 149270, 190944, 391820,
430404, 462748, 465036, 784212, 1565564, 5087940}
;[o]
{204, 252, 432, 572, 612, 1224, 1276, 1298, 1716, 1860,
2070, 3692, 4004, 4284, 4816, 5060, 5148, 5568, 6210,
7344, 9300, 11076, 12420, 14076, 14868, 16588, 18972,
27348, 36036, 40612, 47124, 56592, 68310, 72644, 74008,
76496, 87516, 142428, 143572, 149270, 190944, 391820,
430404, 462748, 465036, 784212, 1565564, 5087940}
:[font = text; inactive; preserveAspect; endGroup; endGroup]
However some (for instance 2070) do not work.
\-
\!intro
\@/A
\@A HREF="smallnum.html"
\!smallnum
:[font = section; inactive; Cclosed; preserveAspect; startGroup]
Small Numerators
:[font = text; inactive; preserveAspect]
\!intro
The algorithms described above work for any input. We now discuss techniques limited to specific numerators. The typical question here is how many terms are needed to represent fractions with a given numerator. For fractions 2/y the answer is clearly 2. Some fractions 3/y require 3 terms, as we see below. It is not known whether any fraction 4/y requires 4 terms.
More generally, good bounds are known on the number of terms needed to represent x/y measured as a function of y
\@A HREF="refs.html#Vos85"
\.[Vos85]
\@/A
, but there seems to be less work on measuring this minimum number of terms as a function only of x. As we note in the section on 4/y, a solution to this specific case would have implications for the general problem.
:[font = subsection; inactive; preserveAspect; startGroup]
Numerator 3
:[font = text; inactive; preserveAspect]
The basic result for fractions of the form 3/y is that there is a two-term expansion if and only if y has a factor congruent to 2 mod 3. Klee and Wagon
\@A HREF="refs.html#KW91"
\.[KW91]
\@/A
credit this result to N.ÊNakayama; however they supply no citation, so we repeat the proof below.
:[font = text; inactive; preserveAspect]
\@B
Theorem:
\@/B
3/y has a two-term expansion if and only if y has a factor congruent to 2 mod 3.
\@BLOCKQUOTE
\@B
Proof:
\@/B
In one direction, the representation 3/(3n+2)=1/(n+1)+1/(n+1)(3n+2) is found by both the greedy and continued fraction methods. This idea can easily be extended to 3/y where y is a multiple of 3n+2.
In the other direction, suppose y=3n+1 and 3/y=1/a+1/b=(a+b)/ab. First note that a and b must be divisible by the same power of 3, since if a were divisible by 3^i and b by 3^j, with j>i, then a+b would not divisible by 3^j and the powers of 3 wouldn't cancel from the denominator. Let g=gcd(a,b), u=a/g, v=b/g, so 3/y=(u+v)/guv and 3 divides u+v; let u+v=3z. Then 1/a+1/b=3z/guv and g must factor as zw since gcd(uv,u+v)=1. So y=uvw. For u+v=3z, one of u and v (say u) must be 2 mod 3, giving the factor of y we seek.
\@/BLOCKQUOTE
Unfortunately this seems to imply that finding short representations, even in this special case, is computationally difficult: at least as difficult as factoring integers.
:[font = text; inactive; preserveAspect; endGroup]
The
\@A HREF="greed.html#smallnum"
\.small numerator version of the reverse greedy method
\@/A
(which includes factorization as one of its subroutines) will always find a two-term representation for 3/n when one exists. Some examples of two-term representations that would not be found by our other general algorithms: 3/25=1/10+1/50; 3/55=1/22+1/110=1/20+1/220; 3/121=1/44+1/484
:[font = subsection; inactive; preserveAspect; startGroup]
Numerator 4
:[font = text; inactive; preserveAspect]
The question of whether all fractions 4/y have 3-term representations is discussed by Mordell
\@A HREF="refs.html#Mor69"
\.[Mor69]
\@/A
, who attributes it to Erdšs and Straus. Guy
\@A HREF="refs.html#Guy81"
\.[Guy81]
\@/A
cites several other authors as having worked on the problem: Bernstein, Obl‡th, Rosati, Shapiro, Straus, Yamamoto, and Franceschine. Others have worked on more general versions of this problem including Schinzel, Sierpinski, Sedl‡cek, Palamˆ, Stewart, Webb, Breusch, Graham, and Vaughan. A positive solution to this question would have more general implications: we could use such a solution as the basis for a conflict resolution method that, given a number x/y, would find an Egyptian fraction representation with x^(Log[3]/Log[4]) Å x^0.7925 terms.
:[font = subsubsection; inactive; preserveAspect; startGroup]
Modular Conditions
:[font = text; inactive; preserveAspect; endGroup]
Mordell shows that in any example 4/y requiring 4 terms in an Egyptian fraction representation, y must be 1 mod 24, ±1 mod 5, and one of three values mod 7 (giving a total of 6 possible values mod 840, all squares of small numbers). If y is a minimal counterexample, it must be prime
(since if y=ab we could divide all terms in a representation of 4/a by b).
If y is 2 or 3 mod 4, the greedy algorithm gives a 2 or 3 term representation. If y is 1 mod 4 we have the representation 1/ceil[y/4] + 3/(y ceil[y/4]) where the last term has a 2-term expansion whenever y is 2 mod 3 or 5 mod 8. So if 4/y is to fail to have a 3 term representation, y must be of the form 24n + 1. Several methods extend this analysis by representing 4/y when y (equivalently n) has certain values modulo small primes.
The representations 1/(6n+1) + 3/(24n+1)(6n+1) and 1/(18n+1)(24n+1) + 3/(18n+1) work if one of 6n+1, 18n+1, or 24n+1 is divisible by a prime p congruent to 5 mod 6. Thus for any of these primes one can derive rules for finding three-term representations of 4/y, that work whenever y has certain values mod p. We can use this technique to find representations when n is congruent to 4, 3, or 1 mod 5 (and so, rule out counterexamples for y congruent to anything but ±1 mod 5).
The representation 1/(6n+k) + (4k-1)/(6n+k)(24n+1) works via a greedy method if a factor of the second denominator is (4k-2) mod (4k-1), or more generally if the factor is (4k-1-i) mod (4k-1) and i divides the denominator. In particular these work with k=2 when n is 2, 3, 4, or 6 mod 7
(with the corresponding values of i being 0, 1, 1, and 2). Therefore in any counterexample 4/y, y must be a quadratic residue mod 7.
Yet another type of rule is possible: consider the decomposition
1/(6n+k) +a/(6n+k)(24n+1) + b/(6n+k)(24n+1), where a+b = 4k-1. This is only possible when k is even, since otherwise one of a or b would be even and not divide the denominator.
For instance 4/(24n+1)=1/(6n+10) + 26/(6n+10)(24n+1) + 13/(6n+10)(24n+1)
where the last two simplify to unit fractions if n is 7 mod 13.
:[font = subsubsection; inactive; preserveAspect; startGroup]
Particular Values
:[font = text; inactive; preserveAspect]
As noted above, the numbers y for which 4/y might possibly require four terms fall into six classes modulo 840: 1, 121, 169, 289, 361, and 529. We only need to consider prime n since if mn is a counterexample, so must be both m and n. Following are representations for all such cases through 12500. Most use rules like the ones described above that depend only on the values of y mod 11, 13, and 19, but 4/3361 uses a method that depends on y mod 29 and 4/8089 uses a method that depends on y mod 17.
:[font = input; preserveAspect]
4/1801 = 1/451 + 1/295364 + 1/3249004
:[font = input; preserveAspect]
4/2521 = 1/636 + 1/69748 + 1/131876031
:[font = input; preserveAspect]
4/2689 = 1/676 + 1/139828 + 1/908882
:[font = input; preserveAspect]
4/3049 = 1/772 + 1/60980 + 1/5884570
:[font = input; preserveAspect]
4/3361 = 1/841 + 1/974690 + 1/28266010
:[font = input; preserveAspect]
4/3529 = 1/892 + 1/80726 + 1/569764108
:[font = input; preserveAspect]
4/3889 = 1/975 + 1/345150 + 1/268457670
:[font = input; preserveAspect]
4/4201 = 1/1096 + 1/25208 + 1/13237351
:[font = input; preserveAspect]
4/4561 = 1/1244 + 1/13684 + 1/15603181
:[font = input; preserveAspect]
4/4729 = 1/1185 + 1/510732 + 1/201739140
:[font = input; preserveAspect]
4/5209 = 1/1308 + 1/296262 + 1/3086457516
:[font = input; preserveAspect]
4/5569 = 1/1402 + 1/200484 + 1/140539284
:[font = input; preserveAspect]
4/5881 = 1/1604 + 1/17644 + 1/25941091
:[font = input; preserveAspect]
4/6841 = 1/1713 + 1/1065486 + 1/7288989726
:[font = input; preserveAspect]
4/7681 = 1/1924 + 1/1136788 + 1/7389122
:[font = input; preserveAspect]
4/8089 = 1/2023 + 1/5775546 + 1/98184282
:[font = input; preserveAspect]
4/8521 = 1/2324 + 1/25564 + 1/54457711
:[font = input; preserveAspect]
4/8689 = 1/2175 + 1/1718250 + 1/14929874250
:[font = input; preserveAspect]
4/8761 = 1/2196 + 1/836676 + 1/3665059218
:[font = input; preserveAspect]
4/8929 = 1/2233 + 1/7250348 + 1/79753828
:[font = input; preserveAspect]
4/9241 = 1/2314 + 1/1644898 + 1/10691837
:[font = input; preserveAspect]
4/9601 = 1/2406 + 1/1008105 + 1/269500070
:[font = input; preserveAspect]
4/9769 = 1/2452 + 1/614226 + 1/12000747588
:[font = input; preserveAspect]
4/10369 = 1/2828 + 1/31108 + 1/80639713
:[font = input; preserveAspect]
4/12049 = 1/3016 + 1/2795368 + 1/18169892
:[font = input; preserveAspect]
4/12289 = 1/3078 + 1/1644678 + 1/30317171913
:[font = text; inactive; preserveAspect; endGroup; endGroup; endGroup]
According to Guy, N. Franceschine has performed similar calculations for y<10^8.
\-
\!intro
\@/A
\@A HREF="refs.html"
\!refs
:[font = section; inactive; preserveAspect; startGroup]
References
:[font = text; inactive; preserveAspect]
\-
\!intro
\@/A
\-
\!refs
:[font = text; inactive; preserveAspect]
\@A NAME="Bee93"
[Bee93]
\@/A
\@BLOCKQUOTE
L. Beeckmans. The splitting algorithm for Egyptian fractions.
\@BR
\@I
J. Number Th.
\@/I
43, 1993, pp. 173Ð185.
\@BR
This paper contains a proof that the
\@A HREF="conflict.html#split"
\.splitting method
\@/A
terminates; Wagon
\@A HREF="#Wag91"
\.[Wag91]
\@/A
credits the same result to Graham and Jewett.
\@/BLOCKQUOTE
;[s]
3:0,0;115,1;128,0;369,-1;
2:2,14,10,Times,0,12,0,0,0;1,14,10,Times,2,12,0,0,0;
:[font = text; inactive; preserveAspect]
\@A NAME="Ble72"
[Ble72]
\@/A
\@BLOCKQUOTE
M. N. Bleicher. A new algorithm for the expansion of continued fractions.
\@BR
\@I
J. Number Th.
\@/I
4, 1972, pp. 342Ð382.
\@BR
Defines two methods for Egyptian fraction representation: what he
calls the Farey sequence method, which is equivalent to the
\@A HREF="cfrac.html#cfrac"
\.continued fraction method
\@/A
described here, and what he calls the continued fraction method, which is a variant of what
we call the
\@A HREF="cfrac.html#grouped"
\.grouped continued fraction method
\@/A
.
\@/BLOCKQUOTE
;[s]
3:0,0;127,1;141,0;552,-1;
2:2,14,10,Times,0,12,0,0,0;1,14,10,Times,2,12,0,0,0;
:[font = text; inactive; preserveAspect]
\@A NAME="Bre54"
[Bre54]
\@/A
\@BLOCKQUOTE
R. Breusch. A special case of Egyptian fractions, solution to advanced problem 4512.
\@BR
\@I
Amer. Math. Monthly
\@/I
61, 1954, pp. 200Ð201.
\@BR
Shows that every x/y with y odd has an
Egyptian fraction representation with all denominators odd, by using a method similar to the
\@A HREF="binary.html#binrem"
\.binary remainder method
\@/A
but using the base 5(3^k) instead of 2^k.
\@/BLOCKQUOTE
;[s]
3:0,0;138,1;157,0;442,-1;
2:2,14,10,Times,0,12,0,0,0;1,14,10,Times,2,12,0,0,0;
:[font = text; inactive; preserveAspect]
\@A NAME="BW84"
[BW84]
\@/A
\@BLOCKQUOTE
T. H. Byers and M. S. Waterman. Determining all optimal and near-optimal solutions when
solving shortest path problems by dynamic programming.
\@BR
\@I
Oper. Res.
\@/I
32, 1984, pp. 1381Ð1384.
\@BR
Byers and Waterman describe a simple algorithm for finding short paths in
a graph, used in our implementation of the
\@A HREF="cfrac.html#grouped"
\.grouped continued fraction method
\@/A
.
\@/BLOCKQUOTE
;[s]
3:0,0;193,1;203,0;443,-1;
2:2,14,10,Times,0,12,0,0,0;1,14,10,Times,2,12,0,0,0;
:[font = text; inactive; preserveAspect]
\@A NAME="Epp94"
[Epp94]
\@A
\@BLOCKQUOTE
\@A HREF="http://www.ics.uci.edu/~eppstein/pubs/p-kpath.html"
D. Eppstein. Finding the k shortest paths.
\@/A
\@BR
\@I
35th IEEE Symp. Foundations of Computer Science,
\@/I
1994, pp. 154Ð165.
\@BR
I describe what is theoretically the fastest known algorithm for the shortest path problem used in the
\@A HREF="cfrac.html#grouped"
\.grouped continued fraction method
\@/A
, however my technique is rather more complex than that of
\@A HREF="#BW84"
\.[BW84]
\@/A
and has not been implemented in
\@I
Mathematica.
\@/I
\@/BLOCKQUOTE
;[s]
7:0,0;130,1;131,0;162,1;209,0;541,1;552,0;573,-1;
2:4,14,10,Times,0,12,0,0,0;3,14,10,Times,2,12,0,0,0;
:[font = text; inactive; preserveAspect]
\@A NAME="Guy81"
[Guy81]
\@/A
\@BLOCKQUOTE
R.K. Guy.
\@I
Unsolved Problems in Number Theory.
\@/I
\@BR
Springer-Verlag, 1981, pp. 87Ð93.
\@BR
Guy lists a number of questions about Egyptian fractions, including the following:
\@UL
\@LI
\@A HREF="smallnum.html"
Does 4/y have a 3-term representation for all y?
\@/A
Does 5/y? Does x/y for x sufficiently large relative to y?
\@LI
\@A HREF="approx.html#odd"
Does the odd greedy method terminate?
\@/A
\@LI
What different denominators are possible in a t-term representation of one?
Do all positive-density sets of integers have a subset forming the denominators of a representation of one?
\@LI
If we assign to each of the integers one of a finite set of colors, can we pick a single color that can be used as the denominators for representations of all rationals?
\@/UL
Guy also provides a long bibliography.
\@/BLOCKQUOTE
;[s]
3:0,0;57,1;91,0;874,-1;
2:2,14,10,Times,0,12,0,0,0;1,14,10,Times,2,12,0,0,0;
:[font = text; inactive; preserveAspect]
\@A NAME="KW91"
[KW91]
\@/A
\@BLOCKQUOTE
V. Klee and S. Wagon.
\@I
Old and New Unsolved Problems in Plane Geometry and Number Theory.
\@/I
Math. Assoc. of America, 1991, pp. 175Ð177 and 206Ð208.
\@BR
Concentrates primarily on the question of
\@A HREF="approx.html#odd"
\.whether the odd greedy method halts
\@/A
; notes that a similar method for finding representations with even denominators does halt; contains a number of further references.
\@/BLOCKQUOTE
;[s]
3:0,0;67,1;132,0;460,-1;
2:2,14,10,Times,0,12,0,0,0;1,14,10,Times,2,12,0,0,0;
:[font = text; inactive; preserveAspect]
\@A NAME="Mor69"
[Mor69]
\@/A
\@BLOCKQUOTE
L. J. Mordell.
\@I
Diophantine Equations.
\@/I
Academic Press, 1969, pp. 287Ð290.
\@BR
Discusses the question of
\@A HREF="smallnum.html"
\.whether 4/y has a three-term representation
\@/A
; describes methods of finding such representations depending on the value of n modulo various small primes.
\@/BLOCKQUOTE
;[s]
3:0,0;62,1;83,0;355,-1;
2:2,14,10,Times,0,12,0,0,0;1,14,10,Times,2,12,0,0,0;
:[font = text; inactive; preserveAspect]
\@A NAME="NZ80"
[NZ80]
\@/A
\@BLOCKQUOTE
I. Niven and H.S. Zuckerman.
\@I
An Introduction to the Theory of Numbers.
\@/I
4th ed., Wiley, 1980, p. 200.
\@BR
They describe in an exercise here the secondary sequences used in the
\@A HREF="cfrac.html"
\.continued fraction methods
\@/A
of Egyptian fraction representation.
\@/BLOCKQUOTE
;[s]
3:0,0;74,1;114,0;334,-1;
2:2,14,10,Times,0,12,0,0,0;1,14,10,Times,2,12,0,0,0;
:[font = text; inactive; preserveAspect]
\@A NAME="Ste54"
[Ste54]
\@/A
\@BLOCKQUOTE
B. M. Stewart. Sums of distinct divisors.
\@BR
\@I
Amer. J. Math.
\@/I
76, 1954, pp. 779Ð785.
\@BR
Uses the
\@A HREF="binary.html#binrem"
\.binary remainder method
\@/A
to find representations with all denominators even. Also, like
\@A HREF="#Bre54"
\.[Bre54]
\@/A
, uses a method similar to the binary remainder method (using base 35(3^k))
to find odd representations of fractions with odd denominators.
\@/BLOCKQUOTE
;[s]
3:0,0;95,1;109,0;465,-1;
2:2,14,10,Times,0,12,0,0,0;1,14,10,Times,2,12,0,0,0;
:[font = text; inactive; preserveAspect]
\@A NAME="Ste92"
[Ste92]
\@/A
\@BLOCKQUOTE
I. Stewart. The riddle of the vanishing camel.
\@BR
\@I
Scientific American,
\@/I
June 1992, pp. 122Ð124.
\@BR
Stewart shows that any rational has only a finite number of t-term Egyptian fraction representations, for any fixed number t, and describes a
\@A HREF="force.html#short"
\.brute force method
\@/A
for finding all such representations.
\@/BLOCKQUOTE
;[s]
5:0,0;99,2;118,0;143,1;144,0;403,-1;
3:3,14,10,Times,0,12,0,0,0;1,13,9,Times,0,11,0,0,0;1,14,10,Times,2,12,0,0,0;
:[font = text; inactive; preserveAspect]
\@A NAME="Tak21"
[Tak21]
\@/A
\@BLOCKQUOTE
T. Takenouchi.
On an indeterminate equation.
\@BR
\@I
Proc. Physico-Mathematical Soc. of Japan
\@/I
(3rd ser.) 3, 1921, pp. 78-92.
\@BR
In this paper, discovered for me by Stefan Bartels, Takenouchi proves that any number with a k-term unit fraction representation has a representation in which all terms are distinct. Bartels writes "Takenouchi does not state the theorem itself but gives a proof to it. He uses the fact that the sum of the denominators of the representation increases and the fact that the number of representations of a given length is finite. As far as I know this article has not been recognized in the meantime. I found some proofs (done in the 60s) which for example prove that n/m can be
represented as a sum of n Egyptian fractions. This shows that the article is (was) quite unknown in mathematical literature."
\@/BLOCKQUOTE
:[font = text; inactive; preserveAspect]
\@A NAME="TY90"
[TY90]
\@/A
\@BLOCKQUOTE
G. Tenenbaum and H. Yokota. Length and denominators of Egyptian fractions.
\@BR
\@I
J. Number Th.
\@/I
35, 1990, pp. 150Ð156.
\@BR
This paper provides good simultanous bounds on the number of terms and the denominators of an Egyptian fraction representation, as discussed in the section on the
\@A HREF="binary.html#binrem"
\.binary remainder method
\@/A
.
\@/BLOCKQUOTE
;[s]
3:0,0;125,1;138,0;412,-1;
2:2,14,10,Times,0,12,0,0,0;1,14,10,Times,2,12,0,0,0;
:[font = text; inactive; preserveAspect]
\@A NAME="Vos85"
[Vos85]
\@/A
\@BLOCKQUOTE
M. Vose. Egyptian fractions.
\@BR
\@I
Bull. Lond. Math. Soc.
\@/I
17, 1985, p. 21.
\@BR
Shows that every x/y has a t-term representation where t=O(Sqrt Log[y]). The technique is similar to the
\@A HREF="binary.html#binrem"
\.binary remainder method
\@/A
.
\@/BLOCKQUOTE
;[s]
3:0,0;82,1;104,0;315,-1;
2:2,14,10,Times,0,12,0,0,0;1,14,10,Times,2,12,0,0,0;
:[font = text; inactive; preserveAspect]
[Wag91]
\@BLOCKQUOTE
S. Wagon.
\@I
Mathematica in Action.
\@/I
\@BR
W.H. Freeman, 1991, pp. 271Ð277.
\@BR
Wagon implements the
\@A NAME="approx.html"
greedy and odd greedy methods,
\@/A
and describes the
\@A NAME="conflict.html#split"
splitting method.
\@/A
He also mentions the open problem of
\@A NAME="approx.html#odd"
whether the odd greedy method always terminates
\@/A
for the special case of fractions with numerator 2.
\@/BLOCKQUOTE
;[s]
3:0,0;35,1;56,0;441,-1;
2:2,14,10,Times,0,12,0,0,0;1,14,10,Times,2,12,0,0,0;
:[font = text; inactive; preserveAspect; endGroup; endGroup]
\+
\@P
\@HR
\@P
\@A HREF="http://www.ics.uci.edu/~eppstein/numth/egypt/"
Egyptian Fractions,
\@/A
\@A HREF="http://www.ics.uci.edu/~eppstein/numth/"
Number Theory,
\@/A
\@A HREF="http://www.ics.uci.edu/~eppstein/"
David Eppstein,
\@/A
\@A HREF="http://www.ics.uci.edu/"
ICS,
\@/A
\@A HREF="http://www.uci.edu/"
UC Irvine
\@/A
\@P
\@SMALL
Formatted by
\@A HREF="http://www.maths.monash.edu.au/people/tdr/nbks/sourceCode.html"
\.nb2html
\@/A
and
\@A HREF="http://www.ics.uci.edu/~eppstein/pubs/filter.html"
\.filter
\@/A
.
\@!--#config timefmt="%d %h %Y, %T %Z" --
Last update:
\@!--#flastmod file="egypt.ma" --
.
\@/SMALL
\-
^*)
*