18
\$\begingroup\$

A perfect power is a number of the form \$a^b\$, where \$a>0\$ and \$b>1\$.

For example, \$125\$ is a perfect power because it can be expressed as \$5^3\$.

Goal

Your task is to write a program/function that finds the \$n\$-th perfect power, given a positive integer \$n\$.

Specs

  • The first perfect power is \$1\$ (which is \$1^2\$).
  • Input/output in any reasonable format.
  • Built-ins are allowed.

Further information

Scoring

This is . Shortest solution in bytes wins.

Testcases

input  output
1      1
2      4
3      8
4      9
5      16
6      25
7      27
8      32
9      36
10     49
\$\endgroup\$
7
  • 1
    \$\begingroup\$ Uptil what number should this work? Infinity? \$\endgroup\$ – ghosts_in_the_code May 1 '16 at 9:59
  • \$\begingroup\$ A reasonable amount. \$\endgroup\$ – Leaky Nun May 1 '16 at 10:00
  • \$\begingroup\$ What about a language that uses only a data type of one bit? \$\endgroup\$ – ghosts_in_the_code May 1 '16 at 10:09
  • 2
    \$\begingroup\$ @Agawa001 Yes it is a standard loophole which are no longer funny. \$\endgroup\$ – flawr May 1 '16 at 10:12
  • 6
    \$\begingroup\$ Related. Related. Related. \$\endgroup\$ – Martin Ender May 1 '16 at 10:15

20 Answers 20

8
\$\begingroup\$

Jelly, 11 bytes

µÆE;¬g/’µ#Ṫ

Try it online!.

Background

Every positive integer \$k\$ can be factorized uniquely as the product of powers of the first \$m\$ primes, i.e., \$k=p_1^{\alpha_1}\cdots p_m^{\alpha_m}\$, where \$\alpha_m>0\$.

We have that \$a^b\$ (\$b>1\$) for some positive integer \$a\$ if and only if \$b\$ is a divisor of all exponents \$\alpha_j\$.

Thus, an integer \$k > 1\$ is a perfect power if and only if \$\gcd(α_1, ⋯, α_m) ≠ 1\$.

How it works

µÆE;¬g/’µ#Ṫ  Main link. No arguments.

µ            Make the chain monadic, setting the left argument to 0.
        µ#   Find the first n integers k, greater or equal to 0, for which the
             preceding chain returns a truthy value.
             In the absence of CLAs, n is read implicitly from STDIN.
 ÆE          Compute the exponents of the prime factorization of k.
   ;¬        Append the logical NOT of k, i.e., 0 if k > 0 and 1 otherwise.
             This maps 1 -> [0] and [0] -> [1].
     g/      Reduce the list of exponents by GCD.
             In particular, we achieved that 1 -> 0 and 0 -> 1.
       ’     Decrement; subtract 1 from the GCD.
             This maps 1 to 0 (falsy) and all other integers to a truthy value.
          Ṫ  Tail; extract the last k.
\$\endgroup\$
6
  • \$\begingroup\$ I haven't seen STDIN at all. I have no idea how to use it at all. \$\endgroup\$ – Leaky Nun May 1 '16 at 16:15
  • \$\begingroup\$ Nice use of the definition of perfect power having to do with prime factorization. Could you include this algorithm in the description? \$\endgroup\$ – Leaky Nun May 1 '16 at 16:16
  • \$\begingroup\$ @KennyLau Done. \$\endgroup\$ – Dennis May 1 '16 at 16:41
  • \$\begingroup\$ I don't understand how 21^2 includes the first or third prime in its factorization. Could you please help me understand what you mean by "Every positive integer k can be factorized uniquely as the product of powers of the first m primes...where [the exponent] a_n > 0?" It seems to me in the factorization for 21^2 the exponents for p = 2 and p = 5 are zero. \$\endgroup\$ – גלעד ברקן Mar 6 '18 at 12:09
  • \$\begingroup\$ @גלעדברקן Sorry, that should have been a_m > 0. The previous m-1 exponents may include zeroes. \$\endgroup\$ – Dennis Mar 6 '18 at 12:33
7
\$\begingroup\$

Mathematica, 34 bytes

(Union@@Array[#^#2#&,{#,#}])[[#]]&

Generates an \$n\times n\$ array \$A_{ij} = i^{1+j}\$, flattens it, and returns the \$n\$th element.

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

05AB1E, 12 bytes

Code:

LD>m€`{Ú`¹<@

Uses CP-1252 encoding. Try it online!.

\$\endgroup\$
3
\$\begingroup\$

CJam, 16 bytes

ri_),_2f+ff#:|$=

Test it here.

Explanation

This uses a similar idea to LegionMammal's Mathematica answer.

ri    e# Read input and convert to integer N.
_),   e# Duplicate, increment and turn into range [0 1 ... N].
_2f+  e# Duplicate and add two to each element to get [2 3 ... N+2].
ff#   e# Compute the outer product between both lists over exponentiation.
      e# This gives a bunch of perfect powers a^b for a ≥ 0, b > 1.
