g | x | w | all
Bytes Lang Time Link
071GNU sed160125T173937ZToby Spe
318jBasher2250908T150804Zmadeforl
054YASEPL250905T135617Zmadeforl
012Japt250905T143608ZShaggy
046TIBASIC TI83 Plus250403T150545Zmadeforl
022APLNARS250401T215050ZRosario
5875Vyxal230518T114409Zlyxal
096Haskell230516T220135ZRoman Cz
006Factor + math.extras221228T162623Zchunes
064Java 8181030T131902ZKevin Cr
00805AB1E160124T143030ZAdnan
065C# .NET Core181029T150501ZMeerkat
048Javascript ES6181028T090721Zuser8371
011Seriously160930T195943ZSherlock
035Julia160627T004608ZDennis
048Python 2160124T181023Zxnor
196Microsoft Office Excel160128T143416ZMats Gra
018J160127T102842Zalephalp
018Seriously160124T223807Zuser4594
087Labyrinth160126T111605ZSp3000
007PARI/GP160125T162924ZCharles
016R160124T230756Zmnel
066Julia160125T004034ZAlex A.
015CJam160124T150047ZSp3000
009Pyth160124T205804Zlirtosia
021Japt160124T203858ZETHprodu
011Pyth160124T200747ZFryAmThe
015MATL160124T172747ZLuis Men
016Pyth160124T142316ZDenker
007Jelly160124T135908ZAdnan
nanRuby160124T143502ZDoorknob
020CJam160124T140740ZMartin E
009Mathematica160124T135916ZMartin E

GNU sed, 89 71 bytes

#!/bin/sed -rf
s/.*/factor -h &/e
/\^/!{
s/[^ ]//g
s/  //g
y/ /-/
s/$/1/
}
/:/s/.*/0/

How it works

First, we invoke external factor program.

If there is any ^ in the result, the number is not square-free, and we skip to the end.

Otherwise, we just need to count the spaces - there's one before each prime factor - so remove the non-spaces and eliminate pairs. If there's one left over, we had an odd number of spaces (i.e. an odd number of factors), so replace it with -. Then append 1 to complete the result.

If we didn't remove the non-space characters, there will be a : in the line - then replace the whole line with 0 to indicate a square factor.

jBasher2, 318 bytes

create n with type number
create r with type number
create i with type number
ask for input
set that to n
set 1 to r
set 2 to i
while i <= n
modulo n by i
if that == 0
divide n by i
set that to n
modulo n by i
if that == 0
set 0 to r
endif
subtract 0 by r
set that to r
endif
add i by 1
set that to i
endwhile
output r

translation of my YASEPL answer.

YASEPL, 54 bytes

=n'=r$=i$2`1!u$n%i+[2!/i=q$n%i+[3=r`3=t!r:t`2!i+}4,n>r

explanation

