Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

project euler

Project Euler: Efficient exponentiation

Hammad Qayyum


The most naïve way of computing n^15 requires fourteen multiplications:

n × n × … × n = n^15

But, using a binary method, we can compute n^15 in six multiplications:

n × n = n^2
n^2 × n^2 = n^4
n^4 × n^4 = n^8
n^8 × n^4 = n^12
n^12 × n^2 = n^14
n^14 × n = n^15

However, it is also possible for us to compute n^15 in only five multiplications:

n × n = n^2
n^2 × n = n^3
n^3 × n^3 = n^6
n^6 × n^6 = n^12
n^12 × n^3 = n^15

We will define m(k) to be the minimum number of multiplications to compute n^k, for example, m(15) = 5.

For 1 ≤ k ≤ 200, find ∑ m(k).

Source of problem:


The problem given above can be solved with dynamic programming or recursive functions.

We will use the recursive function method to keep track of the number of steps that have already been taken. The number of steps goes to 200, and after 200 steps, our code will start backtracking.

Let’s start making the tree that explains the binary multiplications until we get 16.

Binary multiplications until we get 16

After reaching step number 16, we start backtracking, go back to 8 steps, and then down to 4 steps.

At 8 steps, we can check all the possible combinations of multiplications. For example, after step number 8, the exponent can move to step 9 (with a root 1 multiplication), step 10 (with root 2 multiplication), step 12, and step 16, as is shown below:

All the possible combinations of the multiplications at 8

Then, we will proceed with step 9, since it is the smallest one. Again, we will get a large number of options, as can be seen in the picture below.

All the possible combinations of the multiplications when choosing 9

In the flow shown above, we get 10 again. We won’t follow this path to 10, because we have already achieved this in fewer multiplication steps. Once we have used all the options from 8 and backtracked to 4, we will repeat all these steps to get 4 again.

Since the tree contains 1, we can conclude that we can generate all the possible paths less than the limit, that is, 16. Now, we can use the path with the minimum number of steps.

We can also generate all the options and trees with the following code, which solves our problem.


using System;
using System.Diagnostics;

namespace euler {
    class ExponentProblem {

        public static void Main(string[] args) {
            new ExponentProblem().BruteforceAlgorithm();
        // initializing the variables.
        int lim = 200;
        int[] cost_answer;
        int[] path;
        public void BruteforceAlgorithm() {
            //  creating new empty arrays
            cost_answer = new int[lim + 1];
            path = new int[lim + 1];
            int result = 0;
        //   filling the arrays with max values
            for (int i = 0; i <= lim; i++)
                cost_answer[i] = int.MaxValue;
            // calling backtrack function here
            Backtrack(1, 0);
            //  adding the cst to result variable and updating the result variable 
            for (int i = 1; i <= lim; i++)
                result += cost_answer[i];                
            Console.WriteLine("the sum of m is {0}", result);

        public void Backtrack(int power, int depth) {
            // boundary conditions/ exceptional cases
            if (power > lim || depth > cost_answer[power]) return;
            // updating the cost and path arrays
            cost_answer[power] = depth;
            path[depth] = power;
            // calling the function recursively until the limit is reached
            for (int i = depth; i >= 0; i--)
                Backtrack(power + path[i], depth + 1);

Code solution for efficient exponentiation


project euler

View all Courses

Keep Exploring