15
\$\begingroup\$

Write the shortest program to print the non-trivial powers ≤ 2^12 in order

non-trivial power means the base and exponent are > 1

Leading whitespace is optional
When there are multiple solutions, the order is not important, so

16 = 4^2, 2^4 is ok

Sample output:

      4 = 2^2
      8 = 2^3
      9 = 3^2
     16 = 2^4, 4^2
     25 = 5^2
     27 = 3^3
     32 = 2^5
     36 = 6^2
     49 = 7^2
     64 = 2^6, 4^3, 8^2
     81 = 3^4, 9^2
    100 = 10^2
    121 = 11^2
    125 = 5^3
    128 = 2^7
    144 = 12^2
    169 = 13^2
    196 = 14^2
    216 = 6^3
    225 = 15^2
    243 = 3^5
    256 = 2^8, 4^4, 16^2
    289 = 17^2
    324 = 18^2
    343 = 7^3
    361 = 19^2
    400 = 20^2
    441 = 21^2
    484 = 22^2
    512 = 2^9, 8^3
    529 = 23^2
    576 = 24^2
    625 = 5^4, 25^2
    676 = 26^2
    729 = 3^6, 9^3, 27^2
    784 = 28^2
    841 = 29^2
    900 = 30^2
    961 = 31^2
   1000 = 10^3
   1024 = 2^10, 4^5, 32^2
   1089 = 33^2
   1156 = 34^2
   1225 = 35^2
   1296 = 6^4, 36^2
   1331 = 11^3
   1369 = 37^2
   1444 = 38^2
   1521 = 39^2
   1600 = 40^2
   1681 = 41^2
   1728 = 12^3
   1764 = 42^2
   1849 = 43^2
   1936 = 44^2
   2025 = 45^2
   2048 = 2^11
   2116 = 46^2
   2187 = 3^7
   2197 = 13^3
   2209 = 47^2
   2304 = 48^2
   2401 = 7^4, 49^2
   2500 = 50^2
   2601 = 51^2
   2704 = 52^2
   2744 = 14^3
   2809 = 53^2
   2916 = 54^2
   3025 = 55^2
   3125 = 5^5
   3136 = 56^2
   3249 = 57^2
   3364 = 58^2
   3375 = 15^3
   3481 = 59^2
   3600 = 60^2
   3721 = 61^2
   3844 = 62^2
   3969 = 63^2
   4096 = 2^12, 4^6, 8^4, 16^3, 64^2
Improve this question
\$\endgroup\$
9
  • \$\begingroup\$ There's a lot of powers missing here; what about 21^3 etc? What is your definition of "non-trivial powers"? \$\endgroup\$
    – hallvabo
    Mar 31, 2011 at 20:41
  • \$\begingroup\$ Is it also possible to print multiple lines with the same number on the left, if there are multiple solutions? \$\endgroup\$
    – FUZxxl
    Mar 31, 2011 at 20:43
  • \$\begingroup\$ @hallvabo, oops haven't had coffee yet this morning. fixed it now \$\endgroup\$
    – gnibbler
    Mar 31, 2011 at 20:47
  • \$\begingroup\$ @FUZxxl, you have to put the multiple solutions on the same line, although for interest please submit the alternative version too if the requirement makes a large difference in your language \$\endgroup\$
    – gnibbler
    Mar 31, 2011 at 20:50
  • \$\begingroup\$ +1 when I get more votes :-) \$\endgroup\$
    – hallvabo
    Mar 31, 2011 at 21:57

19 Answers 19

Reset to default
7
\$\begingroup\$

Python, 113

R=range
for k in R(4097):
 v=', '.join(`i`+'^'+`j`for i in R(2,65)for j in R(2,13)if i**j==k)
 if v:print k,'=',v

This takes a few seconds to complete.
A faster (148 chars) version, using a dictionary to avoid the outermost loop, runs in ~ 0.01 sec:

R=range(2,65)
p={}
for i in R:
 for j in R:
    if i**j<4097:p[i**j]=p.get(i**j,[])+[`i`+'^'+`j`]
for k,v in sorted(p.items()):print k,'=',', '.join(v)
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ I'm pretty sure the equals sign is required for the output, though that shouldn't change the code size by much. \$\endgroup\$
    – Kevin Brown-Silva
    Mar 31, 2011 at 22:12
  • \$\begingroup\$ Whops, I accidentally removed it when I got rid of the (optional) leading whitespace. Fixed it! \$\endgroup\$
    – hallvabo
    Mar 31, 2011 at 22:32