=n'=r$=i$2`1!u$n%i+[2!/i=q$n%i+[3=r`3=t!r:t`2!i+}4,n>r       packed
=n'                                                          get input
   =r$                                                       set r to 1
      =i$2                                                   set increment to 2
          `1                                 !i+}4,n         while i <= n...
            !u$n%i+[2                      `2                  if n is divisible by i...
                     !/i                                         divide n by i
                        =q$n%i+[3  `3                            if n is still divisible by i...
                                 =r                                set r to 0
                                     =t!r:t                      r = -r
                                             !i+                 increment i and check loop
                                                    >r       when done, print r

translation of Kevin's answer in java 8

Japt, 12 bytes

k
eUâ)*JpUÊu

Try it

k\neUâ)*JpUÊu     :Implicit input of integer U
k                 :Prime factors
 \n               :Reassign to U
   e              :Is exactly equal to
    Uâ            :  U deduplicated
      )           :End equality check
       *          :Multiply by
        J         :  -1
         p        :  Raised to the power of
          UÊ      :    Length of U
            u     :    Modulo 2

TI-BASIC (TI-83 Plus), 46 bytes

Input N
1→R
For(I,2,N
If not(fPart(N/I
Then
N/I→N
-R(0<fPart(N/I→R
End
End
R

this is a translation of Kevin's answer in Java 8

APL(NARS), 22 chars

{∨/2≤≢¨k←⊂⍨π⍵:0⋄¯1*≢k}

Factor input if some expont is >=2 return 0, else return -1^(number of factors of input)

Vyxal, 47 bitsv1, 5.875 bytes

ǐÞu$†Ǎ*

Try it Online!

What do you mean it's not morbin' time? I love vyncode and how just re-arranging things makes the program shorter.

Explained

ǐÞu$†Ǎ*
ǐ       # prime factors of input with duplicates
 Þu     # all unique?
   $†Ǎ  # -1 ** len(prime_factors(input))
      * # multiply

Haskell, 96 bytes

import Data.Numbers.Primes
import Data.List
m=(\f->last$0:[(-1)^length f|f==nub f]).primeFactors

Try it online!

Factor + math.extras, 6 bytes

mobius

Attempt This Online!

Java 8, 72 68 65 64 bytes

n->{int r=1,i=1;for(;i++<n;)r=n%i<1?(n/=i)%i<1?0:-r:r;return r;}

-4 bytes thanks to @PeterTaylor.

Port of @Meerkat's .NET C# answer, which I first golfed a bit further, so make sure to upvote him!

Try it online.

Explanation:

n->{                // Method with integer as both parameter and return-type
  int r=1,          //  Result-integer, starting at 1
  i=1;for(;i++<n;)  //  Loop `i` in the range [1, n]:
    r=n%i<1?        //   If `n` is divisible by `i`:
       (n/=i)       //    Divide `n` by `i` first
        %i<1?       //    And if `n` is still divisible by `i`:
         0          //     Change `r` to 0
        :           //    Else:
         -r         //     Swap the sign of `r` (positive to negative or vice-versa)
      :             //    Else:
       r;           //     Leave `r` unchanged
  return r;}        //  Return `r` as result

05AB1E, 8 bytes

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

C# (.NET Core), 86 73 72 65 bytes

a=>{int b=1,i=1;for(;++i<=a;)b=a%i<1?(a/=i)%i<1?0:-b:b;return b;}

Try it online!

-13 bytes: streamlined loops, added return variable (thanks to Kevin Cruijssen)
-1 byte: changed setting b to zero to a ternary from an if (thanks to Kevin Cruijssen)
-7 bytes: changed if statement in for loop to a ternary (thanks to Peter Taylor and Kevin Cruijssen)

Ungolfed:

a => {
    int b = 1, i = 1;           // initialize b and i to 1

    for(; ++i <= a;)            // loop from 2 (first prime) to a
        b = a % i < 1 ?                     // ternary: if a is divisible by i
            ((a /= i) % i < 1 ? 0 : -b) :   // if true: set b to 0 if a is divisible by i squared, otherwise flip sign of b
            b;                              // if false: don't change b

    return b;                   // return b (positive for even numbers of primes, negative for odd, zero for squares)
}

Javascript (ES6), 48 bytes

f=(n,i=1)=>n-1?n%++i?f(n,i):(n/=i)%i?-f(n,i):0:1

First of all - this is my first code golf post so I may misunderstand the rules to some extent. In this submission the last character ; could be omitted and it'll still work but I'm not even sure if the code would be valid according to the ES6 specs. Anyways, a short explanation.

First, I'll explain the idea a bit; we take n, and we try dividing it by the integer i. If it's divisible, then we do so and we check if it's divisible by i again. If that's the case, then we need to return 0. Otherwise, we can try another i. The cool thing is, we can just start at i=2 and just add increase it by 1 every time, so that we divide out all the prime factors.

So, the code works like this:

f=(n,i=1)=>                                           We will increase i by one at the start of
                                                         the function body, so default is 1
           n-1?                                       Check if n==1.
               n%++i?                                 If i isn't, increase i by 1, check if n
                                                         is divisible by i
                     f(n,i):                          if it isn't, we check the next i
                            (n/=i)%i?                 if it is, divide n by i, and check for
                                                         divisibility by i again
                                     -f(n,i):         if it not, then we flip the value to
                                                         account for the 1 and -1 depending on the
                                                         amount of factors
                                             0:       if it's divisible by i twice, done.
                                               1      if we're at 1, divided out all factors,
                                                         then we return 1. The line with
                                                         -f(n,i) will then take care of the sign

So, that's my submission.

Seriously, 11 bytes

Golfing suggestions welcome. Try it online!

;y;l0~ⁿ)π=*

Ungolfing

     Implicit input n.
;    Duplicate n.
y    Push a list of the distinct prime factors of n. Call it dpf.
;    Duplicate dpf.
l    Push len(dpf).
0~   Push -1.
ⁿ    Push (-1)**len(dpf).
)    Rotate (-1)**len(dpf) to BOS. Stack: dpf, n, (-1)**len(dpf)
π    Push product(dpf).
=    Check if product(dpf) == n.
      This is only true if n is squarefree.
*    Multiply (n is squarefree) by (-1)**len(dpf).
     Implicit return.

Julia, 35 bytes

\(n,k=1)=k%n>0?n\-~k-k\0^(n%k):1÷n

Based on @xnor's Python answer. Try it online!

Python 2, 48 bytes

m=lambda n,d=1:d%n and-m(d,n%d<1)+m(n,d+1)or 1/n

Earlier 51 byte version:

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

Möbius-inverts the sequence 1,0,0,0,0....

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.

Thanks to Dennis for saving 3 bytes with better recursive handling inspired by a similar structure in this challenge.

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.

J, 18 bytes

[:*/3<:@|2+2<._&q:

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

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:

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)

PARI/GP, 7 bytes

moebius

Sadly möbius is not available. :)

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

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

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.

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.

Japt, 21 bytes

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

Test it online!

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.

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

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)

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.

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

CJam, 20 bytes

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

Run it against a range of inputs here.

Seems golfable.

Mathematica, 9 bytes

MoebiusMu

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