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
\$\endgroup\$
  • \$\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 '11 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 '11 at 20:43
  • \$\begingroup\$ @hallvabo, oops haven't had coffee yet this morning. fixed it now \$\endgroup\$ – gnibbler Mar 31 '11 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 '11 at 20:50
  • \$\begingroup\$ +1 when I get more votes :-) \$\endgroup\$ – hallvabo Mar 31 '11 at 21:57

19 Answers 19

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*", "]*" = "}
\$\endgroup\$
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)
\$\endgroup\$
  • \$\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 Mar 31 '11 at 22:12
  • \$\begingroup\$ Whops, I accidentally removed it when I got rid of the (optional) leading whitespace. Fixed it! \$\endgroup\$ – hallvabo Mar 31 '11 at 22:32
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"}}
\$\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.

\$\endgroup\$
  • \$\begingroup\$ Using [space]j[backtick]^,' ';', ' instead of 'j';'^';' ';', ' saves 3 bytes. (Given up formatting it...) \$\endgroup\$ – randomra Apr 16 '15 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 '15 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
\$\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";
}
\$\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:]
\$\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).

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

\$\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.?])))
\$\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]
\$\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)
\$\endgroup\$
  • 2
    \$\begingroup\$ Rolled back; please post golfing suggestions as comments, not edits. \$\endgroup\$ – lirtosiast Oct 11 '15 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 \,

\$\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]
\$\endgroup\$
  • \$\begingroup\$ powers that have the same value are supposed to be on the same line \$\endgroup\$ – MtnViewMark May 20 '11 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)
\$\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);
}
\$\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.

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

\$\endgroup\$
  • \$\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 '15 at 16:44
  • \$\begingroup\$ @molarmanful there are strict requirements about formatting \$\endgroup\$ – edc65 Oct 11 '15 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 '15 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 '15 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 '15 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)
\$\endgroup\$

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.