Задача 319
Ограниченные последовательности

Пусть x_(1), x_(2),..., x_(n) - последовательность длиной n, для которой справедливо:

  • x_(1 ) = 2
  • x_(i-1 ) < x_(i) при всех 1 < i < n
  • (x_(i))^( j) < (x_(j) + 1)^(i ) для всех i и j при 1 ≤ i, jn

Существует всего пять таких последовательностей длиной 2, а именно: {2,4}, {2,5}, {2,6}, {2,7} и {2,8}.
Существует 293 такие последовательности длиной 5. Ниже представлены три примера:
{2,5,11,25,55}, {2,6,14,36,88}, {2,8,22,64,181}.

Обозначим через t(n) число таких последовательностей длиной n.
Известно, что t(10) = 86195 и t(20) = 5227991891.

Найдите t(10^(10)) и приведите ответ по модулю 10^(9).

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