Fibonacci's Greedy Algorithm

Algorithm

Let $\dfrac p q$ denote a proper fraction expressed in canonical form.

Fibonacci's greedy algorithm is a greedy algorithm which calculates a sequence of distinct unit fractions which together sum to $\dfrac p q$:

$\ds \dfrac p q$

$=$

$\ds \sum_{\substack {1 \mathop \le k \mathop \le m \\ n_j \mathop \le n_{j + 1} } } \dfrac 1 {n_k}$

$\ds $

$=$

$\ds \dfrac 1 {n_1} + \dfrac 1 {n_2} + \dotsb + \dfrac 1 {n_m}$

$(1) \quad$ Let $p = x_0$ and $q = y_0$ and set $k = 0$.

$(2) \quad$ Is $x_k = 1$? If so, the algorithm has finished.

$(3) \quad$ Find the largest unit fraction $\dfrac 1 {m_k}$ less than $\dfrac {x_k} {y_k}$.

$(4) \quad$ Calculate $\dfrac {x_{k + 1} } {y_{k + 1} } = \dfrac {x_k} {y_k} - \dfrac 1 {m_k}$ expressed in canonical form.

$(5) \quad$ Go to step $(2)$.

This entry was named for Leonardo Fibonacci.