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.

Written by gamwe6 who lives and works in San Francisco building useful things. You should follow him on Twitter