# Expanding integers into distinct egyptian fractions - what is the optimal way?

We know that there are infinite ways to represent $1$ as a sum of distinct unit fractions (i.e. egyptian fractions). The most optimal one (the least demoninators and the least number of fractions) is:

$$1=\frac{1}{2}+\frac{1}{3}+\frac{1}{6}$$

But how to represent other integers in the same way? The rules are as follows: we can't use $1$ as a denominator and no repetitions are allowed.

So far I found a way, which is surely not optimal: for any integer $a$ we find the closest harmonic number such that $H_n-1<a$. Then we expand the difference by the greedy algorithm. It seems to work so far, but gives horrible fractions:

$$2=\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}+\frac{1}{9}+\frac{1}{10}+\frac{1}{15}+\frac{1}{230}+\frac{1}{57960}$$

$$3=\sum _{n=2}^{30} \frac{1}{n}+\frac{1}{200}+\frac{1}{77706}+\frac{1}{16532869712}+\frac{1}{3230579689970657935732}+ \\ +\frac{1}{36802906522516375115639735990520502954652700}$$

For $4$ there is no space here to write the monstrous denominators. However, it definitely consists of $98$ fractions ($81$ of them represent $H_{82}-1$), and the largest denominator contains $142549$ digits.

What is a more optimal ways to expand integers into egyptian fractions?

There is no "the optimal way", as Martin R noticed, since we can optimize the number of fractions or the denominators. I'm searching for something better than my current way at least.

Is it always possible to expand any integer this way?

I know that the greedy algorithm terminates for any rational number. And the smallest denominator of the difference between $a$ and $H_n-1$ is larger than $n$ (if we choose $n$ as largest possible so that the difference is positive), so I think the answer is yes. But I'm not sure if this is rigorous enough.

See this link which uses the same method and provides the same example for $3$. Just found it.

Update

Using @DavidP's advice and the identity to get rid of repeating fractions:

$$\frac{1}{n}=\frac{1}{n+1}+\frac{1}{n(n+1)}$$

I managed to get another expansion for $2$ with more fractions, but smaller maximum denominator:

$$2=\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}+\frac{1}{9}+\frac{1}{12}+\frac{1}{13}+\frac{1}{18}+ \\ +\frac{1}{19}+\frac{1}{36}+\frac{1}{42}+\frac{1}{43}+\frac{1}{56}+\frac{1}{156}+\frac{1}{342}+\frac{1}{1806}$$

So at least I know there is more than one way.

An interesting parameter for optimization seems to be the product of all the denominators, which grows with the size of each individual denominator and with the number of fractions.

Comparing the provided expansions for $2$ we find that the first one is by far the most optimal.

Update 2:

For unit fractions with composite denominators we can create infinitely many 'splitting' formulas, using the following trivial identities:

$$1=\frac{a}{a+b}+\frac{b}{a+b} \\ \frac{1}{ab}=\frac{1}{a(a+b)}+\frac{1}{b(a+b)}$$

The famous identity above comes when $b=1$. This can be continued $m$ times to obtain $2^m$ fractions.

Another case:

$$1=\frac{a}{a+b+c}+\frac{b}{a+b+c}+\frac{c}{a+b+c} \\ \frac{1}{abc}=\frac{1}{ab(a+b+c)}+\frac{1}{bc(a+b+c)}+\frac{1}{ac(a+b+c)}$$

This can also be continued. If $b=c$, we obtain a $3$ term splitting for $1/ab$:

$$\frac{1}{ab}=\frac{1}{ab(a+b+1)}+\frac{1}{b(a+b+1)}+\frac{1}{a(a+b+1)}$$

And so on, for a larger number of terms.

Some examples:

$$\frac{1}{6}=\frac{1}{10}+\frac{1}{15}$$

$$\frac{1}{12}=\frac{1}{21}+\frac{1}{28}=\frac{1}{16}+\frac{1}{48}$$

And a neat example:

$$\frac{1}{2}=\frac{10}{20}=\frac{10}{40}+\frac{10}{50}+\frac{10}{200}=\frac{1}{4}+\frac{1}{5}+\frac{1}{20}$$

In any case, I've obtained yet another expansion for $2$, but now with very small denominators:

$$2=\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{9}+\frac{1}{10}+\frac{1}{15}+\frac{1}{18}+\frac{1}{20}+\frac{1}{21}+ \\ +\frac{1}{27}+\frac{1}{30}+\frac{1}{54}+\frac{1}{63}+\frac{1}{70}$$

And yet another, with even smaller denominators and shorter:

$$2=\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}+\frac{1}{9}+\frac{1}{12}+\frac{1}{14}+\frac{1}{18}+\frac{1}{24}+\\+\frac{1}{27}+\frac{1}{28}+\frac{1}{36}+\frac{1}{54}$$

For this I used another identity for even denominators:

$$\frac{1}{2a}=\frac{1}{2a(2a+3)}+\frac{1}{a(2a+3)}+\frac{1}{2a+3}$$

Update 3:

I decided that it makes more sense to optimize the size of the denominator after all. Because in any particular case, the number of fractions is restricted by the size of the largest denominator.

Here is the best result I was able to get for $3$ (the sequence of denominators is provided):

$$\{2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,19,20,22,23,24,27,28,32,36, \\ 38,44,52,54,56,63,72,76,80,88,91,120,231,608,759,1518\}$$

See also an awesome sequence of denominators for $5$ provided by Greg Martin in the comments to Jack D'Aurizio's answer:

