15
\$\begingroup\$

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

References

\$\endgroup\$
5
  • \$\begingroup\$ Related. \$\endgroup\$
    – Leaky Nun
    Commented Aug 21, 2016 at 19:05
  • 1
    \$\begingroup\$ Will X always be greater than Y? \$\endgroup\$
    – Fatalize
    Commented Aug 22, 2016 at 8:03
  • \$\begingroup\$ @Fatalize What has that got to do with anything? \$\endgroup\$
    – Leaky Nun
    Commented Aug 22, 2016 at 8:10
  • \$\begingroup\$ 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. \$\endgroup\$
    – Fatalize
    Commented Aug 22, 2016 at 8:12
  • 1
    \$\begingroup\$ Your references list is the best illustration I've seen of the ridiculous arbitrariness of OEIS entry ordering. \$\endgroup\$
    – Sparr
    Commented Aug 22, 2016 at 19:32

20 Answers 20

7
\$\begingroup\$

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
\$\endgroup\$
6
6
\$\begingroup\$

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.
\$\endgroup\$
2
  • 1
    \$\begingroup\$ R*%⁸i0 is also 6 bytes. \$\endgroup\$
    – Leaky Nun
    Commented Aug 21, 2016 at 19:55
  • \$\begingroup\$ I think that warrants a separate answer. \$\endgroup\$
    – Dennis
    Commented Aug 21, 2016 at 19:59
6
\$\begingroup\$

JavaScript (ES7), 32 bytes

f=(x,y,i=1)=>i**y%x?f(x,y,i+1):i
\$\endgroup\$
2
  • \$\begingroup\$ You never defined f. I think you need to assign the function to f. \$\endgroup\$
    – kamoroso94
    Commented Aug 23, 2016 at 16:07
  • 1
    \$\begingroup\$ @kamoroso94 Sorry, I'm forever doing that. \$\endgroup\$
    – Neil
    Commented Aug 23, 2016 at 18:09
5
\$\begingroup\$

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.
\$\endgroup\$
5
\$\begingroup\$

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

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

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.

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

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.

\$\endgroup\$
3
  • \$\begingroup\$ Please post an explanation of how this code works for those nto familiar with your language, but otherwise good job, and nice first post. \$\endgroup\$ Commented Aug 21, 2016 at 20:23
  • \$\begingroup\$ That link seems interesting. \$\endgroup\$
    – Leaky Nun
    Commented Aug 21, 2016 at 20:24
  • 2
    \$\begingroup\$ Very nice first answer. \$\endgroup\$
    – Emigna
    Commented Aug 21, 2016 at 20:58
3
\$\begingroup\$

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
\$\endgroup\$
4
  • \$\begingroup\$ Stack manipulation much. \$\endgroup\$
    – Leaky Nun
    Commented Aug 21, 2016 at 19:12
  • 1
    \$\begingroup\$ Yep. I suspect Jelly will have a big advantage here, since it avoids all those "copy" and "swap" \$\endgroup\$
    – Luis Mendo
    Commented Aug 21, 2016 at 19:19
  • \$\begingroup\$ Don't you have find? \$\endgroup\$
    – Leaky Nun
    Commented Aug 21, 2016 at 20:01
  • \$\begingroup\$ @LeakyNun Yes, f, but that finds all nonzero indices. So it would have to be ~f1): negatve, find, get the first entry \$\endgroup\$
    – Luis Mendo
    Commented Aug 21, 2016 at 20:02
3
\$\begingroup\$

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.
\$\endgroup\$
3
  • \$\begingroup\$ @LeakyNun Waiting for one of your winning golf suggestions :D \$\endgroup\$
    – Sherlock9
    Commented Aug 21, 2016 at 19:34
  • \$\begingroup\$ @LeakyNun I'd be happy to post those approaches, too, unless you want to post them yourself. \$\endgroup\$
    – Sherlock9
    Commented Aug 21, 2016 at 19:37
  • \$\begingroup\$ +1 for the smirk ;) \$\endgroup\$
    – Leaky Nun
    Commented Aug 21, 2016 at 20:07
2
\$\begingroup\$

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.

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

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Delioth
    Commented Aug 22, 2016 at 21:48
  • \$\begingroup\$ @Delioth Interesting, thanks! I always just used the -e option, but I'll use that from now on. \$\endgroup\$
    – juh
    Commented Aug 22, 2016 at 23:36
  • \$\begingroup\$ @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. \$\endgroup\$
    – juh
    Commented Sep 4, 2016 at 1:32
1
\$\begingroup\$

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

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

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 .. *
}
\$\endgroup\$
0
\$\begingroup\$

Mathematica, 36 bytes

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

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!

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

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
\$\endgroup\$
0
\$\begingroup\$

PHP, 55 33 bytes

$i=1;while($i**$y%$x)$i++;echo$i;
\$\endgroup\$
0
\$\begingroup\$

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++$\**$'%$`}{
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
-1
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.