20
$\begingroup$

This is essentially the same as the closed question Representation of rational numbers as the sum of 1/k but I hope I can make a case for it as an MO-worthy question.

Ed Pegg, Jr., in his Math Games column for 19 July 2004 at the MAA website, http://www.maa.org/editorial/mathgames/mathgames_07_19_04.html writes, "Here is an interesting sequence of fractions that would likely would [sic] have fascinated Ahmes: $$1/2, 2/3, 4/5, 8/11, 14/17, 19/23, 24/29, 49/59, 65/71, 76/83, 61/157, 183/191, 260/269, 289/299.$$ $8/11 = 1/2 + 1/6 + 1/21 + 1/77$. This is the simplest Egyptian fraction that requires 4 parts. $14/17 = 1/2 + 1/4 + 1/20 + 1/55 + 1/187$ requires 5 parts. 289/299 is the simplest fraction that requires 14 parts. One might think that this sort of thing was well known, but it isn't.... What is the simplest fraction that requires 15 parts, 16 parts, and beyond?"

Pegg never defines "simplest," but presumably it means smallest (positive) denominator and, among fractions with the same denominator, smallest (positive) numerator. So the general question would be, given $s$, what's the simplest rational that can be expressed as a sum of $s$ unit fractions, but not fewer?

In this form, it's probably an open, and maybe impossible, problem (that is, I don't think anyone will find a simple formula for the rational as a function of $s$), so let me ask a bit less. Has there been any advance beyond 14 since 2004? Are there any bounds in the literature (that is, bounds on the "complexity" of the rational as a function of $s$)?

I note that Pegg gives no source for his list of 14. The Online Encyclopedia of Integer Sequences does not recognize the sequence of numerators, nor the sequence of denominators. Before anyone suggests typing "Egyptian fractions" into Google, or looking at the Wikipedia article on that subject, I hope he or she will verify that the particular question I'm asking is in fact answerable by such means.

EDIT: As per the comments, it appears that only the first four terms in Pegg's list are correct, and that the current state of knowledge is $${1\over2},{2\over3},{4\over5},{8\over11},{16\over17},{77\over79},{732\over733}.$$

Also as per the comments, if we are after $f(s)=\min\lbrace b:N(a,b)=s{\rm\ for\ some\ }a,1\le a\lt b\rbrace$ then $f(s)\ge e^{Cn^2}$ for some $C>0$, and, conjecturally, $f(s)\ge e^{e^{Cn}}$ for some $C>0$.

At this point I will gladly settle for a calculation of $s(8)$.

Improve this question
$\endgroup$
16
  • 5
    $\begingroup$ 14/17 = 1/2 + 1/4 + 1/14 + 1/476 appears to be an error; I believe 16/17 = 1/2 + 1/3 + 1/10 + 1/128 + 1/32640 is the simplest requiring 5 terms. $\endgroup$
    – Hugo van der Sanden
    Commented Jul 28, 2010 at 10:52
  • 1
    $\begingroup$ "He conjectures that the true result is $N(a,b)=O(\log\text{}\log b)$, and he in fact establishes the inequalities $$ \sum_{a=1}^{b-2}N(a,b)>{\textstyle\frac 1{2}}(b-2)(\log\text{}\log b-1),\quad N(b-1,b)>\log\text{}\log b-1. $$ " $\endgroup$
    – Wadim Zudilin
    Commented Jul 28, 2010 at 12:23
  • 6
    $\begingroup$ I haven't checked the intervening numbers, but by hand I found 289/299 = 1/2 + 1/3 + 1/8 + 1/156 + 1/552. I checked also just using the greedy algorithm, and that gives 1/2 + 1/3 + 1/8 + 1/122 + 1/39795 + 1/1935522680. So I have no idea what Pegg's numbers are supposed to represent, but I can't see any relation between them and the stated problem. Time permitting I'll try calculating the sequence, but I anticipate the correct denominators will grow much more rapidly, so it'll be hard to calculate more than 7-8 terms. $\endgroup$
    – Hugo van der Sanden
    Commented Jul 28, 2010 at 18:44
  • 1
    $\begingroup$ My apologies to all for taking Pegg's numbers on faith. Guy, Unsolved Problems In Number Theory, D11, writes, "Victor Meally...noted that 2/3, 4/5 and 8/11 are the [simplest rationals] that need 2, 3 and 4 [unit fractions].... Stephane Vandemergel, in a 93-04-28 letter, states that 16/17 requires 5 [unit] fractions, and 77/79 needs 6." With these numbers, I found oeis.org/A097048 which gives 732/733 as the next, and last known, term. So unless there has been some advance since then, exact values are only known to $s=7$. As for bounds... (see next comment) $\endgroup$
    – Gerry Myerson
    Commented Jul 29, 2010 at 0:47
  • 1
    $\begingroup$ Lasse: re: "Is it obvious / known that for any n there is a rational number that can be written as a sum of n unit fraction, but not of n-1?" Maybe not obvious, but it is known. If s_i is the i'th number in Sylvester's sequence then (s_i-1)/s_i requires i terms. E.g. 1/2 requires 1 term, 2/3 requires 2, 6/7 requires 3, 42/43 requires 4, etc. $\endgroup$
    – David Eppstein
    Commented Jul 29, 2010 at 3:57

1 Answer 1

Reset to default
16
$\begingroup$

$s(8) = \frac{27538}{27539}$.

I have made the code I used available at http://crypt.org/hv/maths/least_eg-0.01.tar.gz, with a README file at http://crypt.org/hv/maths/least_eg-0.01-README.

Update: those links no longer available, code is available via github at https://github.com/hvds/seq/tree/master/least_eg.

The package includes both PARI/GP code and C code using the GNU GMP library to calculate the results, as well as a synopsis of the results for each denominator from 2 to 27539 which may be of use for further analysis.

I estimate the PARI code would have taken about a CPU-year to find the result; the C code runs over 20 times faster on my machine, and I don't understand why the difference is so great. (I'd appreciate email if someone can explain.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Bravo. Bravissimo. Well done, and many thanks. $\endgroup$
    – Gerry Myerson
    Commented Sep 14, 2010 at 23:10
  • 1
    $\begingroup$ The links are broken (2019). Can the files kindly be made available again? $\endgroup$
    – Gottfried Helms
    Commented Nov 26, 2019 at 10:59
  • 1
    $\begingroup$ Sorry I no longer have the original tarball; the C code available via github under github.com/hvds/seq/tree/master/least_eg should be the same or close to what was there. $\endgroup$
    – Hugo van der Sanden
    Commented Nov 27, 2019 at 11:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .