# Non trivial powers

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

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

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

• There's a lot of powers missing here; what about 21^3 etc? What is your definition of "non-trivial powers"? – hallvabo Mar 31 '11 at 20:41
• Is it also possible to print multiple lines with the same number on the left, if there are multiple solutions? – FUZxxl Mar 31 '11 at 20:43
• @hallvabo, oops haven't had coffee yet this morning. fixed it now – gnibbler Mar 31 '11 at 20:47
• @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 – gnibbler Mar 31 '11 at 20:50
• +1 when I get more votes :-) – hallvabo Mar 31 '11 at 21:57

## 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*", "]*" = "}


## Python, 113

R=range
for k in R(4097):
v=', '.join(i+'^'+jfor 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)

• I'm pretty sure the equals sign is required for the output, though that shouldn't change the code size by much. – Kevin Brown Mar 31 '11 at 22:12
• Whops, I accidentally removed it when I got rid of the (optional) leading whitespace. Fixed it! – hallvabo Mar 31 '11 at 22:32

## 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"}}  ## Interactive J, 118101 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. • Using [space]j[backtick]^,' ';', ' instead of 'j';'^';' ';', ' saves 3 bytes. (Given up formatting it...) – randomra Apr 16 '15 at 21:35 • @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! :-) – J B Apr 17 '15 at 12:58 ## 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 ## 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"; }  ## 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:]  # 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). ## 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. # OCaml + Batteries, 220206158 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.?])))  ## 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]


# 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]


### 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]}}

• Rolled back; please post golfing suggestions as comments, not edits. – lirtosiast Oct 11 '15 at 18:13

# 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]
^     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 \,

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]

• powers that have the same value are supposed to be on the same line – MtnViewMark May 20 '11 at 4:22

## 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+', '


# 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);
}


## 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.

# 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>

• 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, )) – Mama Fun Roll Oct 11 '15 at 16:44
• @molarmanful there are strict requirements about formatting – edc65 Oct 11 '15 at 16:50
• Oh well... at least change the v.join part. That can at least bring the byte count down to 123. – Mama Fun Roll Oct 11 '15 at 16:51
• @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 – edc65 Oct 11 '15 at 19:12
• Oh well... I did not know that. I just got into ES6 a week ago! – Mama Fun Roll Oct 12 '15 at 3:07

# 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)
`