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

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

Константа Эрдёша — Борвейна  — математическая константа, равная сумме обратных величин чисел Мерсенна. Названа по именам Пала Эрдёша и Питера Борвейна (англ. Peter Borwein), установившим её ключевые свойства.

По определению константа равна:

E=\sum_{n=1}^{\infty}\frac{1}{2^n-1}

что приблизительно составляет 1, 606 695 152 415 291 763 783 301 523 190 924 580 480 579 671 505 756 435 778 079 553 691 418 420 743 486 690 565 711 801 670 155 576…[1].

Эквивалентные формы[править | править вики-текст]

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


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}
,

где \sigma_0(n) = d(n) — мультипликативная функция делителей, равная числу положительных делителей числа n. Для доказательства эквивалентности этих используется факт, что все они представляют ряд Ламберта[2].

Иррациональность[править | править вики-текст]

Эрдёш в 1948 году показал, что константа является иррациональным числом[3]. Позднее Борвейн представил альтернативное доказательство[4].

Несмотря на иррациональность, двоичное представление константы эффективно вычисляется: Кнут в издании 1998 года «Искусства программирования» заметил, что вычисление можно осуществить с использованием ряда Клаузена, который сходится очень быстро[5].

Приложения[править | править вики-текст]

Константа Эрдёша — Борвейна возникает при анализе поведения алгоритма пирамидальной сортировки.[6]

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

  1. последовательность A065442 в OEIS
  2. Первая из этих формул была представлена Кнутом в 1998 году; Кнут ссылается при этом на работу 1828 года Томаса Клаузена
  3. Erdős, Pal (1948), "«On arithmetical properties of Lambert series»", J. Indian Math. Soc. (N.S.) Т. 12: 63–66, <http://www.renyi.hu/~p_erdos/1948-04.pdf> 
  4. Borwein, Peter B. (1992), "«On the irrationality of certain series»", Mathematical Proceedings of the Cambridge Philosophical Society Т. 112 (1): 141–146, DOI 10.1017/S030500410007081X 
  5. Крэндалл, Ричард (2012), "«The googol-th bit of the Erdős–Borwein constant»", Integers Т. 12: A23, DOI 10.1515/integers-2012-0007 
  6. Кнут, Дональд (1998), «The Art of Computer Programming, Vol. 3: Sorting and Searching» (2nd ed.), Reading, MA: Addison-Wesley, сс. 153–155 .

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