About the Egyptian fraction:How to prove that the greedy algorithm is right/wrong?

Revision en1, by HiCode2009, 2022-11-11 15:58:50

As we know,each fraction can be expressed as the sum of multiple unit fractions.

$$$\frac{p}{q}=\frac{1}{a_1}+\frac{1}{a_2}+...+\frac{1}{a_n}$$$

When we want to express a fraction as the sum of multiple unit fractions,we can use a greedy algorithm invented by Fibonacci,subtract the maximum unit fraction which is smaller than this fraction from this fraction.For example,$$$\frac{13}{14}=\frac{1}{2}+\frac{1}{3}+\frac{1}{11}+\frac{1}{231}$$$.

But when we want to find out the minimum value of $$$n$$$,things may be different.Can Fibonacci's greedy algorithm still work?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English HiCode2009 2022-11-11 15:58:50 649 Initial revision (published)