I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Möbius function

From Rosetta Code
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) 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


Related Tasks

ALGOL 68[edit]

Translation of: C
BEGIN
# show the first 199 values of the moebius function #
INT sq root = 1 000;
INT mu max = sq root * sq root;
[ 1 : mu max ]INT mu;
FOR i FROM LWB mu TO UPB mu DO mu[ i ] := 1 OD;
FOR i FROM 2 TO sq root DO
IF mu[ i ] = 1 THEN
# for each factor found, swap + and - #
FOR j FROM i BY i TO UPB mu DO mu[ j ] *:= -i OD;
FOR j FROM i * i BY i * i TO UPB mu DO mu[ j ] := 0 OD
FI
OD;
FOR i FROM 2 TO UPB mu DO
IF mu[ i ] = i THEN mu[ i ] := 1
ELIF mu[ i ] = -i THEN mu[ i ] := -1
ELIF mu[ i ] < 0 THEN mu[ i ] := 1
ELIF mu[ i ] > 0 THEN mu[ i ] := -1
# ELSE mu[ i ] = 0 so no change #
FI
OD;
print( ( "First 199 terms of the möbius function are as follows:", newline, " " ) );
FOR i TO 199 DO
print( ( whole( mu[ i ], -4 ) ) );
IF ( i + 1 ) MOD 20 = 0 THEN print( ( newline ) ) FI
OD
END
Output:
First 199 terms of the möbius function are as follows:
       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

AWK[edit]

 
# 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])
}
 
Output:
first 199 terms of the mobius 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

C[edit]

Translation of: Java
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main() {
const int MU_MAX = 1000000;
int i, j;
int *mu;
int sqroot;
 
sqroot = (int)sqrt(MU_MAX);
 
mu = malloc((MU_MAX + 1) * sizeof(int));
 
for (i = 0; i < MU_MAX;i++) {
mu[i] = 1;
}
 
for (i = 2; i <= sqroot; i++) {
if (mu[i] == 1) {
// for each factor found, swap + and -
for (j = i; j <= MU_MAX; j += i) {
mu[j] *= -i;
}
// square factor = 0
for (j = i * i; j <= MU_MAX; j += i * i) {
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;
}
}
 
printf("First 199 terms of the möbius function are as follows:\n ");
for (i = 1; i < 200; i++) {
printf("%2d ", mu[i]);
if ((i + 1) % 20 == 0) {
printf("\n");
}
}
 
free(mu);
return 0;
}
Output:
First 199 terms of the m÷bius function are as follows:
     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

C++[edit]

Translation of: Java
#include <iomanip>
#include <iostream>
#include <vector>
 
constexpr int MU_MAX = 1'000'000;
std::vector<int> MU;
 
int mobiusFunction(int n) {
if (!MU.empty()) {
return MU[n];
}
 
// Populate array
MU.resize(MU_MAX + 1, 1);
int root = sqrt(MU_MAX);
 
for (int i = 2; i <= root; i++) {
if (MU[i] == 1) {
// for each factor found, swap + and -
for (int j = i; j <= MU_MAX; j += i) {
MU[j] *= -i;
}
// square factor = 0
for (int j = i * i; j <= MU_MAX; j += i * i) {
MU[j] = 0;
}
}
}
 
for (int 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];
}
 
int main() {
std::cout << "First 199 terms of the möbius function are as follows:\n ";
for (int n = 1; n < 200; n++) {
std::cout << std::setw(2) << mobiusFunction(n) << " ";
if ((n + 1) % 20 == 0) {
std::cout << '\n';
}
}
 
return 0;
}
Output:
First 199 terms of the m÷bius function are as follows:
     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

D[edit]

Translation of: C++
import std.math;
import std.stdio;
 
immutable MU_MAX = 1_000_000;
 
int mobiusFunction(int n) {
static initialized = false;
static int[MU_MAX + 1] MU;
 
if (initialized) {
return MU[n];
}
 
// populate array
MU[] = 1;
int root = cast(int) sqrt(cast(real) MU_MAX);
 
for (int i = 2; i <= root; i++) {
if (MU[i] == 1) {
// for each factor found, swap + and -
for (int j = i; j <= MU_MAX; j += i) {
MU[j] *= -i;
}
// square factor = 0
for (int j = i * i; j <= MU_MAX; j += i * i) {
MU[j] = 0;
}
}
}
 
for (int 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;
}
}
 
initialized = true;
return MU[n];
}
 
void main() {
writeln("First 199 terms of the möbius function are as follows:");
write(" ");
for (int n = 1; n < 200; n++) {
writef("%2d ", mobiusFunction(n));
if ((n + 1) % 20 == 0) {
writeln;
}
}
}
Output:
First 199 terms of the m├╢bius function are as follows:
     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

