メビウス関数
$ m\ddot{o}bius function
ウムラウト打てないw
$ \mu(n)=\sum^n_{k=1,(k,n)=1}\exp({2\pi i k\over n})
参考:
基本対称式
$ \prod(1+x_1)(1+x_2)\cdots=1+\sum x_i+\sum_{i>j}x_ix_j+\cdots =\sum_n e(n; x_1,x_2,\cdots)
同次対称式
$ \prod{1\over(1-x_1)(1-x_2)\cdots}=1+\sum x_i+\sum_{i\geq j}x_ix_j+\cdots=\sum_n h(n; x_1,x_2,\cdots)
基本対称式の方の符号を反転させて、辺々積を取ると、
$ 1=(\sum_n e(n; -x_1,-x_2,\cdots)(\sum_n h(n; x_1,x_2,\cdots)=\sum_n\sum_k e(n;-x_i)h(n-k;x_i)
つまり、$ n\neq0 に対して、
$ 0=\sum_k e(n;-x_i)h(n-k;x_i)
符号がおかしいかもw
code:fortran
module m_moebius
implicit none
real, parameter :: pi = 4 * atan(1.0)
contains
pure elemental integer function igcd(ia, ib)
integer, value :: ia, ib
igcd = ia
do
if (ib == 0) exit
igcd = ib
ib = mod(ia, ib)
ia = igcd
end do
end function igcd
pure elemental integer function moebius(n)
integer, intent(in) :: n
integer :: k
real :: x
x = 0.0
do k = 1, n
if (igcd(k, n) == 1) x = x + cos(2 * pi * k / n)
end do
moebius = nint(x)
end function moebius
end module m_moebius