Abandon all squares, ye who divide me

Question

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 code-golf. Shortest answer in bytes wins.

Standard loopholes apply.

Reference

• OEIS A007947

Answer 1

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.

Answer 2

Brachylog, 3 bytes

ḋd×

Try it online!

A very original answer...

Explanation

ḋ          Take the prime factors of the Input
 d         Remove duplicates
  ×        Multiply

Answer 3

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));
}

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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 n² 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.

Answer 8

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.

Answer 9

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

Answer 10

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)

Answer 11

Mathics, 40 bytes

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

Try it online!

Answer 12

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

Answer 13

Haskell, 31 bytes

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

Try it online!

Answer 14

Pyke, 3 bytes

P}B

Try it online!

P   -   factors(input)
 }  -  uniquify(^)
  B - product(^)

Answer 15

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.

Answer 16

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!

Answer 17

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

Answer 18

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;}

Answer 19

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.

Answer 20

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

Answer 21

Pari/GP, 28 bytes

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

Try it online!

Answer 22

Actually, 2 bytes

yπ

Try it online!

Explanation:

yπ
y   prime divisors
 π  product

Answer 23

Pyt, 3 bytes

←ϼΠ

Explanation:

←                  Get input
 ϼ                 Get list of unique prime factors
  Π                Compute product of list
                   Implicit print