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

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 . Solution with lowest byte-count wins.

# References

• Aug 21, 2016 at 19:05
• Will X always be greater than Y? Aug 22, 2016 at 8:03
• @Fatalize What has that got to do with anything? Aug 22, 2016 at 8:10
• There is no test case where X is less than Y, and it can reduce the length of some answers (at least mine) if X is always greater than Y. I would rather have that X can be either bigger or smaller, but then one test case for the latter would be great. Aug 22, 2016 at 8:12
• Your references list is the best illustration I've seen of the ridiculous arbitrariness of OEIS entry ordering. Aug 22, 2016 at 19:32

# Brachylog, 19171615 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

• 1 byte off Aug 21, 2016 at 19:22
• @LeakyNun Thanks. This will be much slower though. Aug 21, 2016 at 19:23
• Why will this be slower? Aug 21, 2016 at 19:25
• Slower still, but another byte off Aug 21, 2016 at 19:26
• To quote the famous Fatalize: "don't care about complexity" Aug 21, 2016 at 19:46

# Jelly, 6 bytes

ÆE÷ĊÆẸ


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

• R*%⁸i0 is also 6 bytes. Aug 21, 2016 at 19:55
• I think that warrants a separate answer. Aug 21, 2016 at 19:59

## JavaScript (ES7), 32 bytes

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

• You never defined f. I think you need to assign the function to f. Aug 23, 2016 at 16:07
• @kamoroso94 Sorry, I'm forever doing that.
– Neil
Aug 23, 2016 at 18:09

# Jelly, 6 bytes

R*%⁸i0


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


# Python 3, 6043 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

• def f(x,y,i=1):¶ while i**y%x:i+=1¶ print(i) Aug 21, 2016 at 19:23
• @LeakyNun Thanks. I just thought of a slightly shorter way to do it (43 vs 44) with recursion. Aug 21, 2016 at 19:34
• 39: f=lambda x,y,z=1:z**y%x<1or-~f(x,y,z+1) Aug 21, 2016 at 19:35
• @Sp3000 Doesn't your function return True instead of z? Aug 21, 2016 at 19:44
• @LeakyNun You're missing the -~ part, but yes it would return True if x was 1. Aug 21, 2016 at 19:52

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.

• Also 31: x#y=until(\n->mod(n^y)x<1)(+1)0
– xnor
Aug 22, 2016 at 5:41

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

• Please post an explanation of how this code works for those nto familiar with your language, but otherwise good job, and nice first post. Aug 21, 2016 at 20:23
• That link seems interesting. Aug 21, 2016 at 20:24
• Very nice first answer. Aug 21, 2016 at 20:58

# 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

• Stack manipulation much. Aug 21, 2016 at 19:12
• Yep. I suspect Jelly will have a big advantage here, since it avoids all those "copy" and "swap" Aug 21, 2016 at 19:19
• Don't you have find? Aug 21, 2016 at 20:01
• @LeakyNun Yes, f, but that finds all nonzero indices. So it would have to be ~f1): negatve, find, get the first entry Aug 21, 2016 at 20:02

# 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.
╜      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.

• @LeakyNun Waiting for one of your winning golf suggestions :D Aug 21, 2016 at 19:34
• @LeakyNun I'd be happy to post those approaches, too, unless you want to post them yourself. Aug 21, 2016 at 19:37
• +1 for the smirk ;) Aug 21, 2016 at 20:07

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

• @TheBikingViking Thanks for pointing that out. I'll edit it after having my late lunch Aug 22, 2016 at 13:52
• if you use which.min, you could get rid of the ==0. The modulus will return a number, which be no lower than 0. Aug 22, 2016 at 14:31
• @user5957401 Edited.Bolshoe spasibo... Aug 22, 2016 at 16:16
• For the same length of 34 bytes you also had the similar function(x,y)which(!(1:x)^y%%x)[1]. Aug 23, 2016 at 6:58

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

• You technically don't need the ? at the beginning, as a standard way to invoke some things is > echo "x y [program]"|dc, where x and y are the same as the Question- x and y will be dropped onto the stack as normal. Aug 22, 2016 at 21:48
• @Delioth Interesting, thanks! I always just used the -e option, but I'll use that from now on.
– juh
Aug 22, 2016 at 23:36
• @Delioth, for me, using quotes throws errors reminding me that " is not implemented in dc, while not using quotes obviously gives shell errors. Is there anything to be done about this? I know stderr can be ignored, but it still bothers me.
– juh
Sep 4, 2016 at 1:32

# 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

# 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｣

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  ## PHP, 55 33 bytes $i=1;while($i**$y%$x)$i++;echo$i;  # 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++$\**$'%$}{


# 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


# 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;}
`
• You're using $z where you should be using$x and I don't think you're incrementing \$i in the loop Aug 22, 2016 at 15:43