Engel Expansions of Rational Numbers
Every positive rational number has a unique finite Engel expansion. In the algorithm for Engel expansion, if ui is a rational number x/y, then ui+1 = (−y mod x)/y. Therefore, at each step, the numerator in the remaining fraction ui 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.
Read more about this topic: Engel Expansion
Famous quotes containing the words engel, rational and/or numbers:
“Now folks, I hereby declare the first church of Tombstone, which ain’t got no name yet or no preacher either, officially dedicated. Now I don’t pretend to be no preacher, but I’ve read the Good Book from cover to cover and back again, and I nary found one word agin dancin’. So we’ll commence by havin’ a dad blasted good dance.”
—Samuel G. Engel (1904–1984)
“I have always been a friend to hero-worship; it is the only rational one, and has always been in use amongst civilized people—the worship of spirits is synonymous with barbarism—it is mere fetish.... There is something philosophic in the worship of the heroes of the human race.”
—George Borrow (1803–1881)
“I’m not even thinking straight any more. Numbers buzz in my head like wasps.”
—Kurt Neumann (1906–1958)