---

Problem 337

---

Totient Stairstep Sequences

Let {a₁, a₂,…, a_n} be an integer sequence of length n such that:

• a₁ = 6
• for all 1 ≤ i < n : φ(a_i) < φ(a_i+1) < a_i < a_i+1 ¹

Let S(N) be the number of such sequences with a_n ≤ N.
For example, S(10) = 4: {6}, {6, 8}, {6, 8, 9} and {6, 10}.
We can verify that S(100) = 482073668 and S(10 000) mod 10⁸ = 73808307.

Find S(20 000 000) mod 10⁸.

¹ φ denotes Euler’s totient function.

---

总计函数台阶序列

记{a₁, a₂,…, a_n}是长度为n且满足以下条件的整数序列：

• a₁ = 6
• 对于所有1 ≤ i < n：φ(a_i) < φ(a_i+1) < a_i < a_i+1 ¹

记S(N)为满足a_n ≤ N的这类序列的数目。
例如，S(10) = 4：{6}、{6, 8}、{6, 8, 9}和{6, 10}。
我们可以验证S(100) = 482073668以及S(10 000) mod 10⁸ = 73808307。

求S(20 000 000) mod 10⁸。

¹ φ表示欧拉总计函数.

---