9
\$\begingroup\$

Some numbers can be represented as perfect powers of other numbers. A number x can be represented as x = base^power for some integer base and power.

Given an integer x you have to find the largest value of power, such that base is also an integer.

Sample Input:
9
Sample Output:
2
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Do we have to handle 0 as an input case? What about negative integers? \$\endgroup\$ Aug 23, 2011 at 16:10
  • 4
    \$\begingroup\$ What output do you expect for input 1? \$\endgroup\$ Feb 26, 2016 at 18:46

15 Answers 15

3
\$\begingroup\$

Golfscript - 26 chars

~:x,{:b;x,{b?x=b*}%+}*$-1>

Rough translation to Python

x=input()
acc = []
for b in range(x):
    for _ in range(x):
        acc.append((_**b==x)*b) # most of these are zeros
print max(acc)

So it loops way more times that necessary, but that often happens with golfed answers

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Does this work for 11 as input? the python version looks like it doesn't. \$\endgroup\$
    – Clueless
    Aug 21, 2011 at 23:15
3
+200
\$\begingroup\$

APL (Dyalog Extended), 13 bytes

⌈/⍳×∘(⊢=⌊)⍳√⊢

Try it online!

⌈/⍳×∘(⊢=⌊)⍳√⊢     Monadic train taking an input n:
         ⍳√⊢     Get the 1st, ..., nth roots of n.
    (⊢=⌊)        Find whether each element equals its floor; i.e. is an integer.
                Returns a list of 0s and 1s.
  ⍳              List of 1, ..., n
   ×            Multiply that with the binary list.
                Now we have a list starting with 1 (since the 1st root of n is n, an integer)
                and larger nonzero values corresponding to the other roots that are integers.
⌈/              Find the maximum.
\$\endgroup\$
3
\$\begingroup\$

Uiua, 11 10 bytes

Edit: -1 byte thanks to ovs

⊢⇌⍖◿1ⁿ÷⇡,1

Try it!

A different approach to Bubbler's Uiua answer, for the same number of bytes.

       ÷⇡,1   # reciprocals of 0..input
      ⁿ       # input to the power of those (so: roots)
    ◿1        # modulo 1 (so whole numbers become zero)         
   ⍖          # fall: indices if it was sorted descending 
              # (index of largest root that is a whole number is now last)
⊢⇌            # get the last item
\$\endgroup\$
2
  • 1
    \$\begingroup\$ pretty sure this can be ⊢⇌⍖◿1ⁿ÷⇡,1 to match Bubbler's 10 \$\endgroup\$
    – ovs
    Oct 16, 2023 at 14:13
  • \$\begingroup\$ @ovs - really nice, thanks a lot! \$\endgroup\$ Oct 16, 2023 at 14:45
2
\$\begingroup\$

Haskell, 63 56 characters

Handles ℤ>0 (56 characters)

main=do n<-readLn;print$last[p|p<-[0..n],b<-[0..n],b^p==n]

Handles ℤ≥0 (58 characters)

main=do n<-readLn;print$last[p|p<-[0..n+1],b<-[0..n],b^p==n]

Handles ℤ (70 characters)

main=do n<-readLn;print$last[p|p<-[0..abs n+1],b<-[n..0]++[0..n],b^p==n]
\$\endgroup\$
2
\$\begingroup\$

Japt -h, 9 bytes

õ f@qX v1

Try it

õ f@qX v1     :Implicit input of integer U
õ             :Range [0,U]
  f@          :Filter as X
    qX        :  Xth root of U
       v1     :  Divisible by 1?
              :Implicit output of last element
\$\endgroup\$
2
\$\begingroup\$

Stax, 4 bytes

|n|g

Run and debug it

|n gets the prime factor exponents of the input. |g calculates the GCD of the result.

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

05AB1E (legacy), 9 8 4 bytes

Ó0K¿

-1 byte thanks to @Don't be a x​‑triple dot.
Only works in the Python legacy version of 05AB1E, because should be DïQ in the Elxiir rewrite due to a bug; and it's also way slower due to zm.
-4 bytes porting @recursive's Stax answer.

