yaworsw/euler-manager

---
:id: 337
:name: Totient Stairstep Sequences
:url: https://projecteuler.net/problem=337
:content: "Let {a<sub>1</sub>, a<sub>2</sub>,..., a<sub><var>n</var></sub>} be an
  integer sequence of length <var>n</var> such that:\n\n- a<sub>1</sub> = 6\n- for
  all 1 ≤ <var>i</var> \\< <var>n</var> : φ(a<sub><var>i</var></sub>) \\< φ(a<sub><var>i</var>+1</sub>)
  \\< a<sub><var>i</var></sub> \\< a<sub><var>i</var>+1</sub><sup>1</sup>\n\nLet S(<var>N</var>)
  be the number of such sequences with a<sub><var>n</var></sub> ≤ <var>N</var>.  \nFor
  example, S(10) = 4: {6}, {6, 8}, {6, 8, 9} and {6, 10}.  \nWe can verify that S(100)
  = 482073668 and S(10 000) mod 10<sup>8</sup> = 73808307.\n\nFind S(20 000 000) mod
  10<sup>8</sup>.\n\n<sup>1</sup> φ denotes **Euler's totient function**.\n\n"