Skip to main content

NT Part 4: Mobius Function Part 1. The Introduction

 What is mobius function? This function is notated as $\mu (n)$. This function has lots of definitions.

However, the main definition is the following.

$\mu (n)$ is $1$ if $n=1$ or $n$ is square-free and has even number of prime divisors.
$\mu (n)$ is $-1$ if $n$ is square-free and has odd number of prime divisors.
$\mu (n)$ is $0$ if $n$ is not square-free.

$\mu (n)$ also has a lot of interesting properties that make $\mu (n)$ so important.

$\sum_{d|n} \mu (d) = 0$ for all $n>1$, and $\mu (n)$ is multiplicative.
(A function $f$ is multiplicative if $f(mn)=f(m)f(n)$ for all $(m,n)=1$.)

How do we calculate $\mu (n)$ fast? Again, we can tweak the Eratosthenes's Sieve a little bit.

void preprocess(void)
{
    int i, j;
    for(i=1 ; i<=111100 ; i++)
    {
        mu[i]=1;
        primechk[i]=1;
    }
    primechk[1]=0;
    for(i=2 ; i<=111100 ; i++)
    {
        if(primechk[i]==1)
        {
            mu[i]=-mu[i];
            for(j=2 ; i*j<=111100 ; j++)
            {
                primechk[i*j]=0;
                if(j%i==0)
                {
                    mu[i*j]=0;  
                }   
                else
                {
                    mu[i*j]=-mu[i*j];
                }
            }   
        }   
    }
}


Okay, $O(n \log \log n)$ is good. Now, how do we use $\mu (n)$?

Comments

Post a Comment