{2,3,4,5,6,7,8,9,10,11,12,13,14,15,17,18,19,20,21,22,23,25,26,27,28,29,30,31,32,33,34,35,36,38,39,40,41,42,43,44,45,46,48,49,50,51,52,53,54,55,56,57,58,60,62,63,64,66,67,68,69,70,72,73,75,76,78,80,81,82,83,84,87,90,91,92,93,94,95,96,97,98,99,104,105,108,110,112,115,116,117,119,120,121,123,126,127,128,129,130,131,132,134,136,137,140,141,143,144,145,146,147,148,150,152,153,154,156,159,160,161,162,165,166,168,169,170,171,174,176,177,178,180,182,183,185,187,190,192,195,196,198,200,201,204,205,206,207,208,209,210,212,213,215,217,220,221,222,224,225,228,230,231,232,234,235,238,240,242,244,245,246,247,249,252,253,254,255,258,260,261,264,266,268,270,272,273,274,275,276,279,280,282,285,286,287,288,290,292,294,295,297,299,300,301,304,306,308,309,310,312,315,318,319,320,322,323,324,325,329,330,336,338,340,341,342,345,348,350,351,352,354,355,356,357,360,363,364,365,368,371,372,374,377,378,380,384,385,388,390,391,396,399,400,402,403,405,406,408,411,412,413,414,416,418,420,425,427,429,432,434,435,437,438,440,442,448,450,455,456,459,460,462,464,465,468,469,475,476,480,483,484,485,493,494,495,496,497,504,506,508,510,511,513,520,522,524,525,527,528,532,534,535,540,544,546,548,550,551,552,558,560,561,567,570,572,575,576,580,581,582,585,589,594,595,598,600,605,608,609,612,616,620,621,623,624,627,630,635,638,640,642,644,646,648,650,651,660,663,665,667,672,675,676,680,682,684,685,690,693,696,700,702,704,713,714,715,720,721,725,726,728,736,741,744,748,749,754,756,759,760,762,765,770,775,780,782,783,786,792,798,800,805,806,810,812,816,819,825,828,832,836,837,840,845,847,850,855,858,864,868,870,874,880,884,891,896,897,899,900,910,912,917,918,920,924,928,930,935,936,945,950,952,957,960,966,969,975,986,988,990,992}

• I am not an expert on this topic, but "the least demoninators" and "the least number of fractions" seems to be two different criteria. How do you define "the most optimal way"? Jan 31, 2017 at 21:11
• @MartinR, the example for $1$ fits both. In my case, either one will be fine Jan 31, 2017 at 21:12
• Yes, every integer can be expanded in this way, using, for example, $$1=\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{6}$$ So, $$2=1+1 = \dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{6}+\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{6}$$ $$=\dfrac{\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{6}}{2}+\dfrac{\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{6}}{3}+\dfrac{\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{6}}{6} + \dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{6}$$ Simplify and keep going until no duplicates Jan 31, 2017 at 21:44
• @DavidP, I used a variation of your method to get another expansion for $2$, so thank you Jan 31, 2017 at 22:22
• One tool that may be useful to you: you may always replace, beginning with the largest duplicates, $$\dfrac{1}{n} = \dfrac{1}{n+1} + \dfrac{1}{n(n+1)}$$ edit: i see you found this out yourself Jan 31, 2017 at 22:33

There are many algorithms for decomposing some $\frac{p}{q}\in\mathbb{Q}^+$ as $$\frac{p}{q}=\sum_{a\in A\subset\mathbb{Z}^+}\frac{1}{a}$$ for instance the greedy algorithm, but the answer to your question strongly depends on what you mean by optimal. If you mean with the least number of terms, the question is not trivial at all: in fact, it is an open problem. Anyway it is not difficult to prove by induction that the greedy algorithm or the algorithm based on the identity $\frac{1}{n}=\frac{1}{n+1}+\frac{1}{n(n+1)}$ stops at some point for any $\frac{p}{q}\in\mathbb{Q}^+$.

Here it is a representation of $2$ I found by combining the two approaches: $$2 = \frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}+\frac{1}{10}+\frac{1}{12}+\frac{1}{15}+\frac{1}{40}+\frac{1}{140}$$ It has $12$ terms, $A=\{2,3,4,5,6,7,8,10,12,15,40,140\}$ and $\prod_{a\in A}a\approx 4\cdot 10^{11}.$

Another representation with twelve terms is given by $A=\{2,3,4,5,6,7,8,9,10,15,230,57960\}$ with $\prod_{a\in A}a\approx 7.2\cdot10^{14}$.

Yet another one is given by $A=\{2,3,4,5,6,7,8,9,12,14,63,2520\}$ with $\prod_{a\in A}a\approx 10^{13}$.

After a long search, I also found a representation for $3$ with just $33$ terms, given by $A=[2,18]\cup[20,28]\cup\{30,32,33,34,864,199836,7813587600\}$.

• @ Jack D'Aurizio, in the edit I clarify that a possible parameter for optimization is the product of all denominators. Also please note that I already use the greedy algorithm, and it's terrible for numbers $\geq 4$. Thank you for the answer! Jan 31, 2017 at 22:48
• Here's a 453-term representation for 6 that I found many years back. One can probably get away with fewer terms (though 227 terms is a lower bound, just from the harmonic sum), but note that all denominators are less than 1,000. Feb 1, 2017 at 0:50
• Then you have my permission to consider it a 452-term representation for 5.... Feb 1, 2017 at 0:54
• A new result for $2$ with product ~ $3 \cdot 10^{12}$ and extremely small denominators: $$[2,3,4,5,6,8,10,12,15,20,21,24,28]$$ Feb 3, 2017 at 12:57
• A better one: $[2,3,4,5,6,8,9,10,15,18,20,24]$ Jan 6, 2019 at 8:50