Smallest positive number whose y-th power is divisible by x

Question

Task

Given integers x and y which are both at least 2, find the smallest positive number whose y-th power is divisible by x.

Example

Given x=96 and y=2, the output should be 24 since 24 is the smallest positive n satisfying n^2 is divisible by 96.

Testcases

x  y output
26 2 26
96 2 24
32 3 4
64 9 2
27 3 3

Scoring

This is code-golf. Solution with lowest byte-count wins.

References

• y=2: OEIS A019554
• y=3: OEIS A019555
• y=4: OEIS A053166
• y=5: OEIS A015052
• y=6: OEIS A015054

Answer 1

Brachylog, 19 17 16 15 12 bytes

2 bytes saved thanks to @LeakyNun.

:[I:1]*$r=#>

Try it online!

Explanation

               Input = [X, Y]
:[I:1]*        Get a list [X*I, Y] (I being any integer at this point)
       $r=     Get the first integer which is the Yth root of X*I
          #>   This integer must be strictly positive
               This integer is the Output

Answer 2

Jelly, 6 bytes

ÆE÷ĊÆẸ

Try it online! or verify all test cases.

How it works

ÆE÷ĊÆẸ  Main link. Arguments: x, y

ÆE      Yield the exponents of x's prime factorization.
  ÷     Divide them by y.
   Ċ    Ceil; round the quotients up to the nearest integer.
    ÆẸ  Return the integer with that exponents in its prime factorization.

Answer 3

JavaScript (ES7), 32 bytes

f=(x,y,i=1)=>i**y%x?f(x,y,i+1):i

Answer 4

Python 3, 60 43 39 bytes

Thanks to @LeakyNun and @Sp3000 for help

f=lambda x,y,i=1:i**y%x<1or-~f(x,y,i+1)

A function that takes input via argument and returns the output.

How it works

The function uses recursion to repeatedly check integers i, starting with i=1, until one satisfying the required condition, here i**y%x<1, is found. This is achieved by taking the logical or of the condition and the result of the expression for i+1 incremented, which here is -~f(x,y,i+1). This expression continuously evaluates as False until a satisfying value j is found, at which point it evaluates to True and recursion stops. Since these are respectively equivalent to 0 and 1 in Python, and the function has repeatedly been adding 1 via the incrementing part, the function returns (j-1)*False + True + (j-1)*1 = (j-1)*0 + 1 + (j-1)*1 = 1 + j-1 = j, as required.

Try it on Ideone

Answer 5

Jelly, 6 bytes

R*%⁸i0

Try it online! or verify all test cases.

How it works

R*%⁸i0  Main link. Arguments: x, y

R       Yield range from 1 to x inclusive.
 *      Raise each to power y.
  %⁸    Take modulo of each with base x.
    i0  Find the 1-based index of the first
        occurence of zero, returns.

Answer 6

Haskell, 31 bytes

x#y=[n|n<-[1..],mod(n^y)x<1]!!0

Usage example: 96#2 -> 24.

Direct implementation: try all integers n, keep those that meet the condition and pick the first one.

Answer 7

05AB1E (10 bytes)

>GN²m¹ÖiNq

Try it online

• > Reads the first argument, increments it, and pushes it on the stack
• G pops the stack (a) and starts a loop that contains the rest of the program where N takes on the value 1, 2, ... a - 1.
• N²m pushes N and the second entry from the input history, then pops them both and pushes the first to the power of the second.
• ¹ pushes the first entry from the input history onto the stack.
• Ö pops the previous two stack entries, then pushes a % b == 0 on the stack.
• i pops that from the stack. If true, it executes the rest of the program; otherwise, the loop continues.
• N pushes N on the stack.
• q terminates the program.

When the program terminates, the top value of the stack is printed.

Answer 8

MATL, 9 bytes

y:w^w\&X<

Try it online!

Explanation

y       % Take x and y implicitly. Push x again
        % STACK: x, y, x
:       % Range from 1 to x
        % STACK: x, y, [1, 2, ..., x]
