Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question

20 Answers 20

Python 2, 51 bytes

m=lambda n:1/n-sum(m(k)for k in range(1,n)if n%k<1)

Möbius-inverts the sequence of all ones.

The Möbius function has the property that for any n>1, the Möbius functions of n's divisors sum to 0. So, for n>1, μ(n) is computed by negating the sum of μ(k) for all proper divisors k of n. For n=1, the output is 1.

The code handles the base case by adding a floor-division 1/n, which gives 1 for n==1 and 0 otherwise.

share|improve this answer
    
if n%k<1 was a nice touch. Saves one byte, yes? – Alec Jan 24 at 22:16
    
@Alec Yup, it's a classic trick for checking divisibility. – xnor Jan 25 at 4:50

Jelly, 7 bytes

Code:

ÆF>1’PS

Explanation:

ÆF       # This computes the prime factorization as well as the exponent
  >1     # Compares each element if it's greater than 1, resulting in 1's and 0's
    ’    # Decrement on each element
     P   # Compute the product
      S  # Compute the sum of the list

For example, the number 10:

ÆF       # [[2, 1], [5, 1]]
  >1     # [[1, 0], [1, 0]]
    ’    # [[0, -1], [0, -1]]
     P   # [0, 1]
      S  # 1

And results in 1.

Try it online.

share|improve this answer

Mathematica, 9 bytes

MoebiusMu

Of course, Mathematica has a built-in. (And will probably be is beaten by Jelly anyway.)

share|improve this answer

CJam, 18 15 bytes

WrimFz~\1&+f/:*

The fact that CJam returns 1 in factorisation builtins for n = 1 makes things a bit tricky.

Try it online | Test suite

Thanks to @PeterTaylor for the neat 1&+ trick for handling the 1 case.

Explanation

W                 Push -1
 ri               Push input as int
   mF             Factorise input into [base exponent] pairs
     z~           Zip and unwrap pairs, leaving stack like [-1 bases exponents]
       \1&        Setwise intersect bases with 1, giving [1] for 1 and [] otherwise
          +       Append to exponent array
           f/     Divide the previously pushed -1 by each element in the array 
                  This gives -1 for 1s and 0 otherwise, since / is int division
             :*   Take product

For n > 1, the modified array is just the exponents array. If n is squarefree then the array is all 1s, which become all -1s after division. Otherwise, if n has a prime square divisor, then there will be a 0 somewhere after division, giving a product of 0.

For n = 1 the modified array is [1] + [1], which becomes [-1 -1] after division, giving a product of 1.


Alternative 16:

