Задача 443
Последовательность НОД

Пусть g(n) будет последовательностью, определенной следующим образом:
g(4) = 13,
g(n) = g(n-1) + НОД(n, g(n-1)) для n > 4.

Вот первые несколько значений последовательности:

n4567891011121314151617181920...
g(n)1314161718272829303132333451545560...

Вам дано, что g(1 000) = 2524 и g(1 000 000) = 2624152.

Найдите g(1015).

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