16
\$\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\$
  • 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
  • 1
    \$\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

15 Answers 15

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 = 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 -> [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\$
  • \$\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
6
\$\begingroup\$

Mathematica, 34 bytes

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

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

\$\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\$
3
\$\begingroup\$

05AB1E, 12 bytes

Code:

LD>m€`{Ú`¹<@

Uses CP-1252 encoding. Try it online!.

\$\endgroup\$
3
\$\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\$
  • \$\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\$

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

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
\$\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\$
0
\$\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\$
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\$
  • \$\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

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.