0%

Problem 337


Problem 337


Totient Stairstep Sequences

Let {a1, a2,…, an} be an integer sequence of length n such that:

  • a1 = 6
  • for all 1 ≤ i < n : φ(ai) < φ(ai+1) < ai < ai+1 1

Let S(N) be the number of such sequences with an ≤ 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 108 = 73808307.

Find S(20 000 000) mod 108.

1 φ denotes Euler’s totient function.


总计函数台阶序列

记{a1, a2,…, an}是长度为n且满足以下条件的整数序列:

  • a1 = 6
  • 对于所有1 ≤ i < n:φ(ai) < φ(ai+1) < ai < ai+1 1

记S(N)为满足an ≤ N的这类序列的数目。
例如,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 φ表示欧拉总计函数.