Задача 101
Оптимальный многочлен

Если нам известны первые k членов некоторой последовательности, то это еще не значит, что мы сможем с уверенностью определить значение следующего члена, поскольку существует бесконечное множество полиномиальных функций, которыми можно описать такую последовательность.

К примеру, рассмотрим последовательность чисел-кубов. Такую последовательность можно определить образующей функцией:
u_(n) = n^(3): 1, 8, 27, 64, 125, 216, ...

Предположим, что нам известны только два первых члена такой последовательности. Руководствуясь принципом "чем проще, тем лучше", мы предполагаем линейную зависимость и предсказываем следующее значение равным 15 (общая разность равна 7). Даже если нам известны первые три члена последовательности, согласно тому же принципу простоты, следует предположить квадратичную зависимость.

Определим OP(k, n) как n-ый член оптимальной полиномиальной образующей функции для первых k членов последовательности. Очевидно, что OP(k, n) даст точные значения членов последовательности при nk, а первым неверным членом будет OP(k, k+1). В таком случае полиномиальную функцию назовем плохой.

В частности, если бы нам был известен только первый член последовательности, наиболее разумным было бы предположить постоянство; т.е. при n ≥ 2, OP(1, n) = u_(1).

Таким образом, получим следующие значения OP(k, n) для последовательности кубов:

OP(1, n) = 1 1, 1, 1, 1, ...
OP(2, n) = 7n−6 1, 8, 15, ...
OP(3, n) = 6n^(2)−11n+6      1, 8, 27, 58, ...
OP(4, n) = n^(3) 1, 8, 27, 64, 125, ...

Понятно, что при k ≥ 4 не существует ни одной плохой полиномиальной функции.

Рассмотрим сумму значений первых неверных членов, которые образованы плохими полиномиальными функциями (отмечены выше красным). Получим: 1 + 15 + 58 = 74.

Дана следующая полиномиальная образующая функция 10-й степени:

u_(n) = 1 − n + n^(2)n^(3) + n^(4)n^(5) + n^(6)n^(7) + n^(8)n^(9) + n^(10)

Найдите сумму значений первых неверных членов, которые образованы плохими полиномиальными функциями.

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