Engel Expansion - Engel Expansions of Rational Numbers

Engel Expansions of Rational Numbers

Every positive rational number has a unique finite Engel expansion. In the algorithm for Engel expansion, if u_i is a rational number x/y, then u_i+1 = (−y mod x)/y. Therefore, at each step, the numerator in the remaining fraction u_i decreases and the process of constructing the Engel expansion must terminate in a finite number of steps. Every rational number also has a unique infinite Engel expansion: using the identity

the final digit n in a finite Engel expansion can be replaced by an infinite sequence of (n + 1)s without changing its value. For example

This is analogous to the fact that any rational number with a finite decimal representation also has an infinite decimal representation (see 0.999...).

Erdős, Rényi, and Szüsz asked for nontrivial bounds on the length of the finite Engel expansion of a rational number x/y; this question was answered by Erdős and Shallit, who proved that the number of terms in the expansion is O(y1/3 + ε) for any ε > 0.