1 / 1

337 : トーティエント階段数列

$\{a_1, a_2,\dots, a_n\}$ を次のような長さ $n$ の整数列とする.

$a_1 = 6$
$1 \leq i < n$ に対し : $φ(a_i) < φ(a_{i+1}) < a_i < a_{i+1}$

$a_n \leq N$ となる数列の数を $S(N)$ とする. 例えば $S(10) = 4$ である：{6}, {6, 8}, {6, 8, 9}, {6, 10}. $S(100) = 482073668$ と $S(10\, 000) \mod 10^8 = 73808307$ であることが確かめられる.

$S(20\, 000\, 000) \mod 10^8$ を求めよ.

注： $φ$ はオイラーのトーティエント関数を表す.

337 : トーティエント階段数列

$\{a_1, a_2,\dots, a_n\}$ を次のような長さ $n$ の整数列とする.

$a_1 = 6$
$1 \leq i < n$ に対し : $φ(a_i) < φ(a_{i+1}) < a_i < a_{i+1}$

$S(20\, 000\, 000) \mod 10^8$ を求めよ.

注： $φ$ はオイラーのトーティエント関数を表す.