Постоянная Портера - Porters constant

В математике Постоянная Портера C возникает при изучении эффективности Евклидов алгоритм.^[1][2] Он назван в честь Дж. У. Портера из Университетский колледж, Кардифф.

Алгоритм Евклида находит наибольший общий делитель двух натуральных чисел м и п. Ганс Хайльбронн доказали, что среднее количество итераций алгоритма Евклида при фиксированных п и усреднены по всем вариантам относительно простой целые числа м < п,является

${\displaystyle {\frac {12\ln 2}{\pi ^{2}}}\ln n+o(\ln n).}$

Портер показал, что член ошибки в этой оценке является константой плюс полиномиально малая поправка, и Дональд Кнут оценил эту константу с высокой точностью. Это:

${\displaystyle {\begin{aligned}C&={{6\ln 2} \over {\pi ^{2}}}\left[3\ln 2+4\gamma -{{24} \over {\pi ^{2}}}\zeta '(2)-2\right]-{{1} \over {2}}\\[6pt]&={{{6\ln 2}((48\ln A)-(\ln 2)-(4\ln \pi )-2)} \over {\pi ^{2}}}-{{1} \over {2}}\\[6pt]&=1.4670780794\ldots \end{aligned}}}$

куда

${\displaystyle \gamma }$ это Константа Эйлера – Маскерони

${\displaystyle \zeta }$ это Дзета-функция Римана

${\displaystyle A}$ это Константа Глейшера – Кинкелина

(последовательность A086237 в OEIS )

${\displaystyle -\zeta ^{\prime }(2)={{\pi ^{2}} \over 6}\left[12\ln A-\gamma -\ln(2\pi )\right]=\sum _{k=2}^{\infty }{{\ln k} \over {k^{2}}}}$

Смотрите также

• Теорема Лохса
• Постоянная Леви

Рекомендации

1. Кнут, Дональд Э. (1976), «Оценка постоянной Портера», Компьютеры и математика с приложениями, 2 (2): 137–139, Дои:10.1016/0898-1221(76)90025-0
2. Портер, Дж. У. (1975), "Об одной теореме Хайльбронна", Математика, 22 (1): 20–28, Дои:10.1112 / S0025579300004459, МИСТЕР  0498452.