Константа Эрдеша – Борвейна

Константа Эрдеша-Борвейна , названная в честь Пауля Эрдеша и Питера Борвейна , представляет собой сумму обратных Мерсенна чисел .

По определению это:

$E=\sum _{n=1}^{\infty }{\frac {1}{2^{n}-1}}\approx 1.606695152415291763\dots$

Эквивалентные формы

Можно доказать, что все следующие формы в сумме дают одну и ту же константу:

$E=\sum _{n=1}^{\infty }{\frac {1}{2^{n^{2}}}}{\frac {2^{n}+1}{2^{n}-1}}$

$E=\sum _{m=1}^{\infty }\sum _{n=1}^{\infty }{\frac {1}{2^{mn}}}$

$E=1+\sum _{n=1}^{\infty }{\frac {1}{2^{n}(2^{n}-1)}}$

$E=\sum _{n=1}^{\infty }{\frac {\sigma _{0}(n)}{2^{n}}}$

где σ0 ₍ n ) = d ( n ) — функция делителя , мультипликативная функция , равная количеству положительных делителей числа n . Чтобы доказать эквивалентность этих сумм, заметим, что все они имеют форму рядов Ламберта и, следовательно, могут быть суммированы как таковые.

Иррациональность

В 1948 году Эрдеш показал, что константа E — иррациональное число . Позже Борвейн предоставил альтернативное доказательство.

Несмотря на свою иррациональность, двоичное представление константы Эрдеша – Борвейна можно эффективно вычислить.

Приложения

Константа Эрдеша-Борвейна возникает при анализе среднего случая алгоритма пирамидальной сортировки , где она контролирует постоянный коэффициент во времени выполнения преобразования неотсортированного массива элементов в кучу.

Внешние ссылки

• Вайсштейн, Эрик В. «Константа Эрдоша-Борвейна» . Математический мир .