Take \$a \in ℤ_{>1}\$ and \$b \in ℤ_+\$ as inputs. Write a function \$f\$ such that:

$$ f(a,b) = \left\{ \begin{array}{ll} \log_ab & \quad \text{if} \space \log_ab \in ℚ \\ -1 & \quad \text{otherwise} \end{array} \right. $$


  • Types and formats of the inputs doesn't matter.

  • Type and format of the output doesn't matter either, but the fraction must be irreducible. In C++, std::pair<int,unsigned> is an example. (Regarding logarithms, the numerator and the denominator need not to be arbitrary-length integers.)

  • Regardless of whether the input type can handle arbitrary-length integers, the algorithm must be "as if" it were handling those. So using floating-point numbers is implicitly banned.

  • If \$a\$ and \$b\$ aren't in the sets as specified above, the challenge falls in don't care situation.

  • \$f\$ may be curried or uncurried.

  • As this is a code-golf, the shortest code in bytes wins.

Test cases

a   b   => answer
2   8   => 3/1
3   9   => 2/1
8   2   => 1/3
9   3   => 1/2
4   8   => 3/2
64  256 => 4/3
999 1   => 0/1
2   7   => -1
10  50  => -1
5   15  => -1
  • 5
    \$\begingroup\$ Could you add some example test cases? Preferably ones where \$log_ab \in \mathbb{Q} \setminus \mathbb{Z}\$ \$\endgroup\$
    – Value Ink
    Feb 13 '20 at 23:16
  • 3
    \$\begingroup\$ @PostRockGarfHunter One example is \$ \log_4 8 = 3/2 \$. \$\endgroup\$
    – Bubbler
    Feb 13 '20 at 23:19
  • \$\begingroup\$ they must be able to represent arbitrary-length integers This is a rather odd requirement, since it unfairly penalizes languages which don't have access to arbitrary-precision integer type (many of them don't even have a thing called "import"). Instead, we usually say "use the most natural number type for the language, but the underlying algorithm should generalize to higher numbers." \$\endgroup\$
    – Bubbler
    Feb 13 '20 at 23:35
  • \$\begingroup\$ @Bubbler I added that requirement to implicitly ban floating-point numbers, but to think about it, that's better. \$\endgroup\$ Feb 13 '20 at 23:38
  • 7
    \$\begingroup\$ It looks like you posted this from the Sandbox with edits that are only in the live version, which is unfortunate. Had you waited, I would have pointed out that you still don't have any test cases, which I had commented to remind you to add. And Bubbler might have raised their point about integer size in the Sandbox, which would give you more time to think how to address it, and I might have asked to clarify your new "as if" rule, which I think is unclear as it stands. See Things to avoid: Assuming you've addressed sandbox feedback. \$\endgroup\$
    – xnor
    Feb 13 '20 at 23:59

Mathematica, 47 45 43 29 bytes SBCS


You can try it online!

Thanks to @J42161217 for saving me a total of 16 bytes!!

  • \$\begingroup\$ @J42161217 weird it works in the pattern guard but not inside the if \$\endgroup\$
    – RGS
    Feb 14 '20 at 0:24
  • \$\begingroup\$ 29 bytes. This one works! Although OP doesn't like solutions like this at all (read main comments above). But after all, this is code-golf \$\endgroup\$
    – ZaMoC
    Feb 14 '20 at 1:19
  • \$\begingroup\$ @J42161217 wow incredible!!! \$\endgroup\$
    – RGS
    Feb 14 '20 at 6:49
  • \$\begingroup\$ Fed floating point numbers ( Print[f[1.2,1.44]] ) it outputs the right value.... almost ( 2.0000000000000004 ). Is "Log" a floating point function? \$\endgroup\$
    – David G.
    Feb 14 '20 at 22:47
  • \$\begingroup\$ OK. I will admit to being impressed by Mathematica's Log operator(?). It makes me wonder if I can't write something faster... \$\endgroup\$
    – David G.
    Feb 15 '20 at 1:34

Python 3, 103 101 97 bytes

Saved 2 bytes thanks to Kevin Cruijssen!!!
Saved 4 bytes thanks to Value Ink!!!

from math import*
def f(a,b):
 return -1if a**n-b**m else l

