← 完整题目索引

PROJECT EULER · #0337

欧拉函数阶梯数列

Totient Stairstep Sequences

仅题目 · 待解原题 ↗

令 {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(10000)mod108=73808307。

求 S(20000000)mod108。

1 ϕ 表示欧拉函数。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。