rimF{1#2+3%(}%:*

This uses # (find) on each [base exponent] array to look for a 1, then maps -1 -> 0, 0 -> 1, 1 -> -1.

share|improve this answer

Ruby, 65+7=72 62+7=69 bytes

->x{((d=x.prime_division).all?{|_,n|n<2}?1:0)*(d.size%2*-2+1)}

+7 bytes for the -rprime flag.

We're doing this the very naïve way:

->x{
 (
  (d=x.prime_division)  # ex. input 20 results in [[2,2],[5,1]] here
  .all?{|_,n|n<2}?      # are all factors' exponents under 2?
  1:0                   # if so, result in a 1; otherwise, a 0
 )
 *                      # multiply that 1 or 0 by...
  (d.size%2*-2+1)       # magic
}

The "magic" part results in 1 if the number is even and -1 otherwise. Here's how:

Expression       Even  Odd
--------------------------
d.size%2         0     1
d.size%2*-2      0     -2
d.size%2*-2+1    1     -1
share|improve this answer

Labyrinth, 87 bytes

1
:
}
?   @ "}){/{=:
""({! "      ;
} )   :}}:={%"
* _}}){     ;
{      #}):{{
")`%#/{+

Try it online!

Short explanation

Here's a port of the algorithm used, in Python:

divisor = 1
mobius = 1
n = int(input())

while n != 1:
  divisor += 1
  count = 0

  while n % divisor == 0:
    n //= divisor
    count += 1

  mobius *= (count + 3)//(count + 1)%3*-1 + 1

print(mobius)

Long explanation

The usual primer on Labyrinth:

  • Labyrinth is stack-based and two-dimensional, with execution starting at the first recognised character. There are two stacks, a main stack and an auxiliary stack, but most operators only work on the main stack.
  • At every branch of the labyrinth, the top of the stack is checked to determine where to go next. Negative is turn left, zero is straight ahead and positive is turn right.

Execution for this program starts at the top-left 1.

Outer preparation
=================

1        Pop 0 (stack is bottomless and filled with 0s) and push 0*10+1 = 1
:}       Duplicate and shift to auxiliary stack
?        Read int from input
         Stack is now [div=1 n | mob=1]

Top of stack positive but can't turn right. Turn left into outer loop.

Begin outer loop
================
Inner preparation
-----------------

(        Decrement top of stack

If top was 1 (and is now zero), move forward and do...
------------------------------------------------------

{!       Print mob
@        Terminate

If top of stack was greater than 1, turn right and do...
--------------------------------------------------------

)        Increment n back to its previous value
_}       Push 0 and shift to aux
         This will count the number of times n can be divided by div
}){      Increment div
         Stack is now [div n | count mob]

Inner loop
----------

:}}      Dup n, shift both n's to aux
:=       Dup div and swap top of main with top of aux
{%       Shift div down and take mod
         Stack is now [div n%div | n count mob]

If n%div == 0, move forward and do...
-----------------------------------

;        Pop n%div
:={/     Turn n into n/div
{)}      Increment count
         (continue inner loop)

If n%div != 0, turn right (breaking out of inner loop) and do...
================================================================

;        Pop n%div
{{       Pull n and count from aux
:)}      Dup and increment count, giving (count+1), and shift to aux
#+       Add length of stack to count, giving (count+3)
{/       Calculate (count+3)/(count+1)
#%       Mod by length of stack, giving (count+3)/(count+1)%3
`        Multiply by -1
)        Increment, giving (count+3)/(count+1)%3*-1 + 1
         This is 1 if count was 0, -1 if count was 1 and 0 if count > 1
{*}      Multiply mob by this number
         (continue outer loop)
share|improve this answer

CJam, 20 bytes

rimf1-___&=\,2%!2*(*

Run it against a range of inputs here.

Seems golfable.

share|improve this answer
2  
The fact that 1 is returned in mf or mF really hurts... – Sp3000 Jan 24 at 14:31
    
@Sp3000 Tell me about it :-( – Luis Mendo Jan 24 at 17:35

Pyth, 9 bytes

^_{IPQlPQ

Explanation:

^_{IPQlPQ    Implicit: Q=input
    PQ       Prime factorization of Q
  {I         Is invariant under uniquify.
  {IPQ       1 if Q is squarefree; 0 otherwise.
 _{IPQ       -1 if Q is squarefree; 0 otherwise.
^     lPQ    Exponentiation to length of PQ.

Try it here.

share|improve this answer

R 3916 bytes

numbers::moebius

Requires you having the numbers package installed on your system...

Edit: Far simpler if I read the specs appropriately [thanks @AlexA.]

share|improve this answer
    
This returns the Möbius function evaluated for each integer from 1 to the input, but the task for this challenge is simply to evaluate the Möbius function on the input. – Alex A. Jan 25 at 0:44
    
Along the lines of the Mathematica answer, you could even do simply numbers::moebius for 16 bytes. – Alex A. Jan 25 at 0:45
    
@AlexA. Noted and thanks! – mnel Jan 25 at 0:48

Pyth, 16 Bytes

?nl{PQlPQZ^_1lPQ

Try it online!

My first actual Pyth answer. Suggestions appreciated! :)

Explanation

My solution uses the fact that a number is squarefree, if its prime-factors contain no number more than once. If the input is squarefree, the Möbius-Function takes the value -1^(number of primefactors).


?n        if not equal
  l{PQ      length of the list of the distinct input-Primefactors
  lPQ       length of the list of primefactors including duplicates    
    Z         Input is not squarefree, so output Zero
  ^_1lPQ  if input is squarefree, output -1^(number of prime-factors)
share|improve this answer

MATL, 15 17 bytes

tq?YftdAwn-1w^*

This uses current release (10.1.0) of the language/compiler.

Try it online!

Explanation

t         % implicit input. Duplicate that
q         % decrement by 1. Gives truthy (nonzero) if input exceeds 1
?         % if input exceeds 1, compute function. Otherwise leave 1 on the stack
  Yf      % vector of prime factors. Results are sorted and possibly repeated
  td      % duplicate and compute differences
  A       % true if all differences are nonzero
  w       % swap
  n       % number of elements in vector of prime factors, "x"
  -1w^    % -1^x: gives -1 if x odd, 1 if x even 
  *       % multiply by previously obtained true/false value, so non-square-free gives 0
          % implicitly end "if"
          % implicitly display stack contents
share|improve this answer

05AB1E, 8 bytes, non-competing

Dammit, once again a bug which makes my submission non-competing. Code:

.p0K1›<P

Explanation:

.p        # Get the prime factorization exponents
  0K      # Remove all zeroes from the list
    1›    # Compare each element if greater than 1
      <   # Decrement on each element
       P  # Take the product

Uses the CP-1252 encoding

share|improve this answer
    
isn't in ISO 8859-1... – ETHproductions Jan 24 at 20:39
1  
@ETHproductions Heh? What kind of encoding is it then? I got it from this site. – Adnan Jan 24 at 20:44
    
I believe it's called Extended ASCII. – ETHproductions Jan 24 at 20:54
    
@ETHproductions Thanks, I have edited the post :) – Adnan Jan 24 at 21:08
    
@ThomasKwa Ahh, I have found it. It is the CP-1252 encoding. – Adnan Jan 24 at 21:41

Pyth, 11

*{IPQ^_1lPQ

Test suite

This multiplies the boolean value of if the prime factors are squarefree by -1 to the power of the number of prime factors that the number has.

I is an invariance check on the preceeding operator, which here is {, which is the unique-ify operator.

share|improve this answer

Japt, 21 bytes

V=Uk)¬¥Vâ ¬?Vl v ªJ:0

Test it online!

share|improve this answer

Julia, 66 bytes

n->(f=factor(n);any([values(f)...].>1)?0:length(keys(f))%2>0?-1:1)

This is a lambda function that accepts an integer and returns an integer. To call it, assign it to a variable.

Ungolfed:

function µ(n::Int)
    # Get the prime factorization of n as a Dict with keys as primes
    # and values as exponents
    f = factor(n)

    # Return 0 for non-squarefree, otherwise check the length of the list
    # of primes
    any([values(f)...] .> 1) ? 0 : length(keys(f)) % 2 > 0 ? -1 : 1
end
share|improve this answer

PARI/GP, 7 bytes

moebius

Sadly möbius is not available. :)

share|improve this answer

Seriously, 19 18 bytes

,w;`iX1=`Mπ)l1&τD*

Try it online!

Explanation:

,w;`iXDY`Mπ)l1&τD*
,w;                push two copies of the full prime factorization of the input
                      (a list of [base, exponent] pairs)
   `    `M         map the following function:
    iX1=             flatten list, discard, equal to 1
                        (push 1 if exponent == 1 else 0)
          π)       product of list, push to bottom of stack
            1&     push 1 if the # of prime factors is even else 0
              τD   double and decrement (transform [0,1] to [-1,1])
                *  multiply
share|improve this answer

GNU sed, 89 bytes

#!/bin/sed -rf
s/.*/factor &/e
s/.*://
/\b([0-9]+) \1\b/!{
s/[0-9]+//g
s/$/1/
s/  //g
y/ /-/
}
s/ .*/0/
share|improve this answer

J, 18 bytes

[:*/3<:@|2+2<._&q:
share|improve this answer

Microsoft Office Excel, British version, 196 bytes

=IF(ROW()>=COLUMN(),IF(AND(ROW()=1,COLUMN()=1),1,IF(COLUMN()=1,
-SUM(INDIRECT(ADDRESS(ROW(),2)&":"&ADDRESS(ROW(),ROW()))),
IF(MOD(ROW(),COLUMN())=0,INDIRECT(ADDRESS(FLOOR(ROW()/COLUMN(),1),
1)),""))),"")

Excel cell formula to be entered in cells A1 to AX50.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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