{a&sub{1};, a&sub{2};,..., an} を次のような長さ n の 整数列とする.
an ≤ N となる数列の数を S(N) とする.
例えば, S(10) = 4 である:{6}, {6, 8}, {6, 8, 9}, {6, 10}.
S(100) = 482073668 と S(10 000) mod 10&sup{8}; = 73808307 であることが確かめられる.
S(20 000 000) mod 10&sup{8}; を求めよ.
&sup{1}; φはオイラーのトーティエント関数を表す.