The classical Möbius function: μ(n) is an important multiplicative function in number theory and combinatorics.

There are several ways to implement a Möbius function.

A fairly straightforward method is to find the prime factors of a positive integer n, then define μ(n) based on the sum of the primitive factors. It has the values {−1, 0, 1} depending on the factorization of n:

 μ(1) is defined to be 1.
 μ(n) = 1 if n is a square-free positive integer with an even number of prime factors.
 μ(n) = −1 if n is a square-free positive integer with an odd number of prime factors.
 μ(n) = 0 if n has a squared prime factor.


Task

 Write a routine (function, procedure, whatever) μ(n) to find the Möbius number for a positive integer n.
 Use that routine to find and display here, on this page, at least the first 99 terms in a grid layout. (Not just one long line or column of numbers.)


See also

 Wikipedia: Möbius function


Related Tasks

 Mertens function


 
# syntax: GAWK -f MOBIUS_FUNCTION.AWK
# converted from Java
BEGIN {
    printf("first 199 terms of the mobius sequence:\n   ")
    for (n=1; n<200; n++) {
      printf("%3d",mobius(n))
      if ((n+1) % 20 == 0) {
        printf("\n")
      }
    }
    exit(0)
}
function mobius(n,  i,j,mu_max) {
    if (n in MU) {
      return(MU[n])
    }
    mu_max = 1000000
    for (i=0; i<mu_max; i++) { # populate array
      MU[i] = 1
    }
    for (i=2; i<=int(sqrt(mu_max)); i++ ) {
      if (MU[i] == 1) {
        for (j=i; j<=mu_max; j+=i) { # for each factor found, swap + and -
          MU[j] *= -i
        }
        for (j=i*i; j<=mu_max; j+=i*i) { # square factor = 0
          MU[j] = 0
        }
      }
    }
    for (i=2; i<=mu_max; i++) {
      if (MU[i] == i) {
        MU[i] = 1
      }
      else if (MU[i] == -i) {
        MU[i] = -1
      }
      else if (MU[i] < 0) {
        MU[i] = 1
      }
      else if (MU[i] > 0) {
        MU[i] = -1
      }
    }
    return(MU[n])
}
 