11
\$\begingroup\$

Your task is to slowly calculate exponentiation, with the following steps:

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!

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

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

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.

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 23 22 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]] / [[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
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

Haskell, 64 bytes

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],[4294967296]]. 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
\$\endgroup\$
0
\$\begingroup\$

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