Try it online or verify all integers in the range [2,100].

Previous 9 8 bytes solution:

Lʒzm.ï}à

Try it online or verify all integers in the range [2,100].

Explanation:

Ó      # Get the exponents of the (implicit) input's prime factorization
 0K    # Remove all 0s
   ¿   # Pop and push the Greatest Common Divisor (GCD) of this list
       # (which is output implicitly as result)

\$b^{^\frac{1}a}\$ is another way to write \$\sqrt[^a]{b}\$

L      # Create a list in the range [1, (implicit) input]
 ʒ     # Filter this list of integers by:
  z    #  Pop the value and push 1/value instead
   m   #  Then take it to the power of the (implicit) input
    .ï #  And check if it's an integer without decimal values after the period
 }à    # After the filter: pop the list and push the maximum
       # (which is output implicitly as result)
\$\endgroup\$
6
  • \$\begingroup\$ @Shaggy Now it should be fixed.. <.> I'm so glad challenges like this would be closed as unclear these days without some more rules and test cases.. Some suggested test cases would be 18 (1), 36 (2), 81 (4), and 1024 (10) imo.. Anyway, thanks for letting me know. Unfortunately there isn't an x-root builtin in 05AB1E, nor is the is_int builtin working for integers with with .0 decimals.. >.> \$\endgroup\$ Feb 7, 2019 at 18:56
  • \$\begingroup\$ Agreed. There are so many old challenges I skip over because their spec is ambiguous or downright unclear, which is a shame, given how few new challenges are being posted these days. When I saw your original solution it took me far too long to figure out if you were wrong or I was (and I'm still not sure!). Maybe it's time for a clearout? Go through our old challenges, close the ones that don't meet our current standards and recreate them with better specs. \$\endgroup\$
    – Shaggy
    Feb 7, 2019 at 19:01
  • \$\begingroup\$ @Shaggy No, you were right. I misunderstood the challenge. And perhaps we should indeed repost old challenges with updates spec, and close the old ones as duplicates. Happened a few times before; I've seen MartinEnder do it a few times (here his most recent challenge as example). Maybe we should create a meta post to ask other people's opinions? It would also mean we have more 'new' challenges to do, since lately less and less challenges are posted. \$\endgroup\$ Feb 7, 2019 at 19:23
  • \$\begingroup\$ Yeah, let's take it to meta, see what everyone else thinks. I know we've had a couple of meta posts about individual challenges but I think this needs a larger effort to help inject some new life here. \$\endgroup\$
    – Shaggy
    Feb 7, 2019 at 22:20
  • \$\begingroup\$ Although, as I say that, I have vague recollections of an existing meta post on this but, assuming I'm not just misremembering, I think that one might have been proposing just arbitrarily closing old challenges without a set criteria for why challenges should be closed, simply in an effort to "reboot" them. \$\endgroup\$
    – Shaggy
    Feb 7, 2019 at 22:22
2
\$\begingroup\$

Uiua, 10 bytes

⊢⍖=⊞ⁿ.⇡+1.

Try it online!

-1 thanks to Dominic van Essen.

⊢⍖=⊞ⁿ.⇡+1.   input: positive integer n >= 2
        ⇡+1    range from 0 to n inclusive
    ⊞ⁿ.       cartesian product with itself by power
               (the k-th row contains x^k for x = 0..n)
   =       .   for each element, 1 if it equals n, 0 otherwise
               (higher power gives 1 at an earlier position,
                so the highest power is the lexicographically highest row)
⊢⍖            index of the maximum row lexicographically

Uiua, 11 bytes

⊢⍏⊗∶⊞ⁿ.⇡+1.

Try it online!

⊢⍏⊗∶⊞ⁿ.⇡+1.    input: positive integer n >= 2
         ⇡+1    range from 0 to n inclusive
     ⊞ⁿ.       cartesian product with itself by power
                (the k-th row contains x^k for x = 0..n)
   ⊗∶       .   the index of n in each row of the matrix, n+1 if not present
                (higher power gives lower index)
⊢⍏             index of the minimum element
\$\endgroup\$
1
  • \$\begingroup\$ 10 bytes, annoyingly outgolfing my own answer... \$\endgroup\$ Oct 13, 2023 at 14:26
1
\$\begingroup\$

Buggy Golfscript - 59

~0\1{1{1$1$?3$={p;\)\.(.}{}if).3$=!}do;).2$=!}do;;{}{1p}if

