Задача 558
Иррациональное основание

Пусть r будет вещетсвенным корнем уравнения x3 = x2 + 1.
Каждое положительное целое число может быть записано как сумма различных увеличивающихся степеней числа r.
Если мы потребуем, чтобы количество членов было конечно и разница между любыми двумя показателями степени была не меньше трех, тогда такое представление будет уникальным.
Например, 3 = r -10 + r -5 + r -1 + r 2 и 10 = r -10 + r -7 + r 6.
Любопытно, что это соотношение сохраняется и для комплексных корней уравнения.

Пусть w(n) будет количеством членов в таком уникальном представлении числа n. Таким образом, w(3) = 4 и w(10) = 3.

Более строго говоря, для всех положительных целых чисел n мы имеем:
n = $\displaystyle \sum_{k=-\infty}^{\infty}$ bk rk
при следующих условиях:
bk равно 0 или 1 для всех k;
bk + bk+1 + bk+2 ≤ 1 для всех k;
w(n) = $\displaystyle \sum_{k=-\infty}^{\infty}$ bk конечно.

Пусть S(m) = $\displaystyle \sum_{j=1}^{m}$ w(j2).
Вам дано, что S(10) = 61 и S(1000) = 19403.

Найдите S(5 000 000).

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