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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Разложение Энгеля положительного вещественного числа x — это единственная неубывающая последовательность положительных натуральных чисел , таких что

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

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

Разложение Энгеля, непрерывные дроби и Фибоначчи[править | править вики-текст]

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

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

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

Алгоритм для вычисления разложений Энгеля[править | править вики-текст]

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

и

,

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

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

Пример[править | править вики-текст]

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

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

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

Разложение Энгеля рациональных чисел[править | править вики-текст]

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

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

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

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

Разложение Энгеля для некоторых хорошо известных констант[править | править вики-текст]

= {1, 1, 1, 8, 8, 17, 19, 300, 1991, 2492,...} (последовательность A006784 в OEIS)
= {1, 3, 5, 5, 16, 18, 78, 102, 120, 144,...} (последовательность A028254 в OEIS)
= {1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,...} (последовательность A000027 в OEIS)

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

Скорость роста элементов разложения[править | править вики-текст]

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

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

Примечания[править | править вики-текст]

  1. Kraaikamp, Wu, 2004.
  2. Erdős, Rényi, Szüsz, 1958.
  3. Erdős, Shallit, 1991.
  4. Wu, 2000, По утверждению Ву, результат о равенстве предела e для почти всех чисел принадлежит Яношу Галамбосу (Janos Galambos).
  5. Wu, 2003.

Литература[править | править вики-текст]

  • F. Engel. Verhandlungen der 52. Versammlung deutscher Philologen und Schulmaenner in Marburg. — 1913. — С. 190—191.
  • T. A. Pierce On an algorithm and its use in approximating roots of algebraic equations // Am. Math. Monthly. — 1929. — Т. 36, № 10. — С. 523—525.
  • Paul Erdős, Alfréd Rényi, Peter Szüsz On Engel's and Sylvester's series // Ann. Univ. Sci. Budapest. Eötvös Sect. Math.. — 1958. — Т. 1. — С. 7—32.
  • Paul Erdős, Jeffrey Shallit New bounds on the length of finite Pierce and Engel series // Journal de théorie des nombres de Bordeaux. — 1991. — Т. 3, вып. 1. — С. 43—53. — DOI:10.5802/jtnb.41.
  • J. Paradis, P. Viader, L. Bibiloni Approximation to quadratic irrationals and their Pierce expansions // Fib. Quart.. — 1998. — Т. 36, № 2. — С. 146—153.
  • Cor Kraaikamp, Jun Wu On a new continued fraction expansion with non-decreasing partial quotients // Monatshefte für Mathematik. — 2004. — Т. 143, вып. 4. — С. 285—298. — DOI:10.1007/s00605-004-0246-3.
  • Jun Wu A problem of Galambos on Engel expansions // Acta Arithmetica. — 2000. — Т. 92, вып. 4. — С. 383—386.
  • Jun Wu How many points have the same Engel and Sylvester expansions? // Journal of Number Theory. — 2003. — Т. 103, вып. 1. — С. 16—26. — DOI:10.1016/S0022-314X(03)00017-9.

Ссылки[править | править вики-текст]