Задача 535
Фрактальная последовательность

Рассмотрим бесконечную последовательность S, начинающуюся так:
S = 1, 1, 2, 1, 3, 2, 4, 1, 5, 3, 6, 2, 7, 8, 4, 9, 1, 10, 11, 5, ...

Выделим для каждого целого числа его первое появление в последовательности:
S = 1, 1, 2, 1, 3, 2, 4, 1, 5, 3, 6, 2, 7, 8, 4, 9, 1, 10, 11, 5, ...

Этой последовательности характерны следующие свойства:

  • Выделенные числа - последовательные целые числа, начиная с 1.
  • Непосредественно перед каждым невыделенным числом ai находится ровно └√ai┘ прилегающих выделенных чисел, где └ ┘ - функция пола.
  • Если убрать все выделенные числа из последовательности, оставшиеся в ней числа сформируют последовательность, идентичную S. Таким образом, S - это фрактальная последовательность.

Пусть T(n) будет суммой первых n элементов этой последовательности.
Вам дано, что T(1) = 1, T(20) = 86, T(103) = 364089 и T(109) = 498676527978348241.

Найдите T(1018). В качестве ответа приведите последние 9 цифр полученного числа.

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