Функция F(n), где n — неотрицательное целое число, задана следующими соотношениями:
F(0) = 0;
F(n) = F(n − 1) + 2n − 1, если
F(n) = 4F(n / 2), если
Известно, что F(a) − F(b) = 1001. Найдите наибольшее возможное значение разности a − b.
Для примера найдем значение F(5):
Рассмотрим значение F(6):
То есть алгоритм считает квадрат числа. Составим программу на языке Python для поиска ответа.
Приведём решение на языке Python.
otv = 0
for a in range(1000):
for b in range(1000):
if a**2 - b**2 == 1001:
otv = max(otv, a-b)
print(otv)
Ответ: 13.
Приведём решение Данила Лукиных на языке Python.
d = list([0] * 100)
j = 0
for i in range(1, 100):
d[i] = i ** 2
a = d[i] - 1001
ans = False
while d[j] <= a:
if ans := a == d[j]:
print(i - j)
break
j+=1
if ans:
break