6
\$\begingroup\$

Ruby 1.9, 112 111 99 characters

4097.times{|x|s=[]
2.upto(64){|a|2.upto(12){|b|a**b==x&&s<<[a,b]*?^}}
puts [x,s*", "]*" = "if s[0]}

This takes about 0.8 seconds to complete on my system. A faster solution is 111 characters long:

h={};(2..64).map{|a|(2..12).map{|b|a**b<4097&&(h[a**b]||=[])<<[a,b]*?^}}
puts h.sort.map{|a,b|[a,b*", "]*" = "}
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Windows PowerShell, 102

With help by Ventero for the initial code.

$OFS=', '
4..4KB|%{$x=$_
if($s=2..64|%{$a=$_
2..12|?{[math]::pow($a,$_)-eq$x}|%{"$a^$_"}}){"$x = $s"}}
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Interactive J, 118 101 98

3 :0"0 i.4097
if.#l=.":2j2+63(<.@%~j.|)I.y=,^/~2+i.63
do.echo(":y),' = ',l rplc j`^,' ';', 'end.
)

(last newline unneeded)

Still a lot of code for the presentation...

Note: in theory changing 63 and 63 to y and y saves 2 more bytes but that version uses extreme amount of memory.

Edited by randomra.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Using [space]j[backtick]^,' ';', ' instead of 'j';'^';' ';', ' saves 3 bytes. (Given up formatting it...) \$\endgroup\$
    – randomra
    Apr 16, 2015 at 21:35
  • \$\begingroup\$ @randomra You've got edit rights; please go ahead! (I can't find a box with J to verify with my current setup, and I'm in kind of in a hurry). This would make J the best of the show, it would be a pity not to show it off! :-) \$\endgroup\$
    – J B
    Apr 17, 2015 at 12:58
3
\$\begingroup\$

Bash, 138 chars

i=2;j=1
f(){((v>4096))&&((j=1,++i))
a[$v]+="$i^$j, "
((v=i**++j,i<65))&&f
}
f
f(){
echo $j = ${a[$j]}
((j++<v))&&f
}
f|sed '/=$/d;s/.$//'

