Find the n-th perfect power!

Question

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

• OEIS A001597

Scoring

This is code-golf. 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

Answer 1

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.

Answer 2

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.

Answer 3

05AB1E, 12 bytes

Code:

LD>m€`{Ú`¹<@

Uses CP-1252 encoding. Try it online!.

Answer 4

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.

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

Pyth - 12 11 bytes

Obvious approach, just goes through and checks all numbers.

e.ffsI@ZTr2

Test Suite.

Answer 9

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

Answer 10

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.

Answer 11

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 n^th element.

Try it online! (includes all test cases)

Answer 12

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>

Answer 13

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

Answer 14

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

Answer 15

R, 44 bytes

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

Try it online!

Same approach as the Mathematica answer.

Answer 16

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

Answer 17

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.

Answer 18

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;}}

Answer 19

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!

Answer 20

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.