Try it online!

  • \$\begingroup\$ Times out on 8,4 (expected result 2/3) among other things. Nice idea for the fractional exponent check, though. \$\endgroup\$
    – Value Ink
    Feb 14 '20 at 1:23
  • \$\begingroup\$ @ValueInk What a shame - guess using as_integer_ratio like this isn't quite up to Mathematica standards! T_T \$\endgroup\$
    – Noodle9
    Feb 14 '20 at 10:43
  • \$\begingroup\$ Yeah, it's the floating point precision error causing problems, which Mathematica probably knows how to get around... I didn't get it submitted before the question closed but I tried something similar with Ruby's to_r which is equivalent -- while that function does return without timing out, because of the precision problems it was giving the wrong number. BTW, use log(b,a) next time. It won't help you with this question because of the aforementioned floating point problem, but could be useful for another problem later! \$\endgroup\$
    – Value Ink
    Feb 14 '20 at 11:03
  • \$\begingroup\$ @ValueInk A golfs a golf, nice one - thanks! :-) Maybe I can sort out the floating point issue. \$\endgroup\$
    – Noodle9
    Feb 14 '20 at 11:13
  • \$\begingroup\$ My solution (which I will post if this gets reopened) was basically to walk through the rationals manually by using the idea that \$x > 1 \implies x^{1/x} \notin \mathbb{Z}\$ to limit the denominator of the fraction to numbers up to \$a\$. Wolframalpha of \$x^{1/x}\$ \$\endgroup\$
    – Value Ink
    Feb 14 '20 at 11:24

05AB1E, 18 17 bytes

-1 byte thanks to Kevin Cruijssen


Try it online!

Ó                   # prime factorize each input
 0ζ                 # zip the factorizations together with filler 0
                    # for each pair of exponents:
    D€¿             #  get the gcd
       ÷            #  divide both by the gcd (reducing the fraction)
        ʒ  }        # filter the pairs, keep only those where:
         O          #  the sum
          Ā         #  is not 0
            DËi     # if all the resulting pairs are equal:
               н    #  output the first pair
                ë   # otherwise:
                 ®  #  output -1
  • 1
    \$\begingroup\$ -1 by using D€¿÷ instead of εD¿÷} \$\endgroup\$ Feb 14 '20 at 14:16

Charcoal, 88 82 bytes


Try it online! Link is to verbose version of code. Takes input as a list in [value, base] order and outputs numerator and denominator. Edit: Saved 6 bytes by simplifying my check for exclusive factors. Explanation:


Factorise both numbers by trial division.


Collect the factors from both inputs, in case some factors are only present in one of them.


Divide the multiplicity of each factor in both the base and the value by their GCD.


If this is not unique then output -1.


If it is unique then output it.


Python 3, 94 79 76 bytes

Nothing clever here; this is the obvious brute force approach.

Edit: Unified return point and switched to lambda syntax.

Edit 2: Shaved off three bytes due to @xnor's next trick and rules clarification.

lambda a,b:next(((i,j)for i in range(b)for j in range(1,a)if a**i==b**j),-1)

Try it online!

  • 1
    \$\begingroup\$ This is a great place to use the next syntax for generators: Try it online!. By the way, by default, you don't have to write f= for non-recursive functions. \$\endgroup\$
    – xnor
    Feb 15 '20 at 5:18
  • \$\begingroup\$ @xnor Didn't know about that second next parameter. Nice one! \$\endgroup\$
    – Yonatan N
    Feb 15 '20 at 22:41

bc, 110 bytes

define f(a,b){
if(e>1)d=d+1 else c=c+1}
print c,"/",d}

Try it online!

As with a number of my solutions, it outputs its answer and returns 0, which the test code ignores.

The use of scale= in the provided input is only so the expected value can be passed in. (You can't have a string value in bc.) The code is strictly integer... provided you pass in integers. The code may fail if a or the needed root of a is less than two. (See two failing samples in TIO.)


JavaScript (Node.js),  72  68 bytes

Takes input as (a)(b), where \$a\$ and \$b\$ are BigInts. Returns either [numerator, denominator] or \$-1\$.


Try it online!


We start with \$p=0\$ and \$q=1\$. We iteratively increment \$q\$ if \$a^p>b^q\$ or increment \$p\$ if \$a^p<b^q\$, until \$a^p=b^q\$ (success) or \$p>b\$ (no solution).


Sledgehammer, 11 bytes

Alternatively, 83 bits.

I ended up forgetting to actually answer this with Sledgehammer for a while...


Compressed from this Wolfram Language code:

If[NumberQ[x1 = Log[Input[], Input[]]], x1, -1]

, where NumberQ is a built-in that checks whether Log has returned an actual number and not a symbolic expression, i.e. when it is rational.


Ruby, 72 bytes

->a,b{n,d=[*1..a*b].product([*1..a]).find{|n,d|a**n==b**d};n ?n/1r/d:-1}

Try it online!


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.