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


# Input: a non-negative integer, $n
# Output: an array of size $n + 1 such that the nth-mobius number is .[$n]
# i.e. $n|mobius_array[-1]
# For example, the first mobius number could be evaluated by 1|mobius_array[-1].
def mobius_array:
  . as $n
  | ($n|sqrt) as $sqrt
  | reduce range(2; 1 + $sqrt) as $i ([range(0; $n + 1) | 1];
       if .[$i] == 1
       then # for each factor found, swap + and -
         reduce range($i; $n + 1; $i) as $j (.; .[$j] *= -$i) 
         | ($i*$i) as $isq #  square factor = 0
         | reduce range($isq; $n + 1; $isq) as $j (.; .[$j] = 0 )
       else .
       end )
  | reduce range(2; 1 + $n) as $i (.;
       if   .[$i] ==  $i then .[$i] = 1
       elif .[$i] == -$i then .[$i] = -1
       elif .[$i]  <   0 then .[$i] = 1
       elif .[$i]  >   0 then .[$i] = -1
       else .[$i] = 0                   # avoid "-0"
       end);
 
# For one-off computations:
def mu($n): $n | mobius_array[-1];