[Question]
  [
Given a positive integer *n*, compute the value of the [Mertens function](https://en.wikipedia.org/wiki/Mertens_function) \$M(n)\$ where:
$$M(n) = \Sigma\_{k=1}^{n}\mu(k)$$
and \$\mu(k)\$ is the [Möbius function](https://en.wikipedia.org/wiki/M%C3%B6bius_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 [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") 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](https://oeis.org/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
```
  
[Answer]
# 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.
[Answer]
# Python 2, ~~45~~ 37 bytes
```
f=lambda n,k=2:n<k or f(n,k+1)-f(n/k)
```
Test it on [Ideone](http://ideone.com/2oF26f).
### Background
This uses the property
![property by David W. Wilson](https://i.stack.imgur.com/rhDhP.png)
from [A002321](https://oeis.org/A002321), which leads to the following recursive formula.
![recursive formula](https://i.stack.imgur.com/VjAmY.png)
### 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.
[Answer]
# [05AB1E](http://github.com/Adriandmen/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!](http://05ab1e.tryitonline.net/#code=TMOSdlgoeWdteXnDmcOvUSpP&input=MTE3)
[Answer]
# [Brachylog](http://github.com/JCumin/Brachylog), ~~22~~ 20 bytes
```
yb:1a+
$p#dl:_1r^|,0
```
[Try it online!](http://brachylog.tryitonline.net/#code=eWI6MWErCiRwI2RsOl8xcl58LDA&input=OQ&args=Wg)
### 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
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 6 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
:Ḋß€SC
```
[Try it online!](http://jelly.tryitonline.net/#code=OuG4isOf4oKsU0M&input=&args=MTE3) or [verify the smaller test cases](http://jelly.tryitonline.net/#code=OuG4isOf4oKsU0MKMTBSOzExNyw1NTI1wrXFvMOH4oKsRw&input=). (takes a while)
### Background
This uses the property
![property by David W. Wilson](https://i.stack.imgur.com/rhDhP.png)
from [A002321](https://oeis.org/A002321), which leads to the following recursive formula.
![recursive formula](https://i.stack.imgur.com/VjAmY.png)
### 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.
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 9 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
RÆFỊNP€FS
```
[Try it online!](http://jelly.tryitonline.net/#code=UsOGRuG7ik5Q4oKsRlM&input=&args=MTAwMDA) or [verify all test cases](http://jelly.tryitonline.net/#code=UsOGRuG7ik5Q4oKsRlMKMTBSOzExNyw1NTI1LDcwNDQsODg4OCzItzTCtcW8w4figqxH&input=).
### 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].
```
[Answer]
# Haskell, ~~29~~ 27 bytes
```
f n=1-sum(f.div n<$>[2..n])
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 7 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
Ị*%ðþÆḊ
```
Not very efficient; determinants are hard.
[Try it online!](http://jelly.tryitonline.net/#code=4buKKiXDsMO-w4bhuIo&input=&args=OQ) or [verify the smaller test cases](http://jelly.tryitonline.net/#code=4buKKiXDsMO-w4bhuIoKMTBSOzExN8K1xbzDh-KCrEc&input=). (takes a while)
### Background
This uses a formula from [A002321](https://oeis.org/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.
```
[Answer]
# 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
```
[Answer]
## 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]))))
```
[Answer]
## CJam (20 bytes)
```
qiM{_,:)(@@f/{j-}/}j
```
[Online demo](http://cjam.aditsu.net/#code=qiM%7B_%2C%3A)(%40%40f%2F%7Bj-%7D%2F%7Dj&input=13)
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
```
[Answer]
## JavaScript (ES6), 50 bytes
```
n=>[1,...Array(n-1)].reduce((r,_,i)=>r-f(n/++i|0))
```
Port of @Dennis's Python answer.
[Answer]
# Julia, ~~26~~ 25 bytes
```
!n=1-sum(map(!,n÷(2:n)))
```
[Try it online!](http://julia.tryitonline.net/#code=IW49MS1zdW0obWFwKCEsbsO3KDI6bikpKQoKZm9yIG4gaW4gWzE6MTA7WzExNyw1NTI1LDcwNDQsODg4OCwxMDAwMF1dCiAgICBAcHJpbnRmKCIlNWQgLT4gJTNkXG4iLCBuLCAhbikKZW5k&input=)
### Background
This uses the property
![property by David W. Wilson](https://i.stack.imgur.com/rhDhP.png)
from [A002321](https://oeis.org/A002321), which leads to the following recursive formula.
![recursive formula](https://i.stack.imgur.com/VjAmY.png)
### 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**.
[Answer]
# 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](https://codegolf.stackexchange.com/users/12012/dennis) for -3 bytes!
[Answer]
# PARI/GP, 24 bytes
```
n->sum(x=1,n,moebius(x))
```
[Answer]
# 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.
[Answer]
# Pyth, 12 bytes
Defines a function `y` that takes in the `n`.
```
L-1syM/LbtSb
```
[Test suite here.](http://pyth.herokuapp.com/?code=L-1syM%2FLbtSby&input=5&test_suite=1&test_suite_input=1%0A2%0A3%0A4%0A5%0A6%0A7%0A8%0A9%0A10%0A117%0A5525%0A7044%0A8888%0A10000&debug=0) (Note that the trailing `y` here is to actually call the declared function.)
[Answer]
# Actually, ~~18~~ ~~17~~ 16 bytes
Golfing suggestions welcome. [Try it online!](http://actually.tryitonline.net/#code=UmA7eTtsMH7igb8pz4A9KmBNzqM&input=ODg4OA)
```
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.
```
[Answer]
# 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
```
[Answer]
# [Factor](https://factorcode.org) + `math.extras math.unicode`, 27 bytes
```
[ [1,b] [ mobius ] map Σ ]
```
[Attempt This Online!](https://ato.pxeger.com/run?1=RY8xDoIwGIV3TvG7C6EFBPUAxsXFOBGGglUZKFjaRGM8iQuJwUt4B3ev4mRpSfqWfu_15TV9vA6kEDXvvr_ddr1ZLaAi4uTRi-CkNcwJO9KRJSuLek-h4VSIa8NLJqClZ0lZoSpL5-aAEoIJIE1Yka8pUOSaMLQYDYg1zmwa2zSxOLeIfFtGSNcjsxfhYdKY2A_1U9jYREnZcFxQ0peBc--lOLjJO4UUTfMMUqjqvJQtZOrTDXyekJlGP1jPcNeZ8w8)
]