Möbius function

Möbius function is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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) as the sum of the primitive factors. It has the values {−1, 0, 1} depending on the factorization of n:

• μ(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

Factor

The mobius word exists in the math.extras vocabulary. See the implementation here.

Works with: Factor version 0.99 2020-01-23

<lang factor>USING: formatting grouping io math.extras math.ranges sequences ;

"First 199 terms of the Möbius sequence:" print 199 [1,b] [ mobius ] map " " prefix 20 group [ [ "%3s" printf ] each nl ] each</lang>

Output:

First 199 terms of the Möbius sequence:
     1 -1 -1  0 -1  1 -1  0  0  1 -1  0 -1  1  1  0 -1  0 -1
  0  1  1 -1  0  0  1  0  0 -1 -1 -1  0  1  1  1  0 -1  1  1
  0 -1 -1 -1  0  0  1 -1  0  0  0  1  0 -1  0  1  0  1  1 -1
  0 -1  1  0  0  1 -1 -1  0  1 -1 -1  0 -1  1  0  0  1 -1 -1
  0  0  1 -1  0  1  1  1  0 -1  0  1  0  1  1  1  0 -1  0  0
  0 -1 -1 -1  0 -1  1 -1  0 -1 -1  1  0 -1 -1  1  0  0  1  1
  0  0  1  1  0  0  0 -1  0  1 -1 -1  0  1  1  0  0 -1 -1 -1
  0  1  1  1  0  1  1  0  0 -1  0 -1  0  0 -1  1  0 -1  1  1
  0  1  0 -1  0 -1  1 -1  0  0 -1  0  0 -1 -1  0  0  1  1 -1
  0 -1 -1  1  0  1 -1  1  0  0 -1 -1  0 -1  1 -1  0 -1  0 -1

Perl 6

Works with: Rakudo version 2019.11

Möbius number is not defined for n == 0. Perl 6 arrays are indexed from 0 so store a blank value at position zero to keep n and μ(n) aligned.

<lang perl6>use Prime::Factor;

sub μ (Int \n) {

   my @p = prime-factors(n);
   +@p == +Bag(@p).keys ?? +@p %% 2 ?? 1 !! -1 !! 0

}

my @möbius = lazy flat ' ', 1, (2..*).map: -> \n { μ(n) };

1. The Task

put "Möbius sequence - First 199 terms:\n",

   @möbius[^200]».fmt('%3s').rotor(20).join("\n");</lang>

Output:

Möbius sequence - First 199 terms:
      1  -1  -1   0  -1   1  -1   0   0   1  -1   0  -1   1   1   0  -1   0  -1
  0   1   1  -1   0   0   1   0   0  -1  -1  -1   0   1   1   1   0  -1   1   1
  0  -1  -1  -1   0   0   1  -1   0   0   0   1   0  -1   0   1   0   1   1  -1
  0  -1   1   0   0   1  -1  -1   0   1  -1  -1   0  -1   1   0   0   1  -1  -1
  0   0   1  -1   0   1   1   1   0  -1   0   1   0   1   1   1   0  -1   0   0
  0  -1  -1  -1   0  -1   1  -1   0  -1  -1   1   0  -1  -1   1   0   0   1   1
  0   0   1   1   0   0   0  -1   0   1  -1  -1   0   1   1   0   0  -1  -1  -1
  0   1   1   1   0   1   1   0   0  -1   0  -1   0   0  -1   1   0  -1   1   1
  0   1   0  -1   0  -1   1  -1   0   0  -1   0   0  -1  -1   0   0   1   1  -1
  0  -1  -1   1   0   1  -1   1   0   0  -1  -1   0  -1   1  -1   0  -1   0  -1