Задача 337
Ступенчатые последовательности фи-функций

Пусть {a1, a2,..., an} - последовательность целых чисел длиной n, для которой справедливо:

  • a1 = 6
  • для любых 1 ≤ i < n : φ (ai) < φ(ai+1) < a i < ai+1 1

Обозначим через S(N) число таких последовательностей, у которых a nN.
К примеру, S(10) = 4: {6}, {6, 8}, {6, 8, 9} и {6, 10}.
Можно убедиться, что S(100) = 482073668 и S(10 000) mod 108 = 73808307.

Найдите S(20 000 000) mod 108.

1 φ обозначена фи-функция Эйлера.

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