# Find the n-th perfect power!

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.

# 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

• Uptil what number should this work? Infinity? – ghosts_in_the_code May 1 '16 at 9:59
• A reasonable amount. – Leaky Nun May 1 '16 at 10:00
• What about a language that uses only a data type of one bit? – ghosts_in_the_code May 1 '16 at 10:09
• @Agawa001 Yes it is a standard loophole which are no longer funny. – flawr May 1 '16 at 10:12
• – Martin Ender May 1 '16 at 10:15

# Jelly, 11 bytes

µÆE;¬g/’µ#Ṫ


### Background

Every positive integer k can be factorized uniquely as the product of powers of the first m primes, i.e., k = p1α1⋯pmαm, where αm > 0.

We have that ab (b>1) for some positive integer a if and only if b is a divisor of all exponents α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 ->  and  -> .
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.

• I haven't seen STDIN at all. I have no idea how to use it at all. – Leaky Nun May 1 '16 at 16:15
• Nice use of the definition of perfect power having to do with prime factorization. Could you include this algorithm in the description? – Leaky Nun May 1 '16 at 16:16
• @KennyLau Done. – Dennis May 1 '16 at 16:41
• 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. – גלעד ברקן Mar 6 '18 at 12:09
• @גלעדברקן Sorry, that should have been a_m > 0. The previous m-1 exponents may include zeroes. – Dennis Mar 6 '18 at 12:33

# Mathematica, 34 bytes

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


Generates an n×n array Aij = i1+j, flattens it, and returns the nth element.

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


# Octave, 5731 30 bytes

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


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

# 05AB1E, 12 bytes

Code:

LD>m€{Ú¹<@


Uses CP-1252 encoding. Try it online!.

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

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

# Pyth - 12 11 bytes

Obvious approach, just goes through and checks all numbers.

e.ffsI@ZTr2


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

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

# 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>

## Actually, 18 bytes (non-competing)

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


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

This solution is non-competing because I fixed a bug with E after this challenge was posted.

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


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

# 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


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

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

• Would it be shorter to use recursion? – Leaky Nun May 24 '16 at 8:40
• Good, idea, needs a lot of planning though. – HopefullyHelpful May 24 '16 at 10:48