Разложение Энгеля

Разложение Энгеля положительного вещественного числа x — это единственная неубывающая последовательность положительных натуральных чисел $\{a_1,a_2,a_3,\dots \}$, таких что

$x=\frac{1}{a_1}+\frac{1}{a_1{a}_2}+\frac{1}{a_1{a}_2{a}_3}+\cdots .$

Рациональные числа имеют конечное разложение Энгеля, а иррациональные числа имеют разложение в бесконечный ряд. Если x рационально, его разложение Энгеля даёт представление x в виде египетской дроби. Разложение названо именем математика Фридриха Энгеля, изучавшего его в 1913 году.

Разложение, аналогичное разложению Энгеля, но с попеременным знаком членов, называется разложением Пирса.

Разложение Энгеля, непрерывные дроби и Фибоначчи

Краайкамп и ВуШаблон:Sfn заметили, что разложение Энгеля можно записать в виде восходящего варианта непрерывной дроби:

$x=\frac{1+\frac{1+\frac{1+\cdots }{a_3}}{a_2}}{a_1}.$

Они утверждают, что восходящие непрерывные дроби, подобные этой, изучались ещё во времена книги абака Фибоначчи (1202). Это утверждение ссылается на нотацию сложных дробей Фибоначчи, в которых последовательность числителей и знаменателей, использующие одну общую черту, представляют восходящую непрерывную дробь:

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

Если в этой нотации все числители равны 0 или 1, как появляется в некоторых местах в книге абака, результатом будет разложение Энгеля. Однако разложение Энгеля как техника в книге не описано.

Алгоритм для вычисления разложений Энгеля

Чтобы найти разложение Энгеля для x, положим

$u_1=x,$

$a_k=\lceil \frac{1}{u_k}\rceil ,$

и

$u_{k+1}=u_k{a}_k-1$,

где $\lceil r\rceil$ — потолок (наименьшее целое, не меньшее r).

Если $u_i=0$ для некоторого i, останавливаем алгоритм.

Пример

Чтобы найти разложение Энгеля для числа 1,175, осуществим следующие шаги.

$u_1=1,175,a_1=\lceil \frac{1}{1,175}\rceil =1;$

$u_2=u_1{a}_1-1=1,175\cdot 1-1=0,175,a_2=\lceil \frac{1}{0,175}\rceil =6$

$u_3=u_2{a}_2-1=0,175\cdot 6-1=0,05,a_3=\lceil \frac{1}{0,05}\rceil =20$

$u_4=u_3{a}_3-1=0,05\cdot 20-1=0$

Последовательность закончилась. Таким образом,

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

и разложение Энгеля для 1,175 равно {1, 6, 20}.

Разложение Энгеля рациональных чисел

Любое положительное рациональное число имеет единственное конечное разложение Энгеля. В алгоритме разложения Энгеля, если u_i является рациональным числом x/y, то u_i+1 = (−y mod x)/y. Таким образом, каждый шаг уменьшает числитель в остаточной дроби u_i и процесс построения разложения Энгеля должен прекратиться за конечное число шагов. Любое рациональное число также имеет единственное бесконечное разложение Энгеля: используя равенство

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

последнее число n в конечном разложении Энгеля можно заменить бесконечной последовательностью (n + 1) без изменения значения. Например,

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

Это аналогично факту, что любое рациональное число с конечным десятичным представлением имеет бесконечное десятичное представление (см. 0,(9)). Бесконечное разложение Энгеля, в котором все элементы равны, это геометрическая прогрессия.

Эрдёш, Реньи и Сюс (Szüsz) задавали вопрос о нетривиальных границах длины конечного разложения Энгеля рациональной дроби x/y. На этот вопрос ответили Эрдёш и Шаблон:Не переведено 5 доказав, что число членов разложения равно O(y^{1/3 + ε}) для любого ε > 0Шаблон:SfnШаблон:Sfn.

Разложение Энгеля для некоторых хорошо известных констант

$\pi$ = {1, 1, 1, 8, 8, 17, 19, 300, 1991, 2492,...} (Шаблон:OEIS)

$\sqrt{2}$ = {1, 3, 5, 5, 16, 18, 78, 102, 120, 144,...} (Шаблон:OEIS)

$e$ = {1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,...} (Шаблон:OEIS)

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

Другие разложения Энгеля можно найти здесь.

Скорость роста элементов разложения

Коэффициенты a_i разложения Энгеля, как правило, имеют экспоненциальный рост. Точнее, для почти всех чисел в интервале (0,1] предел $\underset{n\to \mathrm{\infty }}{\lim }{a}_n^{1/n}$ существует и равен e. Однако подмножество интервала, для которого это не выполняется, достаточно велико, так что его размерность Хаусдорфа равна единицеШаблон:Sfn.

Тот же типичный рост наблюдается у членов, генерируемых жадным алгоритмом для египетских дробей. Однако множество вещественных чисел в интервале (0,1], разложение Энгеля которых совпадает с их разложением жадным алгоритмом, имеет меру ноль и Хаусдорфову размерность 1/2Шаблон:Sfn.

Литература

• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья

Ссылки

• Шаблон:Cite web