w       % Swap
        % STACK: x, [1, 2, ..., x], y
^       % Power, element-wise
        % STACK: x, [1^y,  2^y, ..., x^y]
w       % Swap
        % STACK: [1^y, 2^y, ..., x^y], x
\       % Modulo, element-wise
        % STACK: [mod(1^y,x), mod(2^y,x), ..., mod(x^y,x)]
        % A 0 at the k-th entry indicates that x^y is divisible by x. The last entry
        % is guaranteed to be 0
&X<     % Arg min: get (1-based) index of the first minimum (the first zero), say n
        % STACK: n
        % Implicitly display

Answer 9

Actually, 12 11 bytes

Many thanks to Leaky Nun for his many suggestions. Golfing suggestions welcome. Try it online!

;)R♀ⁿ♀%0@íu

Original 12-byte approach. Try it online!

1WX│1╖╜ⁿ%WX╜

Another 12-byte approach. Try it online!

w┬i)♀/♂K@♀ⁿπ

A 13-byte approach. Try it online!

k╗2`╜iaⁿ%Y`╓N

Ungolfing:

First algorithm

       Implicitly pushes y, then x.
;      Duplicate x.
)      Rotate duplicate x to bottom of the stack.
R      Range [1, x] (inclusive).
♀ⁿ     Map a**y over the range.
♀%     Map a**y%x over the range.
0@í    new_list.index(0)
u      Increment and print implicitly at the end of the program.

Original algorithm

       Implicitly pushes x, then y.
1WX    Pushes a truthy value to be immediately discarded 
         (in future loops, we discard a**y%x)
|      Duplicates entire stack.
         Stack: [y x y x]
1╖     Increment register 0.
╜      Push register 0. Call it a.
ⁿ      Take a to the y-th power.
%      Take a**y mod x.
W      If a**y%x == 0, end loop.
X      Discard the modulus.
╜      Push register 0 as output.

Third algorithm

       Implicitly pushes y, then x.
w      Pushes the full prime factorization of x.
┬      Transposes the factorization (separating primes from exponents)
i      Flatten (into two separate lists of primes and exponents).
)      Rotate primes to the bottom of the stack.
♀/     Map divide over the exponents.
♂K     Map ceil() over all of the divided exponents.
@      Swap primes and modified exponents.
♀ⁿ     Map each prime ** each exponent.
π      Product of that list. Print implicitly at the end of the program.

Fourth algorithm

     Implicitly pushes x, then y.
k╗   Turns stack [x y] into a list [x, y] and saves to register 0.
2    Pushes 2.
  `    Starts function with a.
  ╜i   Pushes register 0 and flattens. Stack: [x y a]
  a    Inverts the stack. Stack: [a y x]
  ⁿ%   Gets a**y%x.
  Y    Logical negate (if a**y is divisible by x, then 1, else 0)
  `    End function.
╓    Push first (2) values where f(x) is truthy, starting with f(0).
N    As f(0) is always truthy, get the second value.
     Print implicitly at the end of the program.

Answer 10

dc, 23 22 bytes

Thanks to Delioth for his tip about input methods, saving a byte

sysxz[zdlylx|0<F]dsFxp

Uses the stack depth operator z for incrementing the test case directly on the stack, and the modular exponentiation operator | for, well, modular exponentiation. Repeat testing until remainder is not greater than zero.

Answer 11

R, 61 bytes, 39 bytes, 37 bytes, 34 bytes

I'm still a newbie in R programming and it turns out this is my first function I create in R (Yay!) so I believe there's still room for improvement.

function(x,y){for(n in 2:x){if(n^y%%x==0){cat(x,y,n);break}}}

Online test can be conducted here: RStudio on rollApp.

---

Major progress:

function(x,y){which.max((1:x)^y%%x==0)}

which.max works because it returns the highest value in a vector and if there are multiple it will return the first. In this case, we have a vector of many FALSEs (which are 0s) and a few TRUEs (which are 1s), so it will return the first TRUE.

---

Another progress:

function(x,y)which.max((1:x)^y%%x==0)

Finally, it beats out the answer using Python by two bytes. :)

Another progress: (Again!)

function(x,y)which.min((1:x)^y%%x)

---

Many thanks to Axeman and user5957401 for the help.

Answer 12

05AB1E, 8 bytes

Lsm¹%0k>

Explanation

L         # range(1,x) inclusive
 sm       # each to the power of y
   ¹%     # each mod x
     0k   # find first index of 0 (0-based)
       >  # increment to 1-based

Try it online

Answer 13

Perl 6,  26  25 bytes

{first * **$^y%%$^x,1..$x}
{first * **$^y%%$^x,1..*}

Explanation:

# bare block with two placeholder parameters ｢$^y｣ and ｢$^x｣
{
  # find the first value
  first

  # where when it ｢*｣ is taken to the power
  # of the outer blocks first parameter ｢$^y｣
  * ** $^y
  # is divisible by the outer blocks second parameter ｢$^x｣
  %% $^x,

  # out of the values from 1 to Inf
  1 .. *
}

Answer 14

Mathematica, 36 bytes

(i=1;While[n=i++;Mod[n^#2,#]!=0];n)&

Answer 15

Dyalog APL, 11 bytes

Translation of this.

0⍳⍨⊣|(⍳⊣)*⊢

0⍳⍨ find the first zero in
⊣| the division remainders when x divides
(⍳⊣)* the integers one through x, raised to the power of
⊢ y

TryAPL online!

Answer 16

PowerShell v2+, 48 bytes

param($x,$y)(1..$x|?{!(("$_*"*$y+1|iex)%$x)})[0]

Takes input $x and $y. Constructs a range from 1 to $x, then uses Where-Object to filter those numbers. The filter takes the string "$_*" (i.e., the current number with an asterisk) and uses string-multiplication to concatenate those $y times, then tacks on a final 1 at the end, then pipes that to iex (short for Invoke-Expression and similar to eval). This takes the place of [math]::Pow($_,$y), since PowerShell doesn't have an exponentiation operator, and is two bytes shorter. That's fed into the modulo operator % with $x -- thus, if it's divisible, this will be 0, so we encapsulate that in parens and take the Boolean-not !(...) thereof. Thus, if its divisible, it'll be included by this filter, and all other numbers will be excluded.

Finally, we encapsulate the resultant numbers in parens (...) and take the [0] index. Since the range entered sorted 1..$x, this will be the smallest. That's left on the pipeline and printing is implicit.

Test cases

PS C:\Tools\Scripts\golfing> (26,2),(96,2),(32,3),(64,9),(27,3)|%{($_-join', ')+' -> '+(.\smallest-positive-number-divisor.ps1 $_[0] $_[1])}
26, 2 -> 26
96, 2 -> 24
32, 3 -> 4
64, 9 -> 2
27, 3 -> 3

Answer 17

PHP, 55 33 bytes

$i=1;while($i**$y%$x)$i++;echo$i;

Answer 18

Perl, 29 26 bytes

Includes +3 for -p (not +1 since the code contains ')

Run with the input on STDIN

power.pl <<< "96 2"

power.pl:

#!/usr/bin/perl -p
/ /;1while++$\**$'%$`}{

Answer 19

Pyth, 9 bytes

AQf!%^THG

A program that takes input of a list of the form [x, y] on STDIN and prints the result.

Try it online

How it works

AQf!%^THG  Program. Input: Q
AQ         G=Q[0];H=Q[1]
  f        First truthy input T in [1, 2, 3, ...] with function:
     ^TH    T^H
    %   G   %G
   !        Logical not (0 -> True, all other modulus results -> False)
           Implicitly print

Answer 20

PHP 59 bytes

Sorry, but I can't test this from my mobile. :)

function blahblah($x,$y){
  for($i=0;1;$i++){
    if(!$i^$y%$x){
      return $i;
    }
  }
}

Golfed

function b($x,$y){for($i=0;1;$i++){if(!$i^$y%$x)return $i;}