Полином. Олимпиадная задача

Об этой задаче мне рассказал коллега по программированию из Венгрии. Ответа не было и пришлось самому рвануть. Конечно, полином четвертой степени можно раскусить и методом Феррари или методом неопределенных коэффициентов, приведя к уравнению:

(x^2-2.3x+0.6)*(x^2-1.7x+0.66)=0.

Но решил делать более просто и быстро. Благо техника сейчас на порядки выше, чем сорок пять лет назад. Раз дан полином, то прежде всего черчу график. Графопостроителей в инете больше, чем звезд на небе. Все показано на рисунке.

Итак, выяснил, что все четыре корня действительные и они компактно расположены в положительной зоне. Это уже радует. Второй этап - выявление точных значений корней. Метод итерации Ньютона - самый оптимальный инструмент для меня. Составляю формулу, что под графиком на рисунке и пишу программу:

for n=1 to 4
for x=1 to 100
y=x^4-4.0*x^3+5.17*x^2-2.538*x+0.396
if y=0 then
print x,y
fi
next x
print
print "INPUT x0 = ";
input x0
for i=1 to 15
f=x0^4-4*x0^3+5.17*x0^2-2.538*x0+0.396
f1=4*x0^3-12*x0^2+10.34*x0-2.538
x=x0-f/f1
if abs(x-x0)>1/10^12 then
print x,x0
x0=x
fi
next i
next n

Программа работает так, что нужно последовательно вводить четыре приближенных корня, а уже за доли секунды прокручиваются пятнадцать итерационных циклов и выводится с огромной точностью результат. Вот полный текст на мониторе:


INPUT x0 = ?0.2
0.270588 0.2
0.296348 0.270588
0.299933 0.296348
0.3 0.299933
0.3 0.3

INPUT x0 = ?0.5
0.636364 0.5
0.600109 0.636364
0.6 0.600109
0.6 0.6

INPUT x0 = ?1
1.14141 1
1.10298 1.14141
1.10002 1.10298
1.1 1.10002
1.1 1.1

INPUT x0 = ?1.8
2.28276 1.8
2.1003 2.28276
2.01828 2.1003
2.00076 2.01828
2 2.00076
2 2
2 2

Получились следующие корни:
х1=0.3
х2=0.6
х3=1.1
х4=2

Как я понял из условия задачи, нужно догадаться, какой же последовательности пропорциональны эти четыре корня.
Слово "последовательность" у меня ассоциируется, конечно, с целочисленной последовательностью. В инете даже есть сайт числовых последовательностей oeis.org, где их буквально сотни тысяч. Если не больше. В результате прихожу к такому набору целых чисел:

3  6  11  20

Что это? Завожу их в окно oeis.org и сайт выдаёт мне десять вариантов. Но самый первый, имеющий индекс A001590 - это хорошо мне знакомые Числа Трибоначчи! Каждое последующее число равно сумме трёх предыдущих. Начало, правда, не совсем стандартное:

0, 1, 0, 1, 2, 3, 6, 11, 20 , 37, 68, 125,...

Как видим, наши четыре числа присутствуют полностью. Задача решена!
Хотя можно выудить ещё одну функциональную зависимость (индекс последовательности А006127):

a(n)=2^n+n

Подставляя n=0, 1, 2, 3,... получим ряд

1, 3, 6, 11, 20, 37, 70, 135, ...

Задание даже перевыполнено - имеем два простых разных решения, сыграны две Венгерские рапсодии!


11 августа 2021 г.