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

NT Part 1:GCD, LCM, Euclidean Algorithm

The definitions of GCD and LCM are well-known, (and taught in middle school I think) I will skip the definitions. Also, since , calculating GCD is equivalent to calculating LCM. Now, how do we calculate the GCD of two numbers? A naive solution would be iterating over all positive integers no more than . This will get the GCD in , very very slow. We can calculate the GCD of in using Euclidean Algorithm. This algorithm uses the easy-to-prove fact , where is the remainder when is divided by , or just a%b. We can now use the following code. #include <iostream> using namespace std ; int gcd ( int u, int v ) { return u % v == 0 ? v : gcd ( v,u % v ) ; } int main ( void ) { int x, y ; cin >> x >> y ; cout << gcd ( x,y ) ; } How do we prove that this algorithm is ? Well, let's suppose that we started with . Then...

NT Part 5: Mobius Function Part 2. Mobius Inversion, Dirichlet Convolution

Theorem. Let be arithmetic function such that . Then, . Proof. using for all and . The Dirichlet Convolution of two function is the following. Denote as the constant function, . is a function which satisfies and for . is the identity function, The mobius inversion formula and the basic property of mobius functions give , and Okay. So what? How can we use this formula to improve our lives solve problems? We can, change our "sum" or our answer using mobius inversion and mobius functions to calculate them fast. I will give 3 examples which changes the desired sum by using number theory (like mobius function) to calculate them fast. Example Problems Problem 1. http://www.spoj.com/problems/LCMSUM/ Let be the answer when . Precalculate , and add to every . ...

This lifeless coder is welcoming you!

Search This Blog