3
$\begingroup$

Given $n > 1$, it's obvious that $$\frac{2^n - 1}{2^n} = \sum_{i = 1}^n \frac{1}{2^i}.$$

For example, $$\frac{15}{16} = \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16}.$$ That's not the answer we'd get using the greedy algorithm, since after taking one half, it would take one third instead of one quarter: $$\frac{15}{16} = \frac{1}{2} + \frac{1}{3} + \frac{1}{10} + \frac{1}{240}.$$

That last denominator is a little larger than I'd like, but it's still just four fractions.

My main question is: does the greedy algorithm ever give more fractions than some other algorithm?

Maybe if we require the fractions to be distinct, e.g., in Egyptian fractions with very large denominators, Mr. Santos gives $$\frac{5}{31} = \frac1 7 + \frac 1 {55} + \frac 1 {3\,979} + \frac 1 {23\,744\,683} + \frac 1 {1\,127\,619\,917\,796\,295},$$ which is preferable to $$\frac{5}{31} = 5 \times \frac{1}{31}$$ only because of the distinct fraction requirement.

Then if the... sorry, my ride to vote is here, and then dinner

$\endgroup$
1
  • $\begingroup$ At least for $\frac{2^n - 1}{2^n}$, the greedy algorithm might give fewer fractions than adding up $2^n$ for $n = -1, -2, -3, \ldots$, but depending on the implementation, might take a very long time to give the answer. $\endgroup$ – Robert Soupe Nov 7 '18 at 5:26
3
$\begingroup$

My interpretation of your hypothesis is: The Greedy Algorithm never gives more Egyptian Fractions than the minimum number "easily proven" necessary.

If you start with the fraction $\frac{n}{m}$ where $(m>n)$ then it can always be split into a sum of $n$ positive Egyptian fractions, but depending on the particular denominator $m$ chosen, less Egyptian Fractions may be needed as an easily provable minimum.

Taking your example with $n=5$ we can split the denominators into even $(2q)$ and odd $(2q+1)$

Case Even Denominator: $$\frac{5}{2q}=\frac{1}{2q}+ \frac{2}{q}$$ If $q$ is even, $2$ Egyptian fractions are required. If $q$ is odd, then $\frac{2}{q}$ can always be written as the sum of two different Egyptian fractions e.g. $$\frac{2}{2t+1}=\frac{1}{t+1}+\frac{1}{(t+1)(2t+1)},$$ giving a minimum of $3$ Egyptian fractions. Therefore in the case of an even denominator the greedy algorithm should not exceed $2$ Egyptian fractions if $q$ is even and $3$ Egyptian Fractions if $q$ is odd for your hypothesis to hold true for $n=5$.

Case Odd Denominator: $$\frac{5}{2q+1}=\frac{1}{2q+1}+ \frac{2}{q+1} +\frac{2}{(q+1)(2q+1)}$$ In the case of $q$ odd the spilt into 3 Egyptian fractions is obvious, in the case q is even and $(q=2u)$ five Egyptian fractions are needed as a simply provable minimum $$\frac{5}{4u+1}=\frac{1}{4u+1}+ \frac{1}{u+1} +\frac{1}{(u+1)(2u+1)}+ \frac{1}{(u+1)(4u+1)} +\frac{1}{(u+1)(2u+1)(4u+1)}$$

Therefore in the case of an odd denominator with $q$ odd the greedy algorithm should give no more than $3$ Egyptian fractions and with $q$ even no more than $5$ Egyptian fractions for your hypothesis to hold true for $n=5$.

In the last case if the Erdős-Straus conjecture is proved true then the maximum number of Egyptian fractions needed can be reduced to 4 I think for $n=5$, but I don't think you need this level of analysis to prove your hypothesis wrong in general.

For any value $n$ you can find values of $m$ which will give a split into $2$ Egyptian fractions and $3$ and so on.

$\endgroup$

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.