This is my first attempt with golfscript, so it probably can be improved in length.

Now the buggy part comes from the fact that this runs perfectly on the interpreter written in perl, but in the original ruby version, I'm having a really weird bug. I spent a couple of hours trying to wrap my head around it but I can't figure it out. I decided to post anyway to maybe get some feedback.

\$\endgroup\$
5
  • \$\begingroup\$ If might help you debug if you change the inner loop to this {1$.p 1$.p?3$.p={p;\)\.(.}{}if).3$=!} you can see that this is going haywire on the second iteration of the outer loop \$\endgroup\$
    – gnibbler
    Feb 6, 2011 at 1:56
  • \$\begingroup\$ The ruby interpreter is broken, see this: stackoverflow.com/questions/3927328 \$\endgroup\$
    – Nabb
    Feb 6, 2011 at 4:51
  • 1
    \$\begingroup\$ A few tips -- {...}{}if can be replaced by !!{...}* or {...}* (if the value is 0/1). {}{...}if becomes !{...}*. Since the stack is outputted at the end of the program, it is usually shorter to avoid explicit outputs. {}/, {}% and {}* constructs are shorter than do loops and manually maintaining a counter. \$\endgroup\$
    – Nabb
    Feb 6, 2011 at 5:00
  • \$\begingroup\$ @Nabb well that sucks :( Thanks for the tips and the heads up! @gnibbler what I found is that the last value on the stack as the outer loop finishes its first iteration, is incremented by one when the second iteration starts which is really weird. \$\endgroup\$
    – Champo
    Feb 6, 2011 at 7:07
  • \$\begingroup\$ Argh, that sucks. I think we are probably stuck with the same interpreter forever \$\endgroup\$
    – gnibbler
    Feb 7, 2011 at 10:20
1
\$\begingroup\$

Python, 72 chars

x=range(1,input()+1)
print max(p*sum(b**p==len(x)for b in x)for p in x)
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 23 bitsv2, 2.875 bytes

∆ǐġ

Try it Online!

Bitstring:

00010101110010111001101

Ports Recursive's answer in Stax

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

Mathematica : 61 chars

. First try:

Max[k/.Table[Solve[Log@#/Log@b==k,k,Integers],{b,2,#}]][[1]]&
\$\endgroup\$
0
\$\begingroup\$

CSharp - 130 chars

void Main(){var i = Int32.Parse(Console.ReadLine());Console.WriteLine(Enumerable.Range(2,i-2).Last(k => Math.Pow(i,1.0/k)%1==0));}
\$\endgroup\$
0
\$\begingroup\$

APL(NARS), 34 chars, 68 bytes

{⍵≤1:∞⋄⌈/i/⍨{0=1∣⍵√w}¨i←⍳n←⌊2⍟w←⍵}

The idea is that the max possible exponent is n←⌊2⍟argument, so i build one range on that: 1..n and to get the max possible exponent; test:

  f←{⍵≤1:∞⋄⌈/i/⍨{0=1∣⍵√w}¨i←⍳n←⌊2⍟w←⍵}
  f 25
2
  f 30
1
  f 8
3
  f  323*(2×3)
6

They want max exponent, right?

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

Scala, 70 bytes

Golfed version. Try it online!

x=>(for{b<-0 to x-1;a<-0 to x-1;if Math.pow(a,b).toInt==x}yield b).max

Ungolfed version. Try it online!

object Main {
  def main(args: Array[String]): Unit = {
    def f(x: Int): Int = {
      val acc = for {
        b <- 0 until x
        a <- 0 until x
        if scala.math.pow(a, b).toInt == x
      } yield b 
      acc.max
    }

    println(f(9))
  }
}
\$\endgroup\$

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.