23
4
The Möbius Function
The Möbius function is an important number theoretic function.
Your submission should accept a positive integer n
and return the value of the Möbius function evaluated at n
.
Definition
The Möbius function μ(n) is defined as follows:
| 1 if n is squarefree and has an even number of distinct prime factors
μ(n) = | -1 if n is squarefree and has an odd number of distinct prime factors
| 0 otherwise
n
is called squarefree if the exponents of the prime factorization of n are all strictly less that two. (Alternatively: No prime to the power of two divides n
).
Test cases
Here you can see the first 50 values of μ:
Public Domain Image from Wikipedia
The Möbius function is sequence number A008683 in the OEIS.
These are the first 77 values:
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
Larger values can also easily be checked in Wolframalpha.com or in the b-file of OEIS, as suggested by @MartinBüttner.
-1 byte:
ÆFỊNPS
(not sure ifỊ
was a built-in back then, but should be fine now). – Erik the Outgolfer – 2018-10-28T10:47:06.207