Problem 464 「メビウス関数と区間」

メビウス関数μ(n) で表され, 次のように定義される:

  • μ(n) = (-1)ω(n), n が無平方の場合 (ここで ω(n) は n の相異なる素因数の数)
  • μ(n) = 0, n が無平方でない場合

区間 [a,b] 内で μ(n) = 1 となるような整数 n の個数を P(a,b) としよう.
区間 [a,b] 内で μ(n) = -1 となるような整数 n の個数を N(a,b) としよう.
例えば, P(2,10) = 2, N(2,10) = 4.

以下のような整数の組 (a,b) の個数を C(n) としよう:

  • 1 ≤ abn
  • 99·N(a,b) ≤ 100·P(a,b)
  • 99·P(a,b) ≤ 100·N(a,b)

例として, C(10) = 13, C(500) = 16676, そして C(10 000) = 20155319.

C(20 000 000) を求めよ.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2014-03-23 (日) 13:49:28 (1101d)