The Moebius function is one of the fundamental functions in number theory and has been the subject of few recent conjectures: see here and here.
It is defined as \[ \mu(n) = \begin{cases} 1 & \text{ if } n=1\\ (-1)^k & \text{ if $n=p_1\cdots p_k$ where $p_i$'s are distinct primes}\\ 0 & \text{ otherwise} \end{cases} \]
Today, I will give a recursive definition of \(\mu\) which does not require you to factor \(n\), or use a variation of Sieve of Eratosthenes. In fact, the only thing you have to know is \(\mu(1)\).
Since the inner sum \(\sum_{m=q}^n\nu(m,q) = \left\lfloor\frac{n}{q}\right\rfloor\) we get \[ 1 = \sum_{q=1}^n\mu(q)\left\lfloor\frac{n}{q}\right\rfloor \] By re-arranging the terms we get \[ \mu(n) = 1 - \sum_{q=1}^{n-1}\left\lfloor\frac{n}{q}\right\rfloor\mu(q) \] We know that \(\mu(1)=1\). See if we can get \(\mu(i)\) correctly for \(i=2,3,4\):
\[ \mu(2) = 1 - 2\mu(1) = -1 \]
\[ \mu(3) = 1 - 3\mu(1) - \mu(2) = 1 - 3 + 1 = -1 \]
\[ \mu(4) = 1 - 4\mu(1) - 2\mu(2) - \mu(3) = 1 - 4 + 2 + 1 = 0 \]
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
long int *mu_arr;
int mu(long int n) {
long int j, res, temp;
res = mu_arr[n];
if(res!=-2)
return(res);
res = 0;
for(j=1;j<n;j++) {
temp = mu_arr[j];
if(temp == -2)
res += (int)(floor(n/j))*mu(j);
else
res += (int)(floor(n/j))*temp;
}
res = 1-res;
mu_arr[n] = res;
return(res);
}
int main(int argc, char *argv[]) {
long int n, i, j;
long int res;
if(argc<1)
return(0);
n = atoll(argv[1]);
mu_arr = (long *)malloc((n+1)*sizeof(long));
for(i=0;i<=n;i++)
mu_arr[i]=-2;
mu_arr[1] = 1;
for(i=1;i<=n;i++)
printf("mu(%d) = %d\n",i,mu(i));
free(mu_arr);
return(1);
}I was not aware of such an additively recursive definition of \(\mu(n)\). The time complexity of the implementation is slightly worse than \(\mathcal{O}(n^2)\). Since I am using only the four basic arithmetic operations, if-then conditionals, and bounded for loops in the algorithm with recursive calls, it is easy to see that \(\mu(n)\) must be primitive recursive.