Project Euler: Efficient exponentiation
Problem
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
Solution
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.
Code
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);
}
}
}RELATED TAGS
CONTRIBUTOR
View all Courses
