Задача 101: Оптимальный полином
Если нам представить первые k членов последовательности, то с уверенностью нельзя сказать значение следующего члена, так как существует бесконечно много полиномиальных функций, которые могут моделировать последовательность. В качестве примера рассмотрим последовательность чисел куба. Это определяется производящей функцией, un = n3: 1, 8, 27, 64, 125, 216, ... Предположим, что нам дали только первые два члена этой последовательности. Работая над принципом, что «просто лучше», мы должны принять линейную зависимость и предсказать, что следующий термин будет равен 15 (общая разница 7). Даже если нам были представлены первые три термина, по тому же принципу простоты, следует принять квадратичную зависимость. Будем определять OP (k, n) как n-й член оптимальной производящей полиномы функции для первых k членов последовательности. Должно быть ясно, что OP (k, n) будет точно генерировать члены последовательности для n ≤ k, и потенциально первый неправильный член (FIT) будет OP (k, k + 1); в этом случае мы будем называть это плохим OP (BOP). В качестве основы, если бы нам дали только первый член последовательности, было бы разумнее предполагать постоянство; т. е. при n ≥ 2, OP (1, n) = u1. Следовательно, для кубической последовательности мы получаем следующие OP:
OP (1, n) = 1 1, 1, 1, 1, ... OP (2, n) = 7n-6 1, 8, 15, ... OP (3, n) = 6n2-11n + 6 1, 8, 27, 58, ... OP (4, n) = n3 1, 8, 27, 64, 125, ...
Очевидно, что для k ≥ 4 не существует BOP. Рассматривая сумму FIT, генерируемых BOP (указанную красным выше), получаем 1 + 15 + 58 = 74. Рассмотрим следующую производящую функцию многочлена десятой степени: un = 1 - n + n2 - n3 + n4 - n5 + n6 - n7 + n8 - n9 + n10 Найти сумму FIT для BOP.