Edits

  • (169 : 155) 2 for for a while.
  • (155 : 148) Append with +=
  • (148 : 147) output with while, reusing j
  • (147 : 142) use sed to remove empty lines
  • (142 : 137) put v in (()), use v for 4096 (last value)
  • (137 : 134) remove sed quotes, join (()) expressions
  • (134 : 132) replace loops with recursive functions
  • (132 : 142) forgot the comma , :(
  • (142 : 138) tired of updates :p
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

PHP, 138 characters - Output

<?for($b=1;++$b<65;)for($e=1;++$e<13;)if(4097>$f=pow($b,$e))$p[$f][]="$b^$e";ksort($p);foreach($p as$n=>$c)echo"$n = ".join($c,", ")."\n";

Ungolfed

<?php

// Array of combinations

$powers = array();

// Loop through every base from 2 to 64, as 64 is the highest you can go

for($base = 2; $base < 65; $base++){

    // Loop through all powers from 2 to 12, as 12 is the maximum

    for($power = 2; $power < 13; $power++){

        // Calculate the power

        $end = pow($base, $power);

        // Kill the loop if the result is too high

        if($end > 4096){
            break;
        }

        // Add the combination if the result is within limits

        $powers[$end][] = $base."^".$power;
    }
}

// Sort the powers by the total amount

ksort($powers);

// Output the powers in the correct format

foreach($powers as $number => $combinations){
    echo $number." = ".implode($combinations, ", ")."\n";
}
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Python, 127 chars

F={}
for i in range(693):a,b=i/11+2,i%11+2;F[a**b]=F.get(a**b,'')+', %d^%d'%(a,b)
for k in sorted(F)[:81]:print k,'=',F[k][2:]
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 152 byte

Print/@Cases[Range@4096,n_/;(2<=##&&##==##&)@@(f=#2&@@@FactorInteger@#&)@n:>{n,Row[{n^(1/#),#}~Row~"^"&/@Reverse@Rest@Divisors@#,", "]&@@f@n}~Row~" = "]

This got embarrassingly long. Something like 25 characters are spent on output formatting. The actual code is fairly simple: filter those numbers where all exponents in the prime factorisation are equal. Then, for each of those produce one result for each divisor of the exponent (excluding 1, including itself).

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

C (589 bytes)

int pow(int a,int b){
   int res = 1;
   while(b>0){
    while(b%2 == 0){
        a *= a; b/=2;
    }
    b--;
    res = res*a;
}
return res;
}
char s[99],t[9];

int main(){
   int N,T,a,i,f,e,n;
  for(n = 2; n <= 1<<12; n++){
      strcpy(s,"");
      T = N = n;
      f = 0;
      int sqt = sqrt(N)+1;
      for(i = 2; i <= sqt; i++){
         for(e=0;0==N%i;e++,N/=i);
           for(a = i; e > 1;e = e%2?(e+1)/2:e/2)
              for(a=i;a<T;pow(a,e)==T?f++?0:printf("%d =",T),sprintf(t,", %d^%d",a,e),strcat(s,t):0,a*=i);
    }
    f?puts(s+1):0;
   }
   return 0;
 }

I didn't golfed also this approach is not the best one but yet fast enough to produce an exact 0s in ideone.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

OCaml + Batteries, 220 206 158 156 characters

Taking a hint from the best-scored solutions:

Printf.(iter(fun x->match
String.join", "[?List:sprintf"%d^%d"b e|b<-2--64;e<-2--12;float
x=float b**float e?]with""->()|s->printf"%5d = %s\n"x s)(4--4096))

(Line endings at significative whitespace to keep lines short.) A faster but longer version that generates powers instead of testing them:

Printf.(List.(iter(fun l->printf"%5d = %s\n"(fst(hd l))(String.join", "(map
snd l)))(group(fun(x,_)(y,_)->x-y)[?List:truncate p,sprintf"%d^%d"b
e|b<-2--64;e<-2--12;p<-List:[float b**float e];p<=4096.?])))
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Haskell, 146 characters

c[a]=a
c(a:z)=a++", "++c z
n#[]=""
n#s=shows n$" = "++c s++"\n"
main=putStr$(\n->n#[shows x$'^':show y|x<-[2..64],y<-[2..12],x^y==n])=<<[4..4096]
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

JavaScript, 160

o={}
i=2
s=''
n=4097
for(k=4;k<n;k=++i*i)for(j=2;k<n;k*=i)
{a=i+'^'+j
if(o[k])o[k]+=', '+a
else o[k]=a
j++}for(i=0;i<n;i++)if(o[i])s+='\n'+i+' = '+o[i]
alert(s)

194

o={},i=2,s='',n=4096
for(k=4;k<=n;k=i*i){for(j=2;k<=n;k*=i){o[k]=o[k]||[]
o[k].push(i+'^'+j)
j++}i++}
for(i=0;i<n;i++){if(o[i]){s+='\n'+i+' = '
for(j in o[i])s+=(j==0?'':', ')+o[i][j]}}
alert(s)
Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Rolled back; please post golfing suggestions as comments, not edits. \$\endgroup\$
    – lirtosiast
    Oct 11, 2015 at 18:13
1
\$\begingroup\$

Pyth, 39 bytes

jm++^Fhd" = "j", "jL\^d<.g^Fk^tS64 2 81

Try it online here.

jm++^Fhd" = "j", "jL\^d<.g^Fk^tS64 2 81
                               S64       [1-64]
                              t          Discard first element
                             ^     2     Cartesian product of the above with itself
                        .g               Group the pairs, as k, using:
                          ^Fk              [a,b] -> a^b
                       <             81  Take the first 81 results of the above (those where exponential <= 4096)
 m                                       Map the remaining groups, as d, using:
                  jL\^d                    Join each pair in d on "^"
             j", "                         Join on ", "
  +     " = "                              Prepend " = "
   +^Fhd                                   Prepend the result of the exponent of one of the pairs
j                                        Join the result of the above on newlines, implicit print

If the output format is flexible enough to remove the need for spaces, -5 bytes to replace " = " with \= and ", " with \,

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Haskell, 131

p[]=return()
p((x,y,z):s)=do print$show x++" = "++show y++"^"++show z;p s
main=p [(x,y,z)|x<-[2..2^12],y<-[2..x],z<-[2..x],x==y^z]
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ powers that have the same value are supposed to be on the same line \$\endgroup\$
    – MtnViewMark
    May 20, 2011 at 4:22
0
\$\begingroup\$

JavaScript, 148 chars

s=''
for(i=2;i<4097;i++){q=''
for(a=2;a<65;a++)for(b=2;b<13;b++)if(Math.pow(a,b)==i)q+=a+'^'+b+', '
if(q)s+=i+' = '+q.slice(0,-2)+"\n"}alert(s)
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

C 184

Should compile (with warnings) with any C compiler

char*l[5000],*t=l+4100,*u;
main(b,e,r) 
{
  for(;++b<65;)
    for(e=2,r=b;(r*=b)<4100;l[r]=u)
      t+=1+sprintf(u=t,"%s, %d^%d",l[r]?l[r]:"",b,e++);
  for(r=1;++r<4097;)
    l[r]&&printf("%d =%s\n",r,l[r]+1);
}
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Pyth, 55 chars

=Tr2 64V^2 12JYFZTFbTIqN^ZbaJj\^[Zb))))IJjk[Nd\=dj", "J

My first time using Pyth, so it can probably be improved. It's a brute force that checks up to 64^64, thus is quite slow. You can save time by only checking up to 64^12 but it would cost a byte.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6) 134 127

Edit revised, bugfixed and shortened Edit 2After some research, I realized that this answer was invalid for chronological reasons. The question predates arrow functions by years.

All that said, the other JS answers are way too complicated

/* for TEST:redefine console.log */ console.log=x=>O.innerHTML+=x+'\n';

for(l=[],b=1;++b<65;)for(e=2,r=b;(r*=b)<4197;)(l[r]=l[r]||[]).push(b+'^'+e++);l.some(function(v,i){console.log(i+' = '+v.join(', '))})
<pre id=O></pre>

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ If you don't care too much about '=' formatting, then you can reduce down to 121 bytes: for(l=[],b=1;++b<65;)for(e=2,r=b;(r*=b)<4197;)(l[r]=l[r]||[]).push(b+'^'+e++);l.map((v,i)=>console.log(i+'='+v.join`, `)) \$\endgroup\$
    – Mama Fun Roll
    Oct 11, 2015 at 16:44
  • \$\begingroup\$ @molarmanful there are strict requirements about formatting \$\endgroup\$
    – edc65
    Oct 11, 2015 at 16:50
  • \$\begingroup\$ Oh well... at least change the v.join part. That can at least bring the byte count down to 123. \$\endgroup\$
    – Mama Fun Roll
    Oct 11, 2015 at 16:51
  • \$\begingroup\$ @molarmanful at time this challenge (and this answer!) were posted, template strings were not implemented in any browser: Firefox was the first - rel 34, dec first 2014 - then Chrome, march 2015. You cannot use a feature that was available 3 years after the question \$\endgroup\$
    – edc65
    Oct 11, 2015 at 19:12
  • \$\begingroup\$ Oh well... I did not know that. I just got into ES6 a week ago! \$\endgroup\$
    – Mama Fun Roll
    Oct 12, 2015 at 3:07
0
\$\begingroup\$

05AB1E, 36 bytes

2žxŸãΣ`m}99£.γ`m}εн`m'=yε'^ý}„, ý)}»

I have the feeling this can be improved a bit by using a slightly different approach..

Try it online.

Explanation:

2žxŸ           # Create a list in the range [2,64]
    ã          # Create each possible pair by taking the cartesian product with itself
Σ`m}           # Sort these `a,b`-pairs by their result of `a ** b`
    99£        # Only leave the first 99 pairs
       .γ`m}   # And then group the `a,b`-pairs by their result of `a ** b`
ε              # Now map each list of pairs `y` to:
 н             #  Take the first pair of list `y`
  `m           #  Take the `a ** b` value
 '=           '#  Push character "=" to the stack
 yε            #  Inner map over the pairs of list `y`:
   '^ý        '#   Join each pair with a "^" delimiter
      }„, ý    #  After the inner map: join these strings with a ", " delimiter
 )             #  Wrap all values on the stack into a list
}»             # After the outer map: join every inner list by spaces,
               # and the outer list by newlines (and output the result implicitly)
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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