Return to Answer

I also like thisone, $\mathcal{O}(N \ln N)$ additions being not so different of $\mathcal{O}(N \ln \ln N)$ multiplications :

% N(1+ln N) additions/affectations. an array of 2 bits elements would be enough !

% matlab 
function mu = computeMu(N)
    mu = -ones(1,N); mu(1) = 1;
    for n = 2:N
        mu(n+n:n:end) = mu(n+n:n:end) - mu(n);
    end
end

// C++/java/C#
char[] computeMu(int N) {
   char[] mu = new char[N+1];
   mu[0] = 0; mu[1] = 1; for (int n = 2; n <= N; n++) mu[n] = -1;
   for (int n = 2; n <= N; n++) {
       if (mu[n]) {
           for (int m = n+n; m <= N; m += n) mu[m] -= mu[n];
       }
   }
   return mu;
}

I'll leave you as an exercice to prove that it effectly computes $\mu(n)$

$$ \left(\sum_n \mu_n n^0 \right) \left(\sum_m m^0 \right) = \sum_n n^0 \sum_{d | n} \mu_d$$

I also like thisone, $\mathcal{O}(N \ln N)$ additions being not so different to $\mathcal{O}(N \ln \ln N)$ multiplications

% N(1+ln N) additions/affectations. an array of 2 bits elements would be enough

% matlab 
function mu = computeMu(N)
    mu = zeros(1,N); mu(1) = 1; 
    % Will compute the Dirichlet inverse of any sequence starting with 1
    for n = 1:N
        mu(n+n:n:end) = mu(n+n:n:end) - mu(n);
    end
end

I also like thisone, $\mathcal{O}(N \ln N)$ additions being not so different of $\mathcal{O}(N \ln \ln N)$ multiplications :

% N(1+ln N) additions/affectations. an array of 2 bits elements would be enough !

% matlab 
function mu = computeMu(N)
    mu = -ones(1,N); mu(1) = 1;
    for n = 2:N
        mu(n+n:n:end) = mu(n+n:n:end) - mu(n);
    end
end

// C++/java/C#
char[] computeMu(int N) {
   char[] mu = new char[N+1];
   mu[0] = 0; mu[1] = 1; for (int n = 2; n <= N; n++) mu[n] = -1;
   for (int n = 2; n <= N; n++) {
       for (int m = n+n; m <= N; m += n) mu[m] -= mu[n];
   }
   return mu;
}

I'll leave you as an exercice to prove that it effectly computes $\mu(n)$

$$ \left(\sum_n \mu_n n^0 \right) \left(\sum_m m^0 \right) = \sum_n n^0 \sum_{d | n} \mu_d$$

I also like thisone, $\mathcal{O}(N \ln N)$ additions being not so different of $\mathcal{O}(N \ln \ln N)$ multiplications :

% N(1+ln N) additions/affectations. an array of 2 bits elements would be enough !

% matlab 
function mu = computeMu(N)
    mu = -ones(1,N); mu(1) = 1;
    for n = 2:N
        mu(n+n:n:end) = mu(n+n:n:end) - mu(n);
    end
end

// C++/java/C#
char[] computeMu(int N) {
   char[] mu = new char[N+1];
   mu[0] = 0; mu[1] = 1; for (int n = 2; n <= N; n++) mu[n] = -1;
   for (int n = 2; n <= N; n++) {
       if (mu[n]) {
           for (int m = n+n; m <= N; m += n) mu[m] -= mu[n];
       }
   }
   return mu;
}

I'll leave you as an exercice to prove that it effectly computes $\mu(n)$

$$ \left(\sum_n \mu_n n^0 \right) \left(\sum_m m^0 \right) = \sum_n n^0 \sum_{d | n} \mu_d$$

I also like thisone, sometimes $\mathcal{O}(N \ln N)$ additions is better than $\mathcal{O}(N \ln \ln N)$ multiplications :

% N(1+ln N) additions/affectations. if a given precision integer is enough or not depends on
% the riemann hypothesis !!!!

% matlab 
function mu = computeMu(N)
    mu = -ones(1,N); mu(1) = 1;
    for n = 2:N
        mu(n+n:n:end) = mu(n+n:n:end) - mu(n);
    end
end

// C++/java/C#
int[] computeMu(int N) {
   int[] mu = new int[N+1];
   mu[0] = 0; mu[1] = 1; for (int n = 2; n <= N; n++) mu[n] = -1;
   for (int n = 2; n <= N; n++) {
       for (int m = n+n; m <= N; m += n) mu[m] -= mu[n];
   }
   return mu;
}

I'll leave you as an exercice to prove that it effectly computes $\mu(n)$

$$ \left(\sum_n \mu_n n^0 \right) \left(\sum_m m^0 \right) = \sum_n n^0 \sum_{d | n} \mu_d$$

I also like thisone, $\mathcal{O}(N \ln N)$ additions being not so different of $\mathcal{O}(N \ln \ln N)$ multiplications :

% N(1+ln N) additions/affectations. an array of 2 bits elements would be enough !

% matlab 
function mu = computeMu(N)
    mu = -ones(1,N); mu(1) = 1;
    for n = 2:N
        mu(n+n:n:end) = mu(n+n:n:end) - mu(n);
    end
end

// C++/java/C#
char[] computeMu(int N) {
   char[] mu = new char[N+1];
   mu[0] = 0; mu[1] = 1; for (int n = 2; n <= N; n++) mu[n] = -1;
   for (int n = 2; n <= N; n++) {
       for (int m = n+n; m <= N; m += n) mu[m] -= mu[n];
   }
   return mu;
}

I'll leave you as an exercice to prove that it effectly computes $\mu(n)$

$$ \left(\sum_n \mu_n n^0 \right) \left(\sum_m m^0 \right) = \sum_n n^0 \sum_{d | n} \mu_d$$