# Compute the Mertens function

Given a positive integer n, compute the value of the Mertens function M(n) where

and μ(k) is the Möbius function where μ(k) = 1 if k has an even number of distinct prime factors, -1 if k has an odd number of distinct prime factors, and 0 if the prime factors are not distinct.

• This is so create the shortest code for a function or program that computes the Mertens function for an input integer n > 0.
• This is the OEIS sequence A002321.

## Test Cases

n M(n)
1 1
2 0
3 -1
4 -1
5 -2
6 -1
7 -2
8 -2
9 -2
10 -1
117 -5
5525 5
7044 -25
8888 4
10000 -23


# Jelly, 6 bytes

:Ḋß€SC


Try it online! or verify the smaller test cases. (takes a while)

### Background

This uses the property

from A002321, which leads to the following recursive formula.

### How it works

:Ḋß€SC  Main link. Argument: n

Ḋ      Dequeue; yield [2, ..., n].
:       Perform the integer division of n by each k in [2, ..., n].
ß€    Recursively call the main link on each result.
S   Sum; add the results from the recursive calls.
C  Complement; map the sum r to 1 - r.


# Mathematica, 22 20 bytes

Thanks to @miles for saving 2 bytes.

Tr@*MoebiusMu@*Range


# Explanation

Range


Generate a list from 1 to input.

MoebiusMu


Find MoebiusMu of each number

Tr


Sum the result.

• I love how Mathematica has a builtin for everything, but it's usually longer than a golfing language anyway. =D – DJMcMayhem Sep 29 '16 at 13:42
• Another call for mthmca, the command-name-length-optimized version of Mathematica. – Michael Stern Sep 29 '16 at 14:08

# Python 2, 45 37 bytes

f=lambda n,k=2:n<k or f(n,k+1)-f(n/k)


Test it on Ideone.

### Background

This uses the property

from A002321, which leads to the following recursive formula.

### How it works

We use recursion not only to compute M for the quotients, but to compute the sum of those images as well. This saves 8 bytes over the following, straightforward implementation.

M=lambda n:1-sum(M(n/k)for k in range(2,n+1))


When f is called with a single argument n, the optional argument k defaults to 2.

If n = 1, n<k yields True and f returns this value. This is our base case.

If n > 1, n<k initially returns False and the code following or is executed. f(n/k) recursively computes one term of the sum, which is subtracted from the return value of f(n,k+1). The latter increments k and recursively calls f, thus iterating over the possible values of k. Once n < k + 1 or n = 1, f(n,k+1) will return 1, ending the recursion.

# 05AB1E, 16 15 bytes

