12
\$\begingroup\$

Objective

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

Rules

  • 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
\$\endgroup\$
  • 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 at 23:16
  • 3
    \$\begingroup\$ @PostRockGarfHunter One example is \$ \log_4 8 = 3/2 \$. \$\endgroup\$ – Bubbler Feb 13 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 at 23:35
  • \$\begingroup\$ @Bubbler I added that requirement to implicitly ban floating-point numbers, but to think about it, that's better. \$\endgroup\$ – Dannyu NDos Feb 13 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 at 23:59
1
\$\begingroup\$

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.

\$\endgroup\$
8
\$\begingroup\$

Mathematica, 47 45 43 29 bytes SBCS

If[NumberQ[c=#~Log~#2],c,-1]&

You can try it online!

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

\$\endgroup\$
  • \$\begingroup\$ @J42161217 weird it works in the pattern guard but not inside the if \$\endgroup\$ – RGS Feb 14 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\$ – J42161217 Feb 14 at 1:19
  • \$\begingroup\$ @J42161217 wow incredible!!! \$\endgroup\$ – RGS Feb 14 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 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 at 1:34
5
\$\begingroup\$

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):
 l=log(b,a)
 n,m=l.as_integer_ratio()
 return -1if a**n-b**m else l

Try it online!

\$\endgroup\$
  • \$\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 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 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 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 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 at 11:24
5
\$\begingroup\$

05AB1E, 18 17 bytes

-1 byte thanks to Kevin Cruijssen

Ó0ζD€¿÷ʒOĀ}DËiнë®

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
\$\endgroup\$
  • 1
    \$\begingroup\$ -1 by using D€¿÷ instead of εD¿÷} \$\endgroup\$ – Kevin Cruijssen Feb 14 at 14:16
5
\$\begingroup\$

Charcoal, 88 82 bytes

≔Eθ⟦⟧ζ≔²ηW⊖⌈θ¿⌊﹪θη≦⊕ηUMθ⎇﹪κηκ∧⊞O§ζλη÷κηFζFι⊞υκUMυEζ№λιUMυ÷ι⊟Φ⊕⌈ι∧λ¬⌈﹪ιλ¿›⌈υ⌊υ-1I⊟υ

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:

≔Eθ⟦⟧ζ≔²ηW⊖⌈θ¿⌊﹪θη≦⊕ηUMθ⎇﹪κηκ∧⊞O§ζλη÷κη

Factorise both numbers by trial division.

FζFι⊞υκ

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

UMυEζ№λιUMυ÷ι⊟Φ⊕⌈ι∧λ¬⌈﹪ιλ

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

¿›⌈υ⌊υ-1

If this is not unique then output -1.

I⊟υ

If it is unique then output it.

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
  • 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 at 5:18
  • \$\begingroup\$ @xnor Didn't know about that second next parameter. Nice one! \$\endgroup\$ – Yonatan N Feb 15 at 22:41
2
\$\begingroup\$

bc, 110 bytes

define f(a,b){
c=0
d=1
while(0!=e=a^c-b^d){if(a<2^d){print"-1";return}
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.)

\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js),  72  68 bytes

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

a=>g=(b,p=0n,q=1n)=>p>b?-1:(d=a**p-b**q)?g(b,d>0?++q&&p:-~p,q):[p,q]

Try it online!

How?

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

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

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!

\$\endgroup\$

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.