Factor[edit]

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

Works with: Factor version 0.99 2020-01-23
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
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

Fortran[edit]

Translation of: C
 
program moebius
use iso_fortran_env, only: output_unit
 
integer, parameter :: mu_max=1000000, line_break=20
integer, parameter :: sqroot=int(sqrt(real(mu_max)))
integer :: i, j
integer, dimension(mu_max) :: mu
 
mu = 1
 
do i = 2, sqroot
if (mu(i) == 1) then
do j = i, mu_max, i
mu(j) = mu(j) * (-i)
end do
 
do j = i**2, mu_max, i**2
mu(j) = 0
end do
end if
end do
 
do i = 2, mu_max
if (mu(i) == i) then
mu(i) = 1
else if (mu(i) == -i) then
mu(i) = -1
else if (mu(i) < 0) then
mu(i) = 1
else if (mu(i) > 0) then
mu(i) = -1
end if
end do
 
write(output_unit,*) "The first 199 terms of the Möbius sequence are:"
write(output_unit,'(3x)', advance="no") ! Alignment of first number
do i = 1, 199
write(output_unit,'(I2,x)', advance="no") mu(i)
if (modulo(i+1, line_break) == 0) write(output_unit,*)
end do
end program moebius
 
Output:
 The first 199 terms of the Möbius sequence are:
    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 

Go[edit]

package main
 
import "fmt"
 
func möbius(to int) []int {
if to < 1 {
to = 1
}
mobs := make([]int, to+1) // all zero by default
primes := []int{2}
for i := 1; i <= to; i++ {
j := i
cp := 0 // counts prime factors
spf := false // true if there is a square prime factor
for _, p := range primes {
if p > j {
break
}
if j%p == 0 {
j /= p
cp++
}
if j%p == 0 {
spf = true
break
}
}
if cp == 0 && i > 2 {
cp = 1
primes = append(primes, i)
}
if !spf {
if cp%2 == 0 {
mobs[i] = 1
} else {
mobs[i] = -1
}
}
}
return mobs
}
 
func main() {
mobs := möbius(199)
fmt.Println("Möbius sequence - First 199 terms:")
for i := 0; i < 200; i++ {
if i == 0 {
fmt.Print(" ")
continue
}
if i%20 == 0 {
fmt.Println()
}
fmt.Printf("  % d", mobs[i])
}
}
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

Java[edit]

 
public class MöbiusFunction {
 
public static void main(String[] args) {
System.out.printf("First 199 terms of the möbius function are as follows:%n ");
for ( int n = 1 ; n < 200 ; n++ ) {
System.out.printf("%2d ", möbiusFunction(n));
if ( (n+1) % 20 == 0 ) {
System.out.printf("%n");
}
}
}
 
private static int MU_MAX = 1_000_000;
private static int[] MU = null;
 
// Compute mobius function via sieve
private static int möbiusFunction(int n) {
if ( MU != null ) {
return MU[n];
}
 
// Populate array
MU = new int[MU_MAX+1];
int sqrt = (int) Math.sqrt(MU_MAX);
for ( int i = 0 ; i < MU_MAX ; i++ ) {
MU[i] = 1;
}
 
for ( int i = 2 ; i <= sqrt ; i++ ) {
if ( MU[i] == 1 ) {
// for each factor found, swap + and -
for ( int j = i ; j <= MU_MAX ; j += i ) {
MU[j] *= -i;
}
// square factor = 0
for ( int j = i*i ; j <= MU_MAX ; j += i*i ) {
MU[j] = 0;
}
}
}
 
for ( int 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];
}
 
}
 
Output:
First 199 terms of the möbius function are as follows:
     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  

Julia[edit]

using Primes
 
# modified from reinermartin's PR at https://github.com/JuliaMath/Primes.jl/pull/70/files
function moebius(n::Integer)
@assert n > 0
m(p, e) = p == 0 ? 0 : e == 1 ? -1 : 0
reduce(*, m(p, e) for (p, e) in factor(n) if p ≥ 0; init=1)
end
μ(n) = moebius(n)
 
print("First 199 terms of the Möbius sequence:\n ")
for n in 1:199
print(lpad(μ(n), 3), n % 20 == 19 ? "\n" : "")
end
 
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

Kotlin[edit]

Translation of: Java
import kotlin.math.sqrt
 
fun main() {
println("First 199 terms of the möbius function are as follows:")
print(" ")
for (n in 1..199) {
print("%2d ".format(mobiusFunction(n)))
if ((n + 1) % 20 == 0) {
println()
}
}
}
 
private const val MU_MAX = 1000000
private var MU: IntArray? = null
 
