| Bytes | Lang | Time | Link |
|---|---|---|---|
| 071 | GNU sed | 160125T173937Z | Toby Spe |
| 318 | jBasher2 | 250908T150804Z | madeforl |
| 054 | YASEPL | 250905T135617Z | madeforl |
| 012 | Japt | 250905T143608Z | Shaggy |
| 046 | TIBASIC TI83 Plus | 250403T150545Z | madeforl |
| 022 | APLNARS | 250401T215050Z | Rosario |
| 5875 | Vyxal | 230518T114409Z | lyxal |
| 096 | Haskell | 230516T220135Z | Roman Cz |
| 006 | Factor + math.extras | 221228T162623Z | chunes |
| 064 | Java 8 | 181030T131902Z | Kevin Cr |
| 008 | 05AB1E | 160124T143030Z | Adnan |
| 065 | C# .NET Core | 181029T150501Z | Meerkat |
| 048 | Javascript ES6 | 181028T090721Z | user8371 |
| 011 | Seriously | 160930T195943Z | Sherlock |
| 035 | Julia | 160627T004608Z | Dennis |
| 048 | Python 2 | 160124T181023Z | xnor |
| 196 | Microsoft Office Excel | 160128T143416Z | Mats Gra |
| 018 | J | 160127T102842Z | alephalp |
| 018 | Seriously | 160124T223807Z | user4594 |
| 087 | Labyrinth | 160126T111605Z | Sp3000 |
| 007 | PARI/GP | 160125T162924Z | Charles |
| 016 | R | 160124T230756Z | mnel |
| 066 | Julia | 160125T004034Z | Alex A. |
| 015 | CJam | 160124T150047Z | Sp3000 |
| 009 | Pyth | 160124T205804Z | lirtosia |
| 021 | Japt | 160124T203858Z | ETHprodu |
| 011 | Pyth | 160124T200747Z | FryAmThe |
| 015 | MATL | 160124T172747Z | Luis Men |
| 016 | Pyth | 160124T142316Z | Denker |
| 007 | Jelly | 160124T135908Z | Adnan |
| nan | Ruby | 160124T143502Z | Doorknob |
| 020 | CJam | 160124T140740Z | Martin E |
| 009 | Mathematica | 160124T135916Z | Martin 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
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$†Ǎ*
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
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!
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;}
-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.
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*
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
:
}
? @ "}){/{=:
""({! " ;
} ) :}}:={%"
* _}}){ ;
{ #}):{{
")`%#/{+
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)
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.
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.
Pyth, 11
*{IPQ^_1lPQ
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.
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
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.
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
Mathematica, 9 bytes
MoebiusMu
Of course, Mathematica has a built-in. (And will probably be is beaten by Jelly anyway.)