Problem 337 「トーティエント階段数列」

{a1, a2,..., an} を次のような長さ n の 整数列とする.

  • a1 = 6
  • 1 ≤ i < n に対し : φ(ai) < φ(ai+1) < ai < ai+1 1

an ≤ N となる数列の数を S(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 φはオイラーのトーティエント関数を表す.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2011-05-15 (日) 23:40:42 (2232d)