2009年01月13日

ナノピコ教室:メビウス関数(2)

  

さて、素数が求まったので、これを使ってメビウス関数を定義してみる。

メビウス関数とは、

(1) μ(1) = 1
(2) μ(n) = 0 (n が平方因子を持つ(平方数で割り切れる)とき)
(3) μ(n) = (-1)**k (n が相異なる k 個の素因数に分解されるとき)
     n が相異なる偶数個の素数の積ならば μ(n) = 1
     n が相異なる奇数個の素数の積ならば μ(n) = -1
     **は累乗を表す。

とのことです。

素数と同じように、配列を使って求めたいと思います。

まず、配列を 1 で初期化。
それから、
2,3,6,8,9...
3,6,9,12,15...
5,15,20,25,30...
...
の位置の要素に、-1を掛けていきます。これで、

  n が相異なる偶数個の素数の積ならば μ(n) = 1
  n が相異なる奇数個の素数の積ならば μ(n) = -1

の部分を求めます。
さらに、
4,8,12,16,20...
9,18,27,36... 
25,50,75...
...
の要素(素数の2乗で割りきれる数)には、0を代入して、
  n が平方因子を持つ(平方数で割り切れる)ときμ(n) = 0
を求めます。

2以上の数で、上記どれにも該当しなかいのはあり得ないので、配列のすべてにメビウス関数の値が設定されることになります。

今回は、数字を列挙するのはなく、整数 n を与えると、メビウス関数の値が戻ってくるような形にしようと思います。
単独のstaticメソッドとして定義するのは、配列を使った今回の方式だと効率がよくないので、Mebiusクラスとして定義しました。

 static class Mebius {
     static int maxnum = 100;
     static int[] mebius;
     static Mebius() {
         mebius = Enumerable.Repeat(1, maxnum + 1).ToArray();
         foreach (int p in Primes(maxnum)) {
             for (int i = p; i <= maxnum; i += p)
                 mebius[i] *= -1;
             int p2 = p * p;
             for (int pp = p2; pp <= maxnum; pp += p2)
                 mebius[pp] = 0;
         }
     }
     public static int Get(int n) {
         return mebius[n];
     }
 }

Primesメソッドは省略


 Mebius.Get(30)

のようにして値を得ます。


なお、範囲チェックはやってません。

※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式出版社)に掲載されている問題をGushwellが独自にC#で解いたものです。



 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/51726738