:|    e# Fold set union over the list, getting all unique powers generated this way.
$     e# Sort them.
=     e# Retrieve the N+1'th power (because input is 1-based, but CJam's array access
      e# is 0-based, which is why we included 0 in the list of perfect powers.
\$\endgroup\$
3
\$\begingroup\$

Octave, 57 31 30 bytes

@(n)unique((1:n)'.^(2:n+1))(n)

I just noticed again that Octave does not need ndgrid (while Matlab does)=)

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

Jelly, 9 bytes

*þḊFQṢị@o

Try it online!

As far as I can tell, only the þ quick didn't exist when the challenge was posted, but this 10 byter would've worked back then as well as now.

How it works

*þḊFQṢị@o - Main link. Takes n on the left
  Ḋ       - Yield [2, 3, ..., n]
 þ        - Create an n×(n-1) matrix then
            for each entry (i,j) (i = 1,2,...,n and j = 2,3,...n),
            fill it with the following:
*         -   i*j
   F      - Flatten the matrix
    Q     - Remove duplicates
     Ṣ    - Sort
            For all n > 1, this yields an ordered list of perfect powers below n*n
            For n = 1, this yields an empty list
      ị@  - Take the nth item in this list. n = 1 yields 0
        o - Replace 0 with n, to handle n = 1
\$\endgroup\$
2
\$\begingroup\$

Sage (version 6.4, probably also others): 64 63

lambda n:[k for k in range(1+n^2)if(0+k).is_perfect_power()][n]

Creates a lambda function that returns nth perfect power. We rely on the fact that it is found within the first n^2 integers. (The 1+n^2 is necessary for n=1,2. The 0+k bit is necessary to convert int(k) to Integer(k).)

Byte off for xrange->range, thanks Dennis.

Just a fun fact: 0 is a perfect power by Sage's standards, fortunately, because then 1 is the 1st element of the list, not 0th :)

\$\endgroup\$
2
  • \$\begingroup\$ So this is Python except for the prime power part? \$\endgroup\$ – CalculatorFeline May 1 '16 at 21:48
  • \$\begingroup\$ @CatsAreFluffy And is_perfect_power() \$\endgroup\$ – yo' May 1 '16 at 22:52
2
\$\begingroup\$

Pyth - 12 11 bytes

Obvious approach, just goes through and checks all numbers.

e.ffsI@ZTr2

Test Suite.

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

J, 29 bytes

Based on the @LegionMammal978's method.

