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

Разложение Энгеля положительного вещественного числа x — это единственная неубывающая последовательность положительных натуральных чисел {a1,a2,a3,}, таких что
x=1a1+1a1a2+1a1a2a3+.
Рациональные числа имеют конечное разложение Энгеля, а иррациональные числа имеют разложение в бесконечный ряд. Если x рационально, его разложение Энгеля даёт представление x в виде египетской дроби. Разложение названо именем математика Фридриха Энгеля, изучавшего его в 1913 году. Разложение, аналогичное разложению Энгеля, но с попеременным знаком членов называется разложением Пирса.

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

Краайкамп и Ву заметили, что разложение Энгеля можно записать в виде восходящего варианта непрерывной дроби:
x=1+1+1+a3a2a1.
Они утверждают, что восходящие непрерывные дроби, подобные этой, изучались ещё во времена книги абака Фибоначчи (1202). Это утверждение ссылается на нотацию сложных дробей Фибоначчи, в которых последовательность числителей и знаменателей, использующие одну общую черту, представляют восходящую непрерывную дробь:
a b c de f g h=d+c+b+aefgh.
Если в этой нотации все числители равны 0 или 1, как появляется в некоторых местах в книге абака, результатом будет разложение Энгеля. Однако разложение Энгеля как техника в книге не описано.

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

Чтобы найти разложение Энгеля для x, положим
u1=x,
ak=1uk,
и
uk+1=ukak1
, где r — потолок (наименьшее целое, не меньшее r). Если ui=0 для некоторого i, останавливаем алгоритм.

Пример

Чтобы найти разложение Энгеля для числа 1,175, осуществим следующие шаги.
u1=1,175,a1=11,175=1;
u2=u1a11=1,17511=0,175,a2=10,175=6
u3=u2a21=0,17561=0.05,a3=10,05=20
u4=u3a31=0,05201=0
Последовательность закончилась. Таким образом,
1,175=11+116+11620
и разложение Энгеля для 1,175 равно \{1, 6, 20\}.

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

Любое положительное рациональное число имеет единственное конечное разложение Энгеля. В алгоритме разложения Энгеля, если ui является рациональным числом x/y, то ui+1 = (−y mod x)/y. Таким образом, каждый шаг уменьшает числитель в остаточной дроби ui и процесс построения разложения Энгеля должен прекратиться за конечное число шагов. Любое рациональное число также имеет единственное бесконечное разложение Энгеля: используя равенство
1n=r=11(n+1)r.
последнее число n в конечном разложении Энгеля можно заменить бесконечной последовательностью (n + 1) без изменения значения. Например,
1,175={1,6,20}={1,6,21,21,21,}.
Это аналогично факту, что любое рациональное число с конечным десятичным представлением имеет бесконечное десятичное представление (см. 0,(9)). Бесконечное разложение Энгеля, в котором все элементы равны, это геометрическая прогрессия. Эрдёш, Реньи и Сюс (Szüsz) задавали вопрос о нетривиальных границах длины конечного разложения Энгеля рациональной дроби x/y. На этот вопрос ответили Эрдёш и доказав, что число членов разложения равно O(y1/3 + ε) для любого ε \textgreater 0.

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

π
= \{1, 1, 1, 8, 8, 17, 19, 300, 1991, 2492,...\}
2
= \{1, 3, 5, 5, 16, 18, 78, 102, 120, 144,...\}
e
= \{1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,...\}
e1/r1={1r,2r,3r,4r,5r,6r,}
Другие разложения Энгеля можно найти здесь.

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

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