7
\$\begingroup\$

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.
\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Apr 4, 2011 at 14:58
  • \$\begingroup\$ @eBusiness Keeping in mind your point, should 20 secs be enough? \$\endgroup\$
    – fR0DDY
    Commented Apr 4, 2011 at 15:06
  • \$\begingroup\$ I think it might just do it for my GolfScript, but I'd rather make it a minute. \$\endgroup\$ Commented Apr 4, 2011 at 15:50
  • \$\begingroup\$ @eBusiness: What if you output to file instead? \$\endgroup\$
    – mellamokb
    Commented Apr 4, 2011 at 16:42
  • \$\begingroup\$ 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... \$\endgroup\$ Commented Apr 4, 2011 at 17:38

3 Answers 3

5
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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)? \$\endgroup\$ Commented Apr 5, 2011 at 10:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.