<:{[:/:~@~.[:,/[:(^/>:)~>:@i.

Usage

   f =: <:{[:/:~@~.[:,/[:(^/>:)~>:@i.
   f " 0 (1 2 3 4 5 6 7 8 9 10)
1 4 8 9 16 25 27 32 36 49

Explanation

<:{[:/:~@~.[:,/[:(^/>:)~>:@i.
                           i.  Create range from 0 to n-1
                        >:     Increments each in that range, now is 1 to n
               [:              Cap, Ignores input n
                    >:         New range, increment from previous range to be 2 to n+1 now
                  ^/           Forms table using exponentation between 1..n and 2..n+1
             ,/                Flattens table to a list
         ~.                    Takes only distinct items
     /:~                       Sorts the list
<:                             Decrements the input n (since list is zero-based index)
  {                            Selects value from resulting list at index n-1
\$\endgroup\$
1
\$\begingroup\$

MATL, 9 bytes

:tQ!^uSG)

Try it online

This is a port of Flawr's Octave solution to MATL, make the matrix of powers up to n^(n+1), and get the n-th one.

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

Julia, 64 32 bytes

n->sort(∪([1:n]'.^[2:n+1]))[n]

This is an anonymous function that accepts an integer and returns an integer. To call it, assign it to a variable.

The idea here is the same as in LegionMammal's Mathematica answer: We take the outer product of the integers 1 to n with 2 to n + 1, collapse the resulting matrix column-wise, take unique elements, sort, and get the nth element.

Try it online! (includes all test cases)

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

JavaScript (ES6), 87

n=>(b=>{for(l=[i=0,1];b<n*n;++b)for(v=b;v<n*n;)l[v*=b]=v;l.some(x=>n==i++?v=x:0)})(2)|v

Less golfed

f=n=>{
  for(b=2, l=[0,1]; b < n*n; ++b)
    for(v = b; v < n*n;)
      l[v*=b] = v;
  i = 0;
  l.some(x => n == i++ ? v=x : 0);
  return v;
  // shorter alternative, but too much memory used even for small inputs
  // return l.filter(x=>x) [n-1];
}

Test

f=n=>(b=>{for(l=[i=0,1];b<n*n;++b)for(v=b;v<n*n;)l[v*=b]=v;l.some(x=>n==i++?v=x:0)})(2)|v

function test(){
  var v=+I.value
  O.textContent=f(v)
}
  
test()
<input type=number id=I value=10><button onclick='test()'>-></button>
<span id=O></span>

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

><>, 108 bytes

:1)?v  >n;
$:@@\&31+2>2$:@@:@
:1=?\@$:@*@@1-
:~$~<.1b+1v!?(}:{:~~v?(}:{:v?=}:{
1-:&1=?v~~>~61.     >~1+b1.>&

This program requires the input number to be present on the stack before running.

It took quite a lot to reduce the number of wasted bytes down to 7!

After a check to see if the input is 1, the program checks each number, n, from 4 in turn to see if it's a perfect power. It does this by starting with a=b=2. If a^b == n, we've found a perfect power, so decrement the number of perfect powers left to find - if we've already found the right number, output.

If a^b < n, b is incremented. If a^b > n, a is incremented. Then, if a == n, we've found that n isn't a perfect power, so increment n, resetting a and b.

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

Actually, 18 bytes

;;u@ⁿr;`;√≈²=`M@░E

Try it online! (may not work due to needing an update)

Explanation:

;;u@ⁿr;`;√≈²=`M@░E
;;u@ⁿr              push range(n**(n+1))
      ;`;√≈²=`M@░   filter: take if
        ;√≈²=         int(sqrt(x))**2 == x
                 E  get nth element
\$\endgroup\$
1
\$\begingroup\$

R, 44 bytes

n=scan();unique(sort(outer(1:n,2:n,`^`)))[n]

Try it online!

Same approach as the Mathematica answer.

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

Husk, 10 bytes

!¹OuṠ×^tḣ→

Try it online!

Explanation

!¹OuṠ×^tḣ→ Range 1..n+1 (ḣ called with 1 given an empty list)
    Ṡ      hookf: Ṡ f g x = f (g x) x
     ×^     f: apply power to all possible pairs from two lists
       t    g: tail (1..n → 2..n)
   u       all unique powers
  O        sort in ascending order
!¹         element at index n

Husk, 10 bytes

!¹uO§×^…2ḣ

Try it online!

Dominic Van Essen's solution.

Explanation

!¹uO§×^…2ḣ
    §      fork: § f g h x = f (g x) (h x)
     ×^     f: apply power to all possible pairs from two lists
       …2   g: inclusive range from 2..n (works for n<2)
         ḣ  h: range from 1..n
   O        sort in ascending order
  u         all unique powers
!¹         element at index n
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I got !¹uO§×^…2ḣ which is also 10 bytes. You'll get the upvote when you post your explanation... \$\endgroup\$ – Dominic van Essen Oct 9 '20 at 13:31
  • \$\begingroup\$ @DominicvanEssen haha.. nice. \$\endgroup\$ – Razetime Oct 9 '20 at 13:36
  • \$\begingroup\$ @DominicvanEssen added yours as well. \$\endgroup\$ – Razetime Oct 9 '20 at 14:04
0
\$\begingroup\$

JavaScript (ES7), 104 bytes

n=>(a=[...Array(n)]).map(_=>a.every(_=>(p=i**++j)>n*n?0:r[p]=p,i+=j=1),r=[i=1])&&r.sort((a,b)=>a-b)[n-1]

Works by computing all powers not greater than n², sorting the resulting list and taking the nth element.

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

Java, 126

r->{int n,i,k;if(r==1)return r;for(n=i=2,r--;;){for(k=i*i;k<=n;k*=i)if(k==n){i=--r>0?++n:n;if(r<1)return n;}if(--i<2)i=++n;}}
\$\endgroup\$
2
  • \$\begingroup\$ Would it be shorter to use recursion? \$\endgroup\$ – Leaky Nun May 24 '16 at 8:40
  • \$\begingroup\$ Good, idea, needs a lot of planning though. \$\endgroup\$ – HopefullyHelpful May 24 '16 at 10:48
0
\$\begingroup\$

Python 3, 82 bytes

f=lambda n,i=0:n and f(n-any(a**b==i for a in range(i)for b in range(i)),i+1)or~-i

Try it online!

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

05AB1E, 9 bytes

µNDÓ2šθ2@

Try it online or verify a few more test cases.

Explanation:

µ         # Loop until the counter_variable (0 by default) equals the (implicit) input:
 ND       #  Push the current 0-based loop-index `N` twice
   Ó      #  Pop one, and push all its exponents of prime factorization [a,b,c,d,...] in
          #  [2^a,3^b,5^c,7^d,...]
          #  (for N=0 and N=1, this will results in an empty list)
    2š    #  Prepend a 2 (for the edge cases N=0 and N=1)
      θ   #  Pop the list, and leave just the last value
       2@ #  Check if this is larger than or equal to 2
          #  (if it is: implicitly increase the counter_variable by 1)
          # (after the loop, implicitly output the last `N` that's still on the stack)

Minor note: the @ in my answer using the latest 05AB1E version is a builtin for >=, whereas the @ used in @Adnan's existing 05AB1E answer using the legacy 05AB1E version is a builtin to push the \$n^{th}\$ item on the stack.

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