Perfect powers in more than one way?

Question

Challenge

Your task is to write a program or function which, given a positive integer \$N\$, finds all positive integers less than or equal to \$N\$ that can be expressed as a perfect power in more than one way.

Definition

A perfect power is defined as a number \$i\$ found by \$m^k\$, where:

• \$m\$ and \$i\$ are positive integers
• \$m \ne k\$

Test Cases

input -> output
1000 ->  16, 64, 81, 256, 512, 625, 729
56 -> 16
999 -> 16, 64, 81, 256, 512, 625, 729
81 -> 16, 64, 81
1500 -> 16, 64, 81, 256, 512, 625, 729, 1024, 1296

Please provided a readable, commented version as well.

Answer 1

Mathematica: 103 chars

Spaces can be removed

Select[Flatten@
       Table[
        Solve[Log@#/Log@b == k, k, Integers] /. k -> #, {b, 2, #}] & /@ Range@#, 
Length@# > 2 &][[All, 1, 1]] &  

Usage:

%[81]
{16, 64, 81}

Answer 2

Jelly, 11 meaningful bytes, language postdates challenge

ḊḟÆR *@þ Ḋ  F  fḊ

Try it online!

Here's an entirely different solution. This one's a curious hybrid of efficient and inefficient, using an efficient core algorithm in a very inefficient wrapper (so much so that it can't handle very large numbers). As before, all whitespace is meaningless.

Here's how it works. Ḋ (which appears several times) is a list of numbers from 2 to the input inclusive:

ḊḟÆR *@þ Ḋ  F  fḊ
ḊḟÆR                Ḋ, with all primes between 2 and the input removed
                    (i.e. all composite numbers from 4 to the input)
     *@þ Ḋ          Exponentiate all Ḋ elements with all ḊḟÆR elements
            F       Flatten the result (it had a nested structure)
               fḊ   Keep only elements in Ḋ

The basic observation here is that a number is a perfect power in multiple ways, only if it's a perfect power with a composite exponent (that isn't 1). We generate a list of those where the base is from 2 to the input, and the exponent is a composite number from 4 to the input; this is really slow because it generates some really big numbers, all of which are an answer to the question. Then we only keep the answers which are in range.

It'd easily be possible to modify this into a highly efficient answer, by working out what the maximum power in range was and not iterating any further, but that'd be a lot more bytes, and this is code-golf.

Answer 3

Perl: 68 chars

Gets the maximum (1000) in $N and returns the answer in @a.

for $x ( 2..$N ) {
    $c{$x**$_}++ for 2..log($N)/log$x
}
@a = grep { $c{$_} > 1 } keys %c

For a whole program, I need another 18 chars:

$m = shift;
for $x ( 2..$m ) {
    $c{$x**$_}++ for 2..log($m)/log$x
}
print join ' ', grep { $c{$_} > 1 } keys %c

Answer 4

Ruby - 101 chars (without whitespace)

f=->l{c=Hash.new{0}
2.upto(1E4){|i|2.upto(20){|j|c[i**j]+=1}}
c.map{|k,v|v>1&&k<=l&&k||p}.compact.sort}

Works for 1 <= limit <= 100,000,000 within 5 seconds.

Test

> f[10000]
[16, 64, 81, 256, 512, 625, 729, 1024, 1296, 2401, 4096, 6561, 10000]

Answer 5

Jelly, 13 meaningful characters, language postdates challenge

R  µ  ọḊ *@Ḋ ċ >2  µ  Ðf

Try it online!

All whitespace here is insignificant. I used it to show the structure of my answer, as the question asks.

Here's how it works:

R  µ  ọḊ *@Ḋ ċ >2  µ  Ðf
R                     Ðf    Find all numbers n from 1 to the input, such that:
   µ               µ          (grouping marks, like {} in C)
       Ḋ   Ḋ                  Take the range from 2 to n
      ọ                       Find the number of times each divides n
         *@                   Raise the range from 2 to n to these powers
             ċ                Count the number of times n appears
               >2             and the result must be greater than 2

So for example, when testing n=256, we check the number of times each of the numbers from 2 to 256 divides into 256. The only numbers that divide more than once are 2 (which divides 8 times), 4 (which divides 4 times), 8 (which divides twice), and 16 (which divides twice). So when we raise the number of divisions to the powers determined there, we get:

2⁸, 3, 4⁴, 5, 6, 7, 8², 9, 10, 11, 12, 13, 14, 15, 16², 17, ..., 255, 256

This produces the original value, 256, a number of times equal to the way that 256 is a perfect power, plus one (the last element produces 256 because 256 = 256¹). So if we see 256 more than twice in the array (and we do in this case; 8² is 64 but the other "interesting" elements all produce 256), it must be a perfect power.