// Compute mobius function via sieve
private fun mobiusFunction(n: Int): Int {
if (MU != null) {
return MU!![n]
}
 
// Populate array
MU = IntArray(MU_MAX + 1)
val sqrt = sqrt(MU_MAX.toDouble()).toInt()
for (i in 0 until MU_MAX) {
MU!![i] = 1
}
for (i in 2..sqrt) {
if (MU!![i] == 1) {
// for each factor found, swap + and -
for (j in i..MU_MAX step i) {
MU!![j] *= -i
}
// square factor = 0
for (j in i * i..MU_MAX step i * i) {
MU!![j] = 0
}
}
}
for (i in 2..MU_MAX) {
when {
MU!![i] == i -> {
MU!![i] = 1
}
MU!![i] == -i -> {
MU!![i] = -1
}
MU!![i] < 0 -> {
MU!![i] = 1
}
MU!![i] > 0 -> {
MU!![i] = -1
}
}
}
return MU!![n]
}
Output:
First 199 terms of the möbius function are as follows:
     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  

Pascal[edit]

 See Mertens_function#Pascal

Perl[edit]

use utf8;
use strict;
use warnings;
use feature 'say';
use List::Util 'uniq';
 
sub prime_factors {
my ($n, $d, @factors) = (shift, 1);
while ($n > 1 and $d++) {
$n /= $d, push @factors, $d until $n % $d;
}
@factors
}
 
sub μ {
my @p = prime_factors(shift);
@p == uniq(@p) ? 0 == @p%2 ? 1 : -1 : 0;
}
 
my @möebius;
push @möebius, μ($_) for 1 .. (my $upto = 199);
 
say "Möbius sequence - First $upto terms:\n" .
(' 'x4 . sprintf "@{['%4d' x $upto]}", @möebius) =~ s/((.){80})/$1\n/gr;
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

Phix[edit]

function Moebius(integer n)
if n=1 then return 1 end if
sequence f = prime_factors(n,true)
for i=2 to length(f) do
if f[i] = f[i-1] then return 0 end if
end for
return iff(and_bits(length(f),1)?-1:+1)
end function
 
sequence s = {" ."}
for i=1 to 199 do s = append(s,sprintf("%3d",Moebius(i))) end for
puts(1,join_by(s,1,20," "))
Output:
  .   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

Raku[edit]

(formerly Perl 6)

Works with: Rakudo version 2019.11

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

use Prime::Factor;
 
sub μ (Int \n) {
return 0 if n %% 4 or n %% 9 or n %% 25 or n %% 49 or n %% 121;
my @p = prime-factors(n);
+@p == +@p.unique ?? +@p %% 2 ?? 1 !! -1 !! 0
}
 
my @möbius = lazy flat '', 1, (2..*).hyper.map: -> \n { μ(n) };
 
# The Task
put "Möbius sequence - First 199 terms:\n",
@möbius[^200]».fmt('%3s').batch(20).join: "\n";
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

REXX[edit]

Note that the   Möbius   function is also spelled   Mobius   and/or Moebius,   and it is also known as the   mu   function,   where   mu   is the Greek symbol   μ.

Programming note:   This REXX version supports the specifying of the low and high values to be generated,
as well as the group size for the grid   (it can be specified as   1   which will show a vertical list).

A null value will be shown as a bullet (•) when showing the Möbius value of for zero   (this can be changed in the 2nd line of the   mobius   function).

The above "feature" was added to make the grid to be aligned with other solutions.

The function to computer some prime numbers is a bit of an overkill, but the goal was to keep it general  (in case of larger/higher ranges for a Möbius sequence).

/*REXX pgm computes & shows a value grid of the Möbius function for a range of integers.*/
parse arg LO HI grp . /*obtain optional arguments from the CL*/
if LO=='' | LO=="," then LO= 0 /*Not specified? Then use the default.*/
if HI=='' | HI=="," then HI= 199 /* " " " " " " */
if grp=='' | grp=="," then grp= 20 /* " " " " " " */
/* ______ */
call genP HI /*generate primes up to the √ HI */
say center(' The Möbius sequence from ' LO " ──► " HI" ", max(50, grp*3), '═') /*title*/
$= /*variable holds output grid of GRP #s.*/
do j=LO to HI; $= $ right( mobius(j), 2) /*process some numbers from LO ──► HI.*/
if words($)==grp then do; say substr($, 2); $= /*show grid if fully populated,*/
end /* and nullify it for more #s.*/
end /*j*/ /*for small grids, using wordCnt is OK.*/
 
