# Engel expansion

Engel expansion

The Engel expansion of a positive real number "x" is the unique non-decreasing sequence of positive integers $\left\{a_1,a_2,a_3,dots\right\}$ such that

:$x=frac\left\{1\right\}\left\{a_1\right\}+frac\left\{1\right\}\left\{a_1a_2\right\}+frac\left\{1\right\}\left\{a_1a_2a_3\right\}+cdots.;$

Rational numbers have a finite Engel expansion, while irrational numbers have an infinite Engel expansion. If "x" is rational, its Engel expansion provides a representation of "x" as an Egyptian fraction. Engel expansions are named after Friedrich Engel, who studied them in 1913.

An expansion analogous to an Engel expansion, in which alternating terms are negative, is called a Pierce expansion.

Engel expansions, continued fractions, and Fibonacci

Kraaikamp and Wu (2004) observe that an Engel expansion can also be written as an ascending variant of a continued fraction:

:$x = frac\left\{displaystyle 1+frac\left\{displaystyle 1+frac\left\{displaystyle 1+cdots\right\}\left\{displaystyle a_3\left\{displaystyle a_2\left\{displaystyle a_1\right\}.$

They claim that ascending continued fractions such as this have been studied as early as Fibonacci's Liber Abaci (1202). This claim appears to refer to Fibonacci's compound fraction notation in which a sequence of numerators and denominators sharing the same fraction bar represents an ascending continued fraction:

:$frac\left\{a b c d\right\}\left\{e f g h\right\} = dfrac\left\{d+dfrac\left\{c+dfrac\left\{b+dfrac\left\{a\right\}\left\{e\left\{f\left\{g\left\{h\right\}.$

If such a notation has all numerators 0 or 1, as occurs in several instances in Liber Abaci, the result is an Engel expansion. However, Engel expansion as a general technique does not seem to be described by Fibonacci.

Algorithm for computing Engel expansions

To find the Engel expansion of "x", let

:$u_1=x,$

:$a_k=left lceil frac\left\{1\right\}\left\{u_k\right\} ight ceil,$

and

:$u_\left\{k+1\right\}=u_ka_k-1$

where $left lceil r ight ceil$ is the ceiling function (the smallest integer not less than "r").

If $u_i=0$ for any "i", halt the algorithm.

Example

To find the Engel expansion of 1.175, we perform the following steps.

:$u_1 = 1.175, a_1=left lceil frac\left\{1\right\}\left\{1.175\right\} ight ceil = 1;$

:$u_2 = u_1a_1-1=1.175cdot1-1=0.175, a_2=leftlceilfrac\left\{1\right\}\left\{0.175\right\} ight ceil=6$

:$u_3 = u_2a_2-1=0.175cdot6-1=0.05, a_3=leftlceilfrac\left\{1\right\}\left\{0.05\right\} ight ceil=20$

:$u_4 = u_3a_3-1=0.05cdot20-1=0$

The series ends here. Thus,

:$1.175=frac\left\{1\right\}\left\{1\right\}+frac\left\{1\right\}\left\{1cdot6\right\}+frac\left\{1\right\}\left\{1cdot6cdot20\right\}$

and the Engel expansion of $1.175$ is $\left\{1,6,20\right\};$

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 "u""i"+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

:$frac\left\{1\right\}\left\{n\right\}=sum_\left\{r=1\right\}^\left\{infty\right\}frac\left\{1\right\}\left\{\left(n+1\right)^r\right\}.$

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

:$1.175=\left\{1,6,20\right\}=\left\{1,6,21,21,21,dots\right\}.;;$

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("y"1/3 + &epsilon;) for any &epsilon; &gt; 0. [harvtxt|Erdős|Rényi|Szüsz|1958; harvtxt|Erdős|Shallit|1991.]

Engel expansions for some well-known constants

:$pi=\left\{1, 1, 1, 8, 8, 17, 19, 300, 1991, 2492, dots\right\};$ OEIS|id=A006784

:$e=\left\{1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, dots\right\};$ OEIS|id=A000027

And in general,

:$e^\left\{1/r\right\}-1=\left\{1r, 2r, 3r, 4r, 5r, 6r, dots\right\};$

:$sqrt\left\{2\right\}=\left\{1,3,5,5,16,18,78,102,120,144, dots\right\};$ OEIS|id=A028254

:$1=\left\{2,2,2,2,2, dots\right\};$

In general, an Engel expansion with constant terms is a geometric series.More Engel expansions for constants can be found [http://www.research.att.com/~njas/sequences/Sindx_El.html#Engel here] .

Notes

References

*citation
last = Engel | first = F.
contribution = Entwicklung der Zahlen nach Stammbruechen
title = Verhandlungen der 52. Versammlung deutscher Philologen und Schulmaenner in Marburg
pages = 190–191
year = 1913
.

*citation
authorlink1 = Paul Erdős| last1 = Erdős | first1 = Paul
authorlink2 = Alfréd Rényi | last2 = Rényi | first2 = Alfréd
last3 = Szüsz | first3 = Peter
title = On Engel's and Sylvester's series
journal = Ann. Univ. Sci. Budapest Eötvös Sect. Math.
volume = 1
year = 1958
pages = 7–32
.

*citation
authorlink1 = Paul Erdős| last1 = Erdős | first1 = Paul
authorlink2 = Jeffrey Shallit | last2 = Shallit | first2 = Jeffrey
title = New bounds on the length of finite Pierce and Engel series
journal = Journal de théorie des nombres de Bordeaux
volume = 3 | issue = 1 |year = 1991 | pages = 43–53
url = http://jtnb.cedram.org/item?id=JTNB_1991__3_1_43_0
id = MathSciNet | id = 1116100
.

*citation
last1 = Kraaikamp | first1 = Cor | last2 = Wu | first2 = Jun
title = On a new continued fraction expansion with non-decreasing partial quotients
journal = Monatshefte für Mathematik
year = 2004
volume = 143
pages = 285–298
doi = 10.1007/s00605-004-0246-3
.

* cite web
author = Weisstein, Eric W
title = Engel Expansion
publisher = MathWorld–A Wolfram Web Resource
url = http://mathworld.wolfram.com/EngelExpansion.html

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Engel — means angel in German, Danish, Dutch, Norwegian and Afrikaans and may refer to: * Engel (song), performed by Rammstein * Engel (role playing game), a 2002 role playing game * Engel (band), Swedish industrial/melodic death metal band *Engel group… …   Wikipedia

• Friedrich Engel (mathematician) — Infobox Scientist box width = name = Friedrich Engel image size = caption = birth date = birth date|1861|12|26 birth place = Lugau, Saxony, Germany death date = death date and age|1941|9|29|1861|12|26 death place = Giessen, Hessen, Germany… …   Wikipedia

• Développement en série de Engel — Le développement en série de Engel d un nombre réel positif y, moins connu que son développement en fraction continue mais étroitement lié, est son expression sous la forme (essentiellement unique) où les ak forment une suite croissante d entiers …   Wikipédia en Français

• Egyptian fraction — An Egyptian fraction is the sum of distinct unit fractions, such as frac{1}{2}+ frac{1}{3}+ frac{1}{16}. That is, each fraction in the expression has a numerator equal to 1 and a denominator that is a positive integer, and all the denominators… …   Wikipedia

• Greedy algorithm for Egyptian fractions — In mathematics, an Egyptian fraction is a representation of an irreducible fraction as a sum of unit fractions, as e.g. 5/6 = 1/2 + 1/3. As the name indicates, these representations have been used as long ago as ancient Egypt, but the first… …   Wikipedia

• List of mathematics articles (E) — NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… …   Wikipedia

• Wurzel 2 — Unter Wurzel 2 (Quadratwurzel aus 2) versteht man in der Mathematik diejenige positive Zahl, deren Quadrat die Zahl 2 ergibt, also die Zahl x > 0, für die x2 = 2 gilt. Diese Zahl ist eindeutig bestimmt, irrational und wird durch dargestellt.… …   Deutsch Wikipedia

• Continued fraction — Finite continued fraction, where a0 is an integer, any other ai are positive integers, and n is a non negative integer. In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the… …   Wikipedia

• Natural logarithm of 2 — The decimal value of the natural logarithm of 2 (sequence A002162 in OEIS) is approximately as shown in the first line of the table below. The logarithm in other bases is obtained with the formula The common logarithm in particular is ( …   Wikipedia

• Jeffrey Shallit — Jeffrey Outlaw Shallit (born October 17, 1957) is a computer scientist, number theorist, and a noted advocate for civil liberties on the Internet. He is married to Anna Lubiw, also a computer scientist. Early life and education Shallit was born… …   Wikipedia