# Find all Super Powers [duplicate]

A positive number is said to be super power when it is the power of at least two different positive integers. Write a program that lists all super powers in the interval [1, 264) (i.e. between 1 (inclusive) and 264 (exclusive)).

Sample Output

1
16
64
81
256
512
.
.
.
18443366605910179921
18444492376972984336
18445618199572250625


Constraints:

1. The program should not take more than 10 secs.
2. There are 67385 super powers below 264.
3. The shortest code wins.
• The time part is a quite severe limitation on environment, many slow consoles will be out because they basically can't do 10k lines per second. Commented Apr 4, 2011 at 14:58
• @eBusiness Keeping in mind your point, should 20 secs be enough? Commented Apr 4, 2011 at 15:06
• I think it might just do it for my GolfScript, but I'd rather make it a minute. Commented Apr 4, 2011 at 15:50
• @eBusiness: What if you output to file instead? Commented Apr 4, 2011 at 16:42
• That helps, put me down to less than 3 seconds for the output. Now to see if I can do the actual task quick enough... Commented Apr 4, 2011 at 17:38

# GolfScript 52 characters

64,4>{1.{16.?<}{;).2$?}/@.,1>{2$\%*}**!*\;~}%$.&{p}/  I golfed this pretty heavily, here is a compilation of midway solutions: ;64,4>{.,2>{\.@%}%{*}*!\;},{1.{16.?<}{;).2$?}/]2=}%[]*$0\{.@={}{.p}if}/; ;64,4>{.,2>{\.@%}%{*}*!\;},{1.{16.?<}{;).2$?}/]2=}%[]*$.&{p}/ ;64,4>{.,2>{\.@%}%{*}*!\;},{1.{16.?<}{;).2$?}/]2=~}%$.&{p}/ ;4.{64<}{;)..,1>{2$\%*}*!*}/0-\;{1.{16.?<}{;).2$?}/]2=~}%$.&{p}/
;64,4>{.,1>{2$\%*}*!*},{1.{16.?<}{;).2$?}/]2=~}%$.&{p}/ ;64,4>{.,1>{2$\%*}*{1.{16.?<}{;).2$?}/~}or]2>~}%$.&{p}/
64,4>{.,1>{2$\%*}*!\1.{16.?<}{;).2$?}/\;\;*~}%$.&{p}/ 64,4>{1.{16.?<}{;).2$?}/\;\.,1>{2$\%*}*!\;*~}%$.&{p}/
64,4>{1.{16.?<}{;).2$?}/@.,1>{2$\%*}**!*\;~}%$.&{p}/  GolfScript seems to have some problem with outputting large arrays, therefore I step through the result array using {p}/ rather than just inject the needed lineshifts using n*. The first 5 versions work by first generating an array of nonprimes from 4 to 63 (code before {1.), then for each element of that list all N^nonprime less than 2^64 is calculated (1.{16.?<}{;).2$?}/). Finally the result is sorted, duplicates are removed and the result is output.

In the 6th version the 2 first functions are put in the same loop.

In the 7th version the N^nonprime array is generated no matter if the nonprime is actually a nonprime, the array is then thrown away if needed.

In the 8th and 9th version the order has been switched so the N^nonprime array is generated before nonprime status is asserted.

By the way, a^b where a>0, b>1 and b is nonprime is probably a more programming-friendly way of describing super powers.

## Ruby, 97 93 characters

puts (r=2..32).map{|j|r.map{|i|(1..2**(64.0/j/i)).map{|a|a**(j*i)}}}.flatten.uniq.sort[0..-2]


I'm pretty sure this should be correct.

$time ruby1.9 perfectpower.rb > out real 0m0.199s user 0m0.160s sys 0m0.030s$ wc -l out
67385 out

$head -6 out 1 16 64 81 256 512$ tail -3 out
18443366605910179921
18444492376972984336
18445618199572250625


## Python, 107 chars

R=range
for x in sorted(set(i**(j*k)for i in R(65536)for j in R(2,32)for k in R(2,64/j)))[1:67386]:print x


Takes about 40 seconds on my machine, though.

• Well, you do make a set of several million numbers, up to 1024 bit in length. May I suggest that you move for i in R to the other end of the for stack and give it a sensible limit like ceil(2^(64/j/k)+2)? Commented Apr 5, 2011 at 10:52