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 one find the prime factors of a positive integer n and define μ(n) as the sum of the primitive nth roots of unity. It has values in {−1, 0, 1} depending on the factorization of n into prime factors:
- μ(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
- Related Tasks
Perl 6
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) };
- 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