if $\=='' then say substr($, 2) /*handle any residual numbers not shown*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
mobius: procedure expose @.; parse arg x /*obtain a integer to be tested for mu.*/
if x<1 then return '∙' /*special? Then return symbol for null.*/
#= 0 /*start with a value of zero. */
do k=1; p= @.k /*get the Kth (pre─generated) prime.*/
if p>x then leave /*prime (P) > X? Then we're done. */
if p*p>x then do; #= #+1; leave /*prime (P**2 > X? Bump # and leave.*/
end
if x//p==0 then do; #= #+1 /*X divisible by P? Bump mu number. */
x= x % p /* Divide by prime. */
if x//p==0 then return 0 /*X÷by P? Then return zero*/
end
end /*k*/ /*# (below) is almost always small, <9*/
if #//2==0 then return 1 /*Is # even? Then return postive 1 */
return -1 /* " " odd? " " negative 1. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
genP: @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6= 13; nP=6 /*assign low primes; # primes.*/
do lim=nP until lim*lim>=HI /*only keep primes up to the sqrt(HI).*/
end /*lim*/
do [email protected].nP+4 by 2 to HI /*only find odd primes from here on. */
parse var j '' -1 _;if _==5 then iterate /*Is last digit a "5"? Then not prime*/
if j// 3==0 then iterate /*is J divisible by 3? " " " */
if j// 7==0 then iterate /* " " " " 7? " " " */
if j//11==0 then iterate /* " " " " 11? " " " */
if j//13==0 then iterate /* " " " " 13? " " " */
do k=7 while k*k<=j /*divide by some generated odd primes. */
if j // @.k==0 then iterate j /*Is J divisible by P? Then not prime*/
end /*k*/ /* [↓] a prime (J) has been found. */
nP= nP+1; if nP<=HI then @.nP= j /*bump prime count; assign prime to @.*/
end /*j*/; return
output   when using the default inputs:

Output note:   note the use of a bullet (•) to signify that a "null" is being shown (for the 0th entry).

══════════ The Möbius sequence from  0  ──►  199 ═══════════
 ∙  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

Sidef[edit]

Built-in:

say moebius(53)    #=> -1
say moebius(54) #=> 0
say moebius(55) #=> 1

Simple implementation:

func μ(n) {
var f = n.factor_exp.map { .tail }
f.any { _ > 1 } ? 0 : ((-1)**f.sum)
}
 
with (199) { |n|
say "Values of the Möbius function for numbers in the range 1..#{n}:"
[' '] + (1..n->map(μ)) -> each_slice(20, {|*line|
say line.map { '%2s' % _ }.join(' ')
})
}
Output:
Values of the Möbius function for numbers in the range 1..199:
    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

Wren[edit]

Library: Wren-fmt
Library: Wren-math
import "/fmt" for Fmt
import "/math" for Int
 
var isSquareFree = Fn.new { |n|
var i = 2
while (i * i <= n) {
if (n%(i*i) == 0) return false
i = (i > 2) ? i + 2 : i + 1
}
return true
}
 
var mu = Fn.new { |n|
if (n < 1) Fiber.abort("Argument must be a positive integer")
if (n == 1) return 1
var sqFree = isSquareFree.call(n)
var factors = Int.primeFactors(n)
if (sqFree && factors.count % 2 == 0) return 1
if (sqFree) return -1
return 0
}
 
System.print("The first 199 Möbius numbers are:")
for (i in 0..9) {
for (j in 0..19) {
if (i == 0 && j == 0) {
System.write(" ")
} else {
System.write("%(Fmt.dm(3, mu.call(i*20 + j))) ")
}
}
System.print()
}
Output:
The first 199 Möbius numbers are:
      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 

zkl[edit]

fcn mobius(n){
pf:=primeFactors(n);
sq:=pf.filter1('wrap(f){ (n % (f*f))==0 }); // False if square free
if(sq==False){ if(pf.len().isEven) 1 else -1 }
else 0
}
fcn primeFactors(n){ // Return a list of prime factors of n
acc:=fcn(n,k,acc,maxD){ // k is 2,3,5,7,9,... not optimum
if(n==1 or k>maxD) acc.close();
else{
q,r:=n.divr(k); // divr-->(quotient,remainder)
if(r==0) return(self.fcn(q,k,acc.write(k),q.toFloat().sqrt()));
return(self.fcn(n,k+1+k.isOdd,acc,maxD)) # both are tail recursion
}
}(n,2,Sink(List),n.toFloat().sqrt());
m:=acc.reduce('*,1); // mulitply factors
if(n!=m) acc.append(n/m); // opps, missed last factor
else acc;
}
[1..199].apply(mobius)
.pump(Console.println, T(Void.Read,19,False),
fcn{ vm.arglist.pump(String,"%3d".fmt) });
Output:
  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