# Calculate Exponents bit by bit

Given two inputs (in this example, 4 and 8), you must calculate the exponentiation by calculate the equation bit by bit. You would do 4^8, have a greater base value (4) and a smaller exponent (8). You can do this using more exponentiation and division. You can divide the exponent by a value X (provided X is a prime divisor of the exponent), and make the base value (B) into B^X. For example, you can do:

4^8 = (4 ^ 2)^(8 / 2) = 16^4


I have replaced X with 2 in the previous equation.

You can 'simplify' 16^4 further, again with X = 2:

16^4 = (16 ^ 2)^(4 / 2) = 256^2


And then finally calculate a number (again, X = 2):

256^2 = (256 ^ 2)^(2 / 2) = 65536^1 = 65536


Therefore,

4^8 = 16^4 = 256^2 = 65536


This is the output you should give. The output separator is a little flexible, for example, you can separate the equations by newlines or spaces instead of =. Or, you may put them into a list (but you mustn't use a digit or the ^ character as a separator).

As Martin Ender pointed out, the ^ is also flexible. For example, you may use [A, B] or A**B instead of A^B in the output.

X may only be prime, which means you cannot use X = 8 to get straight to the solution, and the values of X will only be prime factors of the second input (the exponent).

### Examples:

(input) -> (output)
4^8 -> 4^8=16^4=256^2=65536
5^11 -> 5^11=48828125
2^15 -> 2^15=32^3=32768 (2^15=8^5=32768 is also a valid output)


Mind that the input format is also flexible (eg you may take A \n B or A B instead of A^B. Obviously, this wouldn't be a problem if you write a function taking two arguments.

In the second example, we go straight to calculation, since 11 is prime and we cannot take any more steps.

You may write a program or a function to solve this, and you may print or return the value, respectively.

As this is , that shortest code wins!

• @JonathanAllan I was looking at that too. 32^3 and 8^15 are not 512 either. Feb 22 '17 at 13:24
• @JonathanAllan thanks for spotting that :)
– Okx
Feb 22 '17 at 16:06
• @Okx the last one can be printed as x^1?
– Rod
Feb 22 '17 at 16:08
• @Rod no, it can't. That would be silly.
– Okx
Feb 22 '17 at 16:08

# JavaScript (ES7), 55 bytes

f=(a,b,c=2)=>b>1?b%c?f(a,b,c+1):a+['^'+b,f(a**c,b/c)]:a


Uses , in place of = (2^15,8^5,32768).

### Test cases

f=(a,b,c=2)=>b>1?b%c?f(a,b,c+1):a+['^'+b,f(Math.pow(a,c),b/c)]:a
g=(a,b)=>console.log(f(${a},${b}):,f(a,b))

g(4,8)
g(5,11)
g(2,15)

Note: the snippet uses Math.pow instead of ** for cross-browser compatibility.

# 05AB1E, 2322 17 bytes

Saved 5 bytes by noticing the flexible output format.

Ò©gƒ²®N¹‚£PŠm‚Rˆ


Try it online!

Explanation

Example for 2^15

Ò©                 # calculate primefactors of exponent and store in register
# STACK: [3,5]
g                # length
# STACK: 2
ƒ               # for N in range[0 ... len(primefactors)] do
²              # push base
# STACK: 2
®             # push primefactors
# STACK: 2, [3,5]
N¹‚£         # split into 2 parts where the first is N items long
# 1st, 2nd, 3rd iteration: [[], [3, 5]] / [, ] / [[3, 5], []]
P        # reduce each by product
# STACK 1st iteration: 2, [1,15]
# split list to items on stack
# STACK 1st iteration: 2, 1, 15
Š      # move down the current exponent
# STACK 1st iteration: 15, 2, 1
m     # raise base to the rest of the full exponent
# STACK 1st iteration: 15, 2
‚    # pair them up
# STACK 1st iteration: [15,2]
R   # reverse the pair
# STACK 1st iteration: [2,15]
ˆ  # store it in global list
# print global list at the end of execution


# Jelly, 16 bytes

*Uż:Ṫ
ÆfṪ1;×\ç@€


Try it online!

Input is a single list [base, exponent]. The return value of the lower monadic link is a list of lists, as a full program a representation of that list is printed, for example 2^15=8^5=32768^1 is printed as:

[[2, 15], [8, 5], [32768, 1]]


### How?

ÆfṪ1;×\ç@€ - Main link: [base, exponent]            e.g.     [4,12]
Æf         - prime factorization array (vectorises)      [[2,2],[2,2,3]]
Ṫ        - tail (tailing first costs bytes)                   [2,2,3]
1;      - 1 concatenated with the result                   [1,2,2,3]
×\    - reduce with multiplication  (make factors)       [1,2,4,12]
ç@€ - call last link (1) as a dyad for €ach with reversed @rguments
- implicit print if running as a full program

*Uż:Ṫ - Link 1, an entry in the equality: [base, exponent], factor  e.g. [4, 12], 4
*     - exponentiate (vectorises) : [base ^ factor, exponent ^ factor]   [256, 20736]
U    - upend                                                            [20736, 256]
:  - integer division: [base // factor, exponent // factor]           [1, 3]
ż   - zip                                                        [[20736, 1], [256, 3]]
Ṫ - tail                                                                    [256, 3]
...i.e at a factor of 4: 4 ^ 12 = 256 ^ 3


It could be formatted as a grid for 2 bytes by a trailing µG, e.g.:

    2    15
8     5
32768     1


...or fully formatted, including trimming off the ^1, for 9, with a trailing j€”^j”=ṖṖ, e.g.:

2^15=8^5=32768


# C, 125 123 + 4 (-lm) = 129 127 bytes

i;f(n,m)double n;{if(m-1){printf("%.0f^%d=",n,m);for(i=2;i<=m;i++)if(!(m%i))return f(pow(n,i),m/i);}else printf("%.0f",n);}


Takes a double and an integer.

Try it online!

a#b|v:_<-[x|x<-[2..b],mod b x<1]=[a,b]:(a^v)#div b v|1<2=[[a^b]]


Usage example: 2 # 32 -> [[2,32],[4,16],[16,8],[256,4],[65536,2],]. Try it online!.

How it works:

a#b                       -- take input numbers a and b
|                      -- if
[x|x<-[2..b]   ]    --  the list of all x drawn from [2..b]
,mod b x<1  --  where x divides b
v:_<-                 --  has at least one element (bind the first to v)
= [a,b]:           --  the the result is the [a,b] followed by
(a^v)#div b v   --  a recursive call with parameters (a^v) and (div b v)
|1<2                   -- else (i.e. no divisors of b)
= [[a^b]]          --  the result is the singleton list of a singleton list
--    of a^b


# Bash + GNU utilities, 82

echo $1^$2
f=factor $2|egrep -o "\S+$"
((m=$2/f,r=$1**f,m-1))&&$0$r $m||echo$r


Recursive shell script. This doesn't seem to work in TIO, but runs fine when saved as a script and executed:

$./expbit2.sh 4 8 4^8 16^4 256^2 65536$ ./expbit2.sh 5 11
5^11
48828125
$./expbit2.sh 2 15 2^15 32^3 32768$