Angel evolution

The Engel development of a positive real number x is the monotonically increasing, unique sequence of natural numbers , so that ${\displaystyle \{a_{1},a_{2},a_{3},\dots \}}$

${\displaystyle x={\frac {1}{a_{1}}}+{\frac {1}{a_{1}a_{2}}}+{\frac {1}{a_{1}a_{2}a_{3}}}+\cdots .\;}$

Rational numbers have a finite angel expansion, while irrational numbers are infinite. If x is rational, the Engel expansion of x leads to an Egyptian fraction , that is, a finite sum of reciprocal values ​​of natural numbers. The Engel development was named after Friedrich Engel , who examined it in 1913.

Angel sequences, continued fractions and Fibonacci

Kraaikamp and Wu observed in 2004 that an angel development can also be written as an ascending variant of a continued fraction :

${\displaystyle x={\frac {\displaystyle 1+{\frac {\displaystyle 1+{\frac {\displaystyle 1+\cdots }{\displaystyle a_{3}}}}{\displaystyle a_{2}}}}{\displaystyle a_{1}}}.}$

They show that ascending continued fractions like these were already examined in Fibonacci's Liber Abaci of 1202. This is how a connection can be established between a general continued fraction development, the ascending continued fraction development and the Engel development:

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

If in such a representation all denominators are 0 or 1, as often occurs in Liber Abaci, the result is an angel development. The angel development has not yet been described as a general procedure by Fibonacci.

Algorithm for calculating Engel developments

To find the angel expansion of x , put

${\displaystyle u_{1}=x,}$

${\displaystyle a_{k}=\left\lceil {\frac {1}{u_{k}}}\right\rceil ,}$

and continue as follows:

${\displaystyle u_{k+1}=u_{k}a_{k}-1}$

where is the rounding function (the smallest integer not less than r ). ${\displaystyle \left\lceil r\right\rceil }$

If for any i , stop executing. ${\displaystyle u_{i}=0}$

example

To find the angel expansion of 1.175, we perform the following steps:

${\displaystyle u_{1}=1{,}175,a_{1}=\left\lceil {\frac {1}{1{,}175}}\right\rceil =1;\,}$

${\displaystyle u_{2}=u_{1}a_{1}-1=1{,}175\cdot 1-1=0{,}175,a_{2}=\left\lceil {\frac {1}{0{,}175}}\right\rceil =6\,}$

${\displaystyle u_{3}=u_{2}a_{2}-1=0{,}175\cdot 6-1=0{,}05,a_{3}=\left\lceil {\frac {1}{0{,}05}}\right\rceil =20\,}$

${\displaystyle u_{4}=u_{3}a_{3}-1=0{,}05\cdot 20-1=0\,}$

The episode ends here. So is

${\displaystyle 1{,}175={\frac {1}{1}}+{\frac {1}{1\cdot 6}}+{\frac {1}{1\cdot 6\cdot 20}}}$

and the angel expansion of 1.175 is {1, 6, 20}.

Angel developments from rational numbers

Every positive rational number has a unique finite angelic development. In the algorithm, if u _{i is} a rational number x / y , then u _{i +1} = (- y mod x ) / y . The numerator in the remaining fraction u _i decreases and the construction of the Engel expansion must terminate in a finite number of steps. Every rational number also has a unique, infinite angelic development: with identity

${\displaystyle {\frac {1}{n}}=\sum _{r=1}^{\infty }{\frac {1}{(n+1)^{r}}}.}$

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

${\displaystyle 1{,}175=\{1,6,20\}=\{1,6,21,21,21,\dots \}.\;\;}$

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

Erdős , Rényi , and Szüsz asked about nontrivial limits for the length of a finite angel expansion of a rational number x / y ; Erdős and Shallit answered this question by proving that the number of terms in the expansion is O ( y ^{1/3 + ε} ) for every ε> 0.

Rate of growth of the terms

The coefficients a _i typically grow exponentially; more precisely, the limit exists for almost all numbers in the interval (0,1] and is equivalent to e . The subset of the interval for which this is not the case is still large enough that its Hausdorff dimension is 1. ${\displaystyle \lim _{n\rightarrow \infty }a_{n}^{1/n}}$

The same typical growth rate also applies to the terms in the greedy algorithm for Egyptian fractions. The proportion of real numbers in the interval (0.1) whose Engel expansion coincides with their Greedy expansion approaches 0, and the set has the Hausdorff dimension 1/2.

Further examples

${\displaystyle \pi =\{1,1,1,8,8,17,19,300,1991,2492,\dots \}\;}$OEIS: A006784

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

In general,

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

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

${\displaystyle 1=\{2,2,2,2,2,\dots \}.\;}$

In general, an angel expansion with constant terms is a geometric series . Further Engel developments for constants can be found on the page of the On-Line Encyclopedia of Integer Sequences .

literature

• F. Engel: Development of the numbers after family breaks . In: Negotiations of the 52nd Assembly of German Philologists and School Men in Marburg 1913, pp. 190–191.
• TA Pierce: On an algorithm and its use in approximating roots of algebraic equations . In: Am. Math. Monthly . 36, No. 10, 1929, pp. 523-525.
• Paul Erdős, Alfréd Rényi, Peter Szüsz: On Engel's and Sylvester's series . In: Ann. Univ. Sci. Budapest. Eötvös Sect. Math. . 1, 1958, pp. 7-32. .
• Paul Erdős, Jeffrey Shallit: New bounds on the length of finite Pierce and Engel series . In: Journal de théorie des nombres de Bordeaux . 3, No. 1, 1991, pp. 43-53. doi : 10.5802 / jtnb.41 .
• J. Paradis, P. Viader, L. Bibiloni: Approximation to quadratic irrationals and their Pierce expansions . In: Fib. Quart. . 36, No. 2, 1998, pp. 146-153.
• Cor Kraaikamp, ​​Jun Wu: On a new continued fraction expansion with non-decreasing partial quotients . In: Monthly books for mathematics . 143, No. 4, 2004, pp. 285-298. doi : 10.1007 / s00605-004-0246-3 .
• Jun Wu: A problem of Galambos on Engel expansions . In: Acta Arithmetica . 92, No. 4, 2000, pp. 383-386.
• Jun Wu: How many points have the same Engel and Sylvester expansions? . In: Journal of Number Theory . 103, No. 1, 2003, pp. 16-26. doi : 10.1016 / S0022-314X (03) 00017-9 .

Web links

• Weisstein, Eric W : Engel Expansion . MathWorld – A Wolfram Web Resource. Retrieved September 20, 2013.

• On-Line Encyclopedia of Integer Sequences