LÒvX(ygmyyÙïQ*O


Explanation

L        # range [1 .. n]
Ò        # list of prime factors for each in list
v        # for each prime factor list
X(ygm   # (-1)^len(factors)
yyÙïQ*  # multiplied by factors == (unique factors)
O       # sum


Try it online!

# Brachylog, 22 20 bytes

yb:1a+
$p#dl:_1r^|,0  Try it online! ### Explanation yb The list [1, 2, …, Input] :1a Apply predicate 1 (second line) to each element + Sum the resulting list$p#d               All elements of the list of prime factors of the Input are distinct
l:_1r^         Output = (-1)^(<length of the list of prime factors>)
|                  Or
,0                 Output = 0


# Jelly, 9 bytes

RÆFỊNP€FS


### How it works

RÆFỊNP€FS  Main link. Argument: n

R          Range; yield [1, ..., n].
ÆF        Factor; decompose each integer in that range into prime-exponent pairs.
Ị       Insignificant; yield 1 for argument 1, 0 for all others.
N      Negative; map n to -n.
This maps primes to 0, exponent 1 to -1, and all other exponents to 0.
P€    Reduce the columns of the resulting 2D arrays by multiplication.
The product of the prime values will always be 0; the product of the
exponent values is 0 if any exponent is greater than, 1 if there is an
even number of them, -1 is there is an odd number of them.
FS  Flatten and sum, computing the sum of µ(k) for k in [1, ..., n].


f n=1-sum(f.div n<$>[2..n])  # Jelly, 7 bytes Ị*%ðþÆḊ  Not very efficient; determinants are hard. Try it online! or verify the smaller test cases. (takes a while) ### Background This uses a formula from A002321: M(n) is the determinant of the Boolean matrix An×n, where ai,j is 1 if j = 1 or i | j, and 0 otherwise. ### How it works Ị*%ðþÆḊ Main link. Argument: n ð Combine the preceding atoms into a chain (unknown arity). Begin a new, dyadic chain with arguments a and b. Ị Insignificant; return 1 iff a = 1. % Compute a % b. * Compute (a == 1) ** (a % b). This yields 1 if a = 1, or if a ≠ 1 and a % b = 0; otherwise, it yields 0. þ Table; construct the matrix A by calling the defined chain for every pair of integers in [1, ..., n]. ÆḊ Compute the determinant of the resulting matrix.  # PHP, 113 bytes for(;$i=$argv[1]--;){for($n=$j=1;$j++<$i;)if(!($i%$j)){$i/=$j;$n++;if(!($i%$j))continue 2;}$a+=$n%2?1:-1;}echo$a;  As far as I know php lacks anything like prime number functionality so this is kind of a pain. It's probably possible to do better. use like:  php -r "for(;$i=$argv[1]--;){for($n=$j=1;$j++<$i;)if(!($i%$j)){$i/=$j;$n++;if(!($i%$j))continue 2;}$a+=$n%2?1:-1;}echo\$a;" 10000


## Racket 103 bytes

(λ(N)(for/sum((n(range 1 N)))(define c(length(factorize n)))(cond[(= 0 c)0][(even? c)1][(odd? c)-1])))


Ungolfed:

(define f
(λ(N)
(for/sum ((n (range 1 N)))
(define c (length (factorize n)))
(cond
[(= 0 c) 0]
[(even? c) 1]
[(odd? c) -1]))))


## CJam (20 bytes)

qiM{_,:)(@@f/{j-}/}j


Online demo

Uses the formula from OEIS

sum(k = 1..n, a([n/k])) = 1. - David W. Wilson, Feb 27 2012

and CJam's memoising operator j.

### Dissection

qi       e# Read stdin as an integer
M{       e# Memoise with no base cases
e#   Memoised function: stack contains n
_,:)(  e#   Basic manipulations to give n [2 .. n] 1
@@f/   e#   More basic manipulations to give 1 [n/2 ... n/n]
{j-}/  e#   For each element of the array, make a memoised recursive call and subtract
}j


## JavaScript (ES6), 50 bytes

n=>[1,...Array(n-1)].reduce((r,_,i)=>r-f(n/++i|0))


# Julia, 26 25 bytes

!n=1-sum(map(!,n÷(2:n)))


Try it online!

### Background

This uses the property

from A002321, which leads to the following recursive formula.

### How it works

We redefine the unary operator ! for our purposes.

n÷(2:n) computes all required quotients, our redefined ! is mapped over them, and finally the sum of all recursive calls is subtracted from 1.

Unfortunately,

!n=1-sum(!,n÷(2:n))


does not work since dyadic sum will choke on an empty collection.

!n=n<2||1-sum(!,n÷(2:n))


fixes this, but it doesn't save any bytes and returns True for input 1.

# C, 51 50 47 bytes

f(n,t,u){for(t=u=1;n/++u;t-=f(n/u));return t;}


Edit: Thanks to @Dennis for -3 bytes!

# Scala, 53 bytes

def?(n:Int,k:Int=2):Int=if(n<k)1 else?(n,k+1)- ?(n/k)


A port of Dennis's pythin answer.

I've called the method ?, which is a token that doesn't stick to letters.

# Pyth, 12 bytes

Defines a function y that takes in the n.

L-1syM/LbtSb


Test suite here. (Note that the trailing y here is to actually call the declared function.)

# Actually, 1817 16 bytes

Golfing suggestions welcome. Try it online!

R;y;l0~ⁿ)π=*MΣ


Ungolfing

         Implicit input n.
R        Push the range [1..n].
...M   Map the following function over the range. Variable k.
;        Duplicate k.
y        Push the distinct prime factors of k. Call it dpf.
;        Duplicate dpf.
l        Push len(dpf).
0~       Push -1.
ⁿ        Push (-1)**len(dpf).
)        Move (-1)**len(dpf) to BOS. Stack: dpf, k, (-1)**len(dpf)
π        Push product(dpf).
=        Check if this product is equal to k.
If so, then k is squarefree.
*        Multiply (k is squarefree) * (-1)**(length).
If k is NOT squarefree, then 0.
Else if length is odd, then -1.
Else if length is even, then 1.
This function is equivalent to the Möbius function.
Σ        Sum the results of the map.
Implicit return.


# PARI/GP, 24 bytes

n->sum(x=1,n,moebius(x))


# J, 19 bytes

1#.1*/@:-@~:@q:@+i.


Computes the Mertens function on n using the sum of the Möbius function over the range [1, n].

## Usage

   f =: 1#.1*/@:-@~:@q:@+i.
(,.f"0) 1 2 3 4 5 6 7 8 9 10 117 5525 7044 8888 10000
1   1
2   0
3  _1
4  _1
5  _2
6  _1
7  _2
8  _2
9  _2
10  _1
117  _5
5525   5
7044 _25
8888   4
10000 _23


## Explanation

1#.1*/@:-@~:@q:@+i.  Input: integer n
i.  Range [0, 1, ..., n-1]
1            +    Add 1 to each
q:@     Get the prime factors of each
~:@        Sieve mask of each, 1s at the first occurrence
of a value and 0 elsewhere
-@           Negate
*/@:             Reduce each using multiplication to get the product
1#.                  Convert that to decimal from a list of base-1 digits
Equivalent to getting the sum