Trusted answers to developer questions

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: https://projecteuler.net/problem=122

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.

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:

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.

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

RELATED TAGS

project euler

efficient

exponentiation

communitycreator

csharp

CONTRIBUTOR

Hammad Qayyum

RELATED COURSES

View all Courses

Keep Exploring

Related Courses