18
\$\begingroup\$

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

Mertens

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
\$\endgroup\$

19 Answers 19

6
\$\begingroup\$

Jelly, 6 bytes

:Ḋ߀SC

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

Background

This uses the property

property by David W. Wilson

from A002321, which leads to the following recursive formula.

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.
\$\endgroup\$
11
\$\begingroup\$

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.

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

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

property by David W. Wilson

from A002321, which leads to the following recursive formula.

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.

\$\endgroup\$
7
\$\begingroup\$

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!

\$\endgroup\$
7
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

Jelly, 9 bytes

RÆFỊNP€FS

Try it online! or verify all test cases.

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].
\$\endgroup\$
5
\$\begingroup\$

Haskell, 29 27 bytes

f n=1-sum(f.div n<$>[2..n])
\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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]))))
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 50 bytes

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

Port of @Dennis's Python answer.

\$\endgroup\$
2
\$\begingroup\$

Julia, 26 25 bytes

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

Try it online!

Background

This uses the property

property by David W. Wilson

from A002321, which leads to the following recursive formula.

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.)

\$\endgroup\$
1
\$\begingroup\$

Actually, 18 17 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.
\$\endgroup\$
1
\$\begingroup\$

PARI/GP, 24 bytes

n->sum(x=1,n,moebius(x))
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.