6
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ 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"? $\endgroup$ – Martin R Jan 31 '17 at 21:11
  • $\begingroup$ @MartinR, the example for $1$ fits both. In my case, either one will be fine $\endgroup$ – Yuriy S Jan 31 '17 at 21:12
  • $\begingroup$ 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 $\endgroup$ – David Peterson Jan 31 '17 at 21:44
  • $\begingroup$ @DavidP, I used a variation of your method to get another expansion for $2$, so thank you $\endgroup$ – Yuriy S Jan 31 '17 at 22:22
  • $\begingroup$ 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 $\endgroup$ – David Peterson Jan 31 '17 at 22:33
6
$\begingroup$

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\}$.

$\endgroup$
  • $\begingroup$ @ 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! $\endgroup$ – Yuriy S Jan 31 '17 at 22:48
  • $\begingroup$ @YuriyS: in such a case I think we may provide some (very weak) bounds by studying the $p$-adic height of the terms of the expansion, together with their total magnitude, for a set of primes $p$. But again, which set of primes leads to optimality is a very tough question. $\endgroup$ – Jack D'Aurizio Jan 31 '17 at 22:54
  • 1
    $\begingroup$ 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. $\endgroup$ – Greg Martin Feb 1 '17 at 0:50
  • 4
    $\begingroup$ Then you have my permission to consider it a 452-term representation for 5.... $\endgroup$ – Greg Martin Feb 1 '17 at 0:54
  • 1
    $\begingroup$ 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]$$ $\endgroup$ – Yuriy S Feb 3 '17 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.