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\$
  • \$\begingroup\$ Related. \$\endgroup\$ – Leaky Nun Aug 21 '16 at 19:05
  • 1
    \$\begingroup\$ Will X always be greater than Y? \$\endgroup\$ – Fatalize Aug 22 '16 at 8:03
  • \$\begingroup\$ @Fatalize What has that got to do with anything? \$\endgroup\$ – Leaky Nun Aug 22 '16 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 Aug 22 '16 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 Aug 22 '16 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
\$\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\$
  • 1
    \$\begingroup\$ R*%⁸i0 is also 6 bytes. \$\endgroup\$ – Leaky Nun Aug 21 '16 at 19:55
  • \$\begingroup\$ I think that warrants a separate answer. \$\endgroup\$ – Dennis Aug 21 '16 at 19:59
6
\$\begingroup\$

JavaScript (ES7), 32 bytes

f=(x,y,i=1)=>i**y%x?f(x,y,i+1):i
\$\endgroup\$
  • \$\begingroup\$ You never defined f. I think you need to assign the function to f. \$\endgroup\$ – kamoroso94 Aug 23 '16 at 16:07
  • 1
    \$\begingroup\$ @kamoroso94 Sorry, I'm forever doing that. \$\endgroup\$ – Neil Aug 23 '16 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\$
  • 1
    \$\begingroup\$ def f(x,y,i=1):¶ while i**y%x:i+=1¶ print(i) \$\endgroup\$ – Leaky Nun Aug 21 '16 at 19:23
  • \$\begingroup\$ @LeakyNun Thanks. I just thought of a slightly shorter way to do it (43 vs 44) with recursion. \$\endgroup\$ – TheBikingViking Aug 21 '16 at 19:34
  • 2
    \$\begingroup\$ 39: f=lambda x,y,z=1:z**y%x<1or-~f(x,y,z+1) \$\endgroup\$ – Sp3000 Aug 21 '16 at 19:35
  • \$\begingroup\$ @Sp3000 Doesn't your function return True instead of z? \$\endgroup\$ – Leaky Nun Aug 21 '16 at 19:44
  • \$\begingroup\$ @LeakyNun You're missing the -~ part, but yes it would return True if x was 1. \$\endgroup\$ – Sp3000 Aug 21 '16 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\$
  • 2
    \$\begingroup\$ Also 31: x#y=until(\n->mod(n^y)x<1)(+1)0 \$\endgroup\$ – xnor Aug 22 '16 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\$
  • \$\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\$ – Rohan Jhunjhunwala Aug 21 '16 at 20:23
  • \$\begingroup\$ That link seems interesting. \$\endgroup\$ – Leaky Nun Aug 21 '16 at 20:24
  • 2
    \$\begingroup\$ Very nice first answer. \$\endgroup\$ – Emigna Aug 21 '16 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\$
  • \$\begingroup\$ Stack manipulation much. \$\endgroup\$ – Leaky Nun Aug 21 '16 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 Aug 21 '16 at 19:19
  • \$\begingroup\$ Don't you have find? \$\endgroup\$ – Leaky Nun Aug 21 '16 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 Aug 21 '16 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\$
  • \$\begingroup\$ @LeakyNun Waiting for one of your winning golf suggestions :D \$\endgroup\$ – Sherlock9 Aug 21 '16 at 19:34
  • \$\begingroup\$ @LeakyNun I'd be happy to post those approaches, too, unless you want to post them yourself. \$\endgroup\$ – Sherlock9 Aug 21 '16 at 19:37
  • \$\begingroup\$ +1 for the smirk ;) \$\endgroup\$ – Leaky Nun Aug 21 '16 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\$
  • \$\begingroup\$ I think that your test link is dead. \$\endgroup\$ – TheBikingViking Aug 22 '16 at 13:50
  • \$\begingroup\$ @TheBikingViking Thanks for pointing that out. I'll edit it after having my late lunch \$\endgroup\$ – Anastasiya-Romanova 秀 Aug 22 '16 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\$ – user5957401 Aug 22 '16 at 14:31
  • 1
    \$\begingroup\$ @user5957401 Edited.Bolshoe spasibo... \$\endgroup\$ – Anastasiya-Romanova 秀 Aug 22 '16 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 Aug 23 '16 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\$
  • 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 Aug 22 '16 at 21:48
  • \$\begingroup\$ @Delioth Interesting, thanks! I always just used the -e option, but I'll use that from now on. \$\endgroup\$ – Joe Aug 22 '16 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\$ – Joe Sep 4 '16 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\$
  • \$\begingroup\$ You're using $z where you should be using $x and I don't think you're incrementing $i in the loop \$\endgroup\$ – theLambGoat Aug 22 '16 at 15:43

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.