37
\$\begingroup\$

Definitions

  • A perfect square is an integer which can be expressed as the square of another integer. For example, 36 is a perfect square because 6^2 = 36.
  • A squarefree number is an integer which is not divisible by any perfect square, except by 1. For example, 10 is a squarefree number. However, 12 is not a squarefree number, because 12 is divisible by 4 and 4 is a perfect square.

Task

Given a positive integer n, output the largest squarefree number which divides n.

Testcases

n   output
1   1
2   2
3   3
4   2
5   5
6   6
7   7
8   2
9   3
10  10
11  11
12  6
13  13
14  14
15  15
16  2
17  17
18  6
19  19
20  10
21  21
22  22
23  23
24  6
25  5
26  26
27  3
28  14
29  29
30  30
31  31
32  2
33  33
34  34
35  35
36  6
37  37
38  38
39  39
40  10
41  41
42  42
43  43
44  22
45  15
46  46
47  47
48  6
49  7
50  10

Scoring

This is . Shortest answer in bytes wins.

Standard loopholes apply.

Reference

\$\endgroup\$
  • 1
    \$\begingroup\$ ...and is called the radical - so 1980's! \$\endgroup\$ – Jonathan Allan May 11 '17 at 16:14
  • \$\begingroup\$ Closely related, just multiply the two outputs. Edit: Never mind, it only matches on cubefree numbers. \$\endgroup\$ – xnor May 11 '17 at 20:13

23 Answers 23

45
\$\begingroup\$

05AB1E, 2 bytes

fP

Try it online!

How it works

f   Implicitly take input and compute the integer's unique prime factors.
 P  Take the product.
\$\endgroup\$
  • 26
    \$\begingroup\$ >_> really...?? \$\endgroup\$ – HyperNeutrino May 11 '17 at 16:02
  • \$\begingroup\$ @HyperNeutrino yep - if a number is not square-free it is because some of its prime factor(s) have multiplicity. \$\endgroup\$ – Jonathan Allan May 11 '17 at 16:07
  • \$\begingroup\$ @JonathanAllan I'm just interested in the built-in for unique prime factors. I wish Jelly had one of those... \$\endgroup\$ – HyperNeutrino May 11 '17 at 16:09
  • \$\begingroup\$ @HyperNeutrino It's 05AB1E, get used to it. 05AB1E has some really redundant builtins that apparently save bytes. \$\endgroup\$ – Erik the Outgolfer May 11 '17 at 16:33
  • 6
    \$\begingroup\$ Correction, "save bytes", there's no probably about it. \$\endgroup\$ – Draco18s May 11 '17 at 21:43
14
\$\begingroup\$

Brachylog, 3 bytes

ḋd×

Try it online!

A very original answer...

Explanation

ḋ          Take the prime factors of the Input
 d         Remove duplicates
  ×        Multiply
\$\endgroup\$
  • 1
    \$\begingroup\$ Again, Brachylog beats Jelly because a two-byte atom is only one byte here. >:-P \$\endgroup\$ – HyperNeutrino May 11 '17 at 16:21
  • 4
    \$\begingroup\$ Jelly having a lot of builtins is often seen as an advantage; but more builtins means that they need longer names on average. So there are tradeoffs involved in golfing language design. \$\endgroup\$ – user62131 May 11 '17 at 17:44
  • 2
    \$\begingroup\$ I'm not trying to be "that guy", and maybe I just misunderstand byte counting, but isn't this 6 bytes? mothereff.in/byte-counter#ḋd× \$\endgroup\$ – Captain Man May 11 '17 at 18:15
  • 5
    \$\begingroup\$ @CaptainMan Brachylog uses a 256 chars custom code page which you can find here. \$\endgroup\$ – Fatalize May 11 '17 at 18:16
14
\$\begingroup\$

JavaScript (ES6), 55 54 50 46 bytes

Quoting OEIS:
a(n) is the smallest divisor u of n such that n divides u^n

Updated implementation:
a(n) is the smallest divisor u of n positive integer u such that n divides u^n

let f =

n=>(g=(p,i=n)=>i--?g(p*p%n,i):p?g(++u):u)(u=1)

for(n = 1; n <= 50; n++) {
  console.log(n,f(n));
}

\$\endgroup\$
  • \$\begingroup\$ Nice approach to the problem, esp. given lack of builtin factorization \$\endgroup\$ – Riking May 13 '17 at 16:42
12
\$\begingroup\$

MATL, 6 4 bytes

2 bytes saved with help from @LeakyNun

Yfup

Try it online!

Explanation

Consider input 48.

Yf   % Implicit input. Push prime factors with repetitions.  STACK: [2 2 2 2 3]
u    % Unique.                                               STACK: [2 3]
p    % Product of array. Implicit display.                   STACK: 6
\$\endgroup\$
  • \$\begingroup\$ Out-golfed \$\endgroup\$ – Leaky Nun May 11 '17 at 16:01
  • \$\begingroup\$ @LeakyNun Heh, I was about to post that :-) Thanks \$\endgroup\$ – Luis Mendo May 11 '17 at 16:03
11
\$\begingroup\$

Jelly, 4 bytes

ÆfQP

Try it online!

ÆfQP  Main link, argument is z
Æf    Takes the prime factors of z
  Q   Returns the unique elements of z
   P  Takes the product
\$\endgroup\$
9
\$\begingroup\$

CJam, 8 bytes

rimf_&:*

Why does every operation in this program have to be 2 bytes -_-

Try it online!

ri       e# Read int from input
  mf     e# Get the prime factors
    _&   e# Deduplicate
      :* e# Take the product of the list
\$\endgroup\$
  • \$\begingroup\$ I couldn't find a way to deduplicate. Nice! \$\endgroup\$ – Luis Mendo May 11 '17 at 16:17
  • \$\begingroup\$ @LuisMendo I just discovered that recently. I always thought it was multiset intersection but apparently it's just normal set intersection. \$\endgroup\$ – Business Cat May 11 '17 at 16:18
9
\$\begingroup\$

Retina, 36 30 28 bytes

+`((^|\3)(^(1+?)|\3\4))+$
$3

Input and output in unary.

Try it online! (Includes a header and footer for decimal <-> unary conversion and to run multiple test cases at once.)

Explanation

The idea is to match the input as a square times some factor. The basic regex for matching a square uses a forward-reference to match sums of consecutive odd integers:

(^1|11\1)+$

Since we don't want to match perfect squares, but numbers that are divisible by a square, we replace that 1 with a backreference itself:

(^(1+?)|\1\2\2)+$

So now the outer group 1 will be used n times where n2 is the largest square that divides the input and group 2 stores the remaining factor. What we want is to divide the integer by n to remove the square. The result can be expressed as the number of iterations of group 1 times group 2, but this is a bit tricky to do. Retina's $* will probably soon be improved to take a non-character token as its right hand argument in which case we could simply replace this with $#1$*$2, but that doesn't work yet.

Instead, we decompose the odd numbers differently. Let's go back to the simpler example of matching perfect squares with (^1|11\1)+$. Instead of having a counter \1 which is initialised to 1 and incremented by 2 on each iteration, we'll have two counters. One is initialised to 0 and one is initialised to 1, and they're both incremented by 1 on each iteration. So we've basically decomposed the odd numbers 2n+1 into (n) + (n+1). The benefit is that we'll end up with n in one of the groups. In its simplest form, that looks like this:

((^|1\2)(^1|1\3))+$

Where \2 is n and \3 is n+1. However, we can do this a bit more efficiently by noticing that the n+1 of one iteration is equal to the n of the next iteration, so we can save on a 1 here:

((^|\3)(^1|1\3))+$

Now we just need to go back to using an initial factor instead of 1 to match inputs that are divided by a perfect square:

((^|\3)(^(1+?)|\3\4))+$

Now all we need to do is replace this entire thing with $3 at the end, which stores the initial factor times the number of steps, which drops one factor of the square from the input.

This is done repeatedly with the + at the very beginning of the program, to account for inputs that contain higher powers than squares.

\$\endgroup\$
8
\$\begingroup\$

Octave, 27 bytes

@(x)prod(unique(factor(x)))

Similar approach as the other answers. The difference is: The functions have much longer names. I believe the code explains itself really: Takes the product of the unique prime factors of a number.

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

Wolfram Language, 29 28 bytes

-1 Thanks to @Martin Ender ♦

Most[1##&@@FactorInteger@#]&

Explanation:

           FactorInteger@#    (*Get prime factorization as {{a,b},{c,d}}*)
     1##&@@                   (*Multiply list elements together, to get the product of the factors and the product of their exponents*)
Most[                     ]&  (*Take the first element*)
\$\endgroup\$
  • 2
    \$\begingroup\$ Just realized this is basically @GregMartin's comment on the Mathics answer, only less golfy... \$\endgroup\$ – Scott Milner May 11 '17 at 18:43
  • \$\begingroup\$ Don't feel bad, I had the even less golfy answer of Times@@(#&@@@FactorInteger@#)& \$\endgroup\$ – Ian Miller May 12 '17 at 13:04
  • \$\begingroup\$ Most leaves it as a list. You need First to get the value. \$\endgroup\$ – Ian Miller May 12 '17 at 13:06
  • \$\begingroup\$ @IanMiller I realize that, but it is less bytes to just return a list with only one element. I assumed that that was ok, since it is still a reasonable output. \$\endgroup\$ – Scott Milner May 12 '17 at 13:36
7
\$\begingroup\$

Python, 37 bytes

f=lambda n,r=1:1>>r**n%n or-~f(n,r+1)

Try it online!

The largest squarefree divisor of n is that smallest number r with all of n's prime factors. We can check this as r**n%n==0, since r**n make n copies of each prime factor of r, and is divisible by n only if each of n's prime factors is represented.

The 1>>r**n%n is equivalent to int(r**n%n==0). If True can be used output 1, it's 2 bytes shorter to do.

f=lambda n,r=1:r**n%n<1or-~f(n,r+1)
\$\endgroup\$
6
\$\begingroup\$

Mathics, 40 bytes

Times@@(Transpose@FactorInteger@#)[[1]]&

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Times@@#&@@Transpose@FactorInteger@#& saves 3 bytes (#&@@ is standard trick for [[1]] and in cases like this it can often save some extra bytes on parentheses). \$\endgroup\$ – Martin Ender May 11 '17 at 18:25
  • \$\begingroup\$ You can also use Thread instead of Transpose. In Mathematica there's also a 3-byte operator for Transpose, but I don't know whether Mathics supports it. \$\endgroup\$ – Martin Ender May 11 '17 at 18:26
  • 6
    \$\begingroup\$ #&@@(1##&@@FactorInteger@#)& avoids the need to Transpose altogether. (1##&@@ is just Times@@ in disguise, which works great on the ordered pairs yielded by FactorInteger; and '#&@@ is First@ in disguise.) \$\endgroup\$ – Greg Martin May 11 '17 at 18:35
  • \$\begingroup\$ @GregMartin that's basically your own solution, feel free to post it, if you want. \$\endgroup\$ – Pavel May 13 '17 at 8:02
  • \$\begingroup\$ Looks like Scott Milner got it anyway :) \$\endgroup\$ – Greg Martin May 13 '17 at 8:13
5
\$\begingroup\$

Alice, 4 bytes

iDo@

Try it online!

Input and output are given as the code point of a character (works for all valid Unicode code points).

Explanation

Well, Alice has a built-in D whose definition is "Deduplicate prime factors". That is, as long as a value is divisible by some p2 for a prime p, divide that value by p. This happens to be exactly the function required in this challenge. The rest is just input, output, terminate the program.

The reason this was added to Alice actually has nothing to do with this integer sequence. I was trying to stick to a theme of associating divisors with substrings and prime factors with characters. And I needed a function that goes with "deduplicate characters" (which is much more useful in general, because it let's you treat strings as sets, especially when used together with the various multiset operators).

\$\endgroup\$
  • \$\begingroup\$ The sad part is, even with a builtin this isn't the shortest answer. \$\endgroup\$ – Rɪᴋᴇʀ May 11 '17 at 18:40
  • \$\begingroup\$ @Riker Well, that's because Alice isn't a golfing language so it needs explicit I/O and (since it's a 2D language) program termination. \$\endgroup\$ – Martin Ender May 11 '17 at 18:41
  • \$\begingroup\$ Yeah, still somewhat sad though. \$\endgroup\$ – Rɪᴋᴇʀ May 11 '17 at 19:07
  • \$\begingroup\$ @ConorO'Brien We just had this discussion elsewhere, and that's only valid if the stand-alone operator is an expression which evaluates to the function (which isn't the case here, since functions/operators aren't first-class values). codegolf.meta.stackexchange.com/a/7206/8478 \$\endgroup\$ – Martin Ender May 14 '17 at 19:52
  • \$\begingroup\$ @ConorO'Brien sorry that was an exclusive "we". \$\endgroup\$ – Martin Ender May 14 '17 at 20:51
4
\$\begingroup\$

Haskell, 31 bytes

f n=until(\r->r^n`mod`n<1)(+1)1

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Pyke, 3 bytes

P}B

Try it online!

P   -   factors(input)
 }  -  uniquify(^)
  B - product(^)
\$\endgroup\$
3
\$\begingroup\$

Prolog (SWI), 84 39 bytes

f(N,P):-between(1,N,P),P^N mod N=:=0,!.

Try it online!

Adapted the idea of @xnor's Haskell answer to Prolog.

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

PHP, 70 Bytes

for($r=1,$i=2;1<$n=&$argn;)$n%$i?++$i:$n/=$i+!($r%$i?$r*=$i:1);echo$r;

Try it online!

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

Pyth, 8 6 bytes

*F+1{P

*-2 bytes thanks to @LeakyNun

Would be 3 if Pyth had a built-in for products of lists...

Try it!

*F+1{P
      Q     # Implicit input
     P      # Prime factors of the input
    {       # Deduplicate
  +1        # Prepend 1 to the list (for the case Q==1)
*F          # Fold * over the list
\$\endgroup\$
  • \$\begingroup\$ You can use *F+1{P instead. \$\endgroup\$ – Leaky Nun May 11 '17 at 17:40
1
\$\begingroup\$

C, 65 50 bytes

Thanks to @Ørjan Johansen for removing the need for r. Thanks to this and some other dirty tricks I was able to squeeze 15 bytes off!

d;f(n){for(d=1;d++<n;)n%(d*d)||(n/=d--);return n;}

while is gone and replaced with || and index twiddling. <= should have been < all along.

<= turned to < by moving the increment to get n%(++d*d) (should be well defined due to operator precedence).


Original code:

d;r;f(n){for(r=d=1;d++<=n;)while(n%d<1)r*=r%d?d:1,n/=d;return r;}
\$\endgroup\$
  • \$\begingroup\$ I think you can shorten it by removing r and instead use while(n%(d*d)<1)n/=d;. \$\endgroup\$ – Ørjan Johansen May 16 '17 at 0:55
  • \$\begingroup\$ @ØrjanJohansen That seems right. I was thinking construction rather than reduction. I have some additional improvements to add, will update soon. \$\endgroup\$ – algmyr May 16 '17 at 1:40
  • \$\begingroup\$ ++d*d is absolutely not well defined by the C standards - it's a classic case of explicitly undefined behavior. But we're going by implementations here, anyway. \$\endgroup\$ – Ørjan Johansen May 16 '17 at 2:35
  • \$\begingroup\$ Actually, shouldn't d++<n, which is well defined, still work? I think the old version went all the way to n+1 (harmlessly). \$\endgroup\$ – Ørjan Johansen May 16 '17 at 2:45
  • \$\begingroup\$ You're probably right about the undefined behavior. For some reason I thought that operator precedence would solve that. Most examples I've seen of UB uses same priority operators, but of course there is a data race here as well. You're also right about d++<n being correct, for some reason I didn't see that when I rewrote the code. \$\endgroup\$ – algmyr May 16 '17 at 3:10
0
\$\begingroup\$

Axiom, 89 bytes

f(x:PI):PI==(x=1=>1;g:=factor x;reduce(*,[nthFactor(g,i) for i in 1..numberOfFactors g]))

test and results

(38) -> [[i, f(i)] for i in 1..30 ]
   (38)
   [[1,1], [2,2], [3,3], [4,2], [5,5], [6,6], [7,7], [8,2], [9,3], [10,10],
    [11,11], [12,6], [13,13], [14,14], [15,15], [16,2], [17,17], [18,6],
    [19,19], [20,10], [21,21], [22,22], [23,23], [24,6], [25,5], [26,26],
    [27,3], [28,14], [29,29], [30,30]]

this is the one not use factor() function

g(x:PI):PI==(w:=sqrt(x);r:=i:=1;repeat(i:=i+1;i>w or x<2=>break;x rem i=0=>(r:=r*i;repeat(x rem i=0=>(x:=x quo i);break)));r)

but it is only 125 bytes

\$\endgroup\$
0
\$\begingroup\$

R, 52 bytes

`if`((n=scan())<2,1,prod(unique(c(1,gmp::factorize(n))))

reads n from stdin. Requires the gmp library to be installed (so TIO won't work). Uses the same approach as many of the above answers, but it crashes on an input of 1, because factorize(1) returns an empty vector of class bigz, which crashes unique, alas.

\$\endgroup\$
  • \$\begingroup\$ This outputs 12 when I input 12. \$\endgroup\$ – Flounderer May 12 '17 at 4:09
  • \$\begingroup\$ @Flounderer you are correct, I have updated the code. \$\endgroup\$ – Giuseppe May 12 '17 at 15:35
0
\$\begingroup\$

Actually, 2 bytes

Try it online!

Explanation:

yπ
y   prime divisors
 π  product
\$\endgroup\$
0
\$\begingroup\$

Pari/GP, 28 bytes

n->factorback(factor(n)[,1])

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Pyt, 3 bytes

←ϼΠ

Explanation:

←                  Get input
 ϼ                 Get list of unique prime factors
  Π                Compute product of list
                   Implicit print
\$\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.