HiCode2009's blog

By HiCode2009, history, 2 years ago, In English

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 years ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

Before asking, you should probably check small cases yourself to determine if there is an obvious counterexample.

Trying $$$\frac{1}{4} + \frac{1}{7} = \frac{11}{28}$$$ yields a greedy answer of $$$\frac{11}{28} = \frac{1}{3} + \frac{1}{17} + \frac{1}{1428}$$$, which is not optimal. So the greedy algorithm clearly doesn't work.