Mobius number

The nth Mobius number is given by the piecewise function:

       /  0      if n has any repeated factors
       |
       /
u(n) = |  1      if n=1
       \
       |      k
       \  (-1)   if n is a product of k distinct primes

The first several values of u(n) (n=1,2,3,...) are u(n)=1, -1, -1, 0, -1, 1, ... Mobius numbers are multiplicative, i.e.:

         /  u(m)*u(n)  if gcd(m,n)=1
u(m*n) = |
         \  0          otherwise

All information gathered from http://mathworld.wolfram.com/MoebiusFunction.html

The nth Mobius number is shown as μ(n).

Mobius numbers are often first encountered in Riemann's estimate for the number of primes less than N. This estimate is of the form:

R(N) = Li(N) - ½Li(N^½) - 1/3·Li(N^1/3) + ...

Evidently, the nth term of this sequence is

        1
 μ(n) · - · Li( N1/n )
        n

Because μ(n) includes 0 in its range, some of these terms do not really appear at all, as seen in the brief expansion above. Otherwise, the Mobius numbers are simply used to determine the sign of the term.

And now an original thought from me: in terms of algorithm design, isn't it quicker to find all the primes up to N than have to generate the Mobius numbers? Unless of course, you had them calculated at compile time.