Задача 545
Формула Фолхабера

Сумма k-тых степеней первых n натуральных чисел может быть выражена как многочлен степени k+1 с рациональными коэффициентами - формула Фолхабера:
$1^k + 2^k + ... + n^k = \sum_{i=1}^n i^k = \sum_{i=1}^{k+1} a_{i} n^i = a_{1} n + a_{2} n^2 + ... + a_{k} n^k + a_{k+1} n^{k + 1}$,
где ai - рациональные коэффициенты, которые можно записать в виде несократимых дробей pi/qi (если ai = 0, будем считать qi = 1).

Например, $1^4 + 2^4 + ... + n^4 = -\frac 1 {30} n + \frac 1 3 n^3 + \frac 1 2 n^4 + \frac 1 5 n^5.$

Определим D(k) как значение q1 для суммы k-тых степеней (т.е. знаменатель несократимой дроби a1).
Определим F(m) как m-тое значение k ≥ 1, для которого D(k) = 20010.
Известно, что D(4) = 30 (так как a1 = -1/30), D(308) = 20010, F(1) = 308, F(10) = 96404.

Найдите F(105).

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net