You don’t need to be a math whiz to be a good programmer, but there are a handful of tricks you will want to add to your problem solving bag to improve the performance of your algorithms and make an impression in technical interviews. In this tutorial, you will learn how to sum consecutive powers of 2 with a simple and easy to remember equation. Knowing this equation will help you understand recursive runtimes and quickly calculate Big O time and space complexities.
_This article originally published on jarednielsen.com
How to Sum Consecutive Powers of 2
How would you add these numbers?
2^0 + 2^1 + 2^2 + 2^3
Was your first thought to take the ‘brute force’ approach?
2^0 = 1
2^1 = 2, + 1 = 3
2^2 = 4, + 3 = 7
2^3 = 8, + 7 = 15
Nothing wrong with that and you probably didn’t need a pen and paper or a calculator to get there.
What if the final power was not 2^3 but 2^30? Or 2^300?
Brute force would be brutal.
What if you were presented with this situation?
2^0 + 2^1 + 2^2 + … + 2^n = ?
How would you solve this?
Programming is Problem Solving
What is programming?
Programming is problem solving.
What problems do we solve?
There are two primary categories of problems we solve as programmers:
- Automation
- Algorithms
We could write a for loop to automate the addition of our powers of 2:
const sumPowers2 = power => {
let sum = 0;
for (let i = 0; i < power; i++) {
sum += 2**i;
}
return sum;
}
Will it scale?
What’s the Big O?
O(n).
Why?
Our function needs to perform one operation for every input, so the order of our algorithm is O(n) or linear time complexity.
There must be a better way!
Rather than automate the brute force approach, how can we solve this problem algorithmically?
Math O’Clock 🧮 🕐
I’m about to blow your mind.
Check this out:
1 = 1
😐
Bear with me.
🐻
If 1 is equal to 1, then it follows that
1 = 2 - 1
And if
1 + 2 = 3
Then it follows that
1 + 2 = 4 - 1
Let’s take it one more step. If
1 + 2 + 4 = 7
Then
1 + 2 + 4 = 8 - 1
Cool?
😎
Let’s power up!
What is x in this equation?
2^x = 8
Or, in plain English, “How many 2s multiplied together does it take to get 8?”
We could also write it as a logarithm:
log2(8) = 3
We could say, “To what power do we raise 2 for a product of 8?”
🧐
We know that 2^2 = 4.
And 2^1 = 2
And 2^0 = 1.
“Wait, what?”
Why is 2^0 = 1?
Table time! 🏓
| Exponent | = | = | Power |
|---|---|---|---|
| 2^3 | 8 | ||
| 2^2 | (2^3) / 2 | 8 / 2 | 4 |
| 2^1 | (2^2) / 2 | 4 / 2 | 2 |
| 2^0 | (2^1) / 2 | 2 / 2 | 1 |
See the pattern?
What is 2^4?
16
What is the sum of the powers of 2^4?
1 + 2 + 4 + 8 + 16 = 31
What’s another way we can describe 31?
31 = 32 - 1
What is 2^5?
32
Did you see what happened there?
The sum of the powers of two is one less than the product of the next power.
🤯
Let’s make another table! 🏓🏓
| Exponent | Power | Sum of Powers |
|---|---|---|
| 2^0 | 1 | n/a |
| 2^1 | 2 | 3 |
| 2^2 | 4 | 7 |
| 2^3 | 8 | 15 |
| 2^4 | 16 | 31 |
| 2^5 | 32 | 63 |
What’s the next exponent?
2^6
What’s 2^6?
64
So what is the sum of the powers of 2^6?
🤔
Let’s convert this pattern to an equation to find out.
What if our exponent is unknown, or n?
2^n
What is the sum of 2^n?
☝️ The sum of the powers of two is one less than the product of the next power.
If our power is n, what’s the next power?
n + 1
If n is equal to 1, then it follows
2^n = 2
2^(n + 1) = 4
And if n is equal to 2, then it follows
2^n = 4
2^(n + 1) = 8
Lookin’ good!
How do we get one less than the product of the next power?
We simply subtract 1:
2^(n + 1) - 1
🎉 There's our equation!
Programming is Problem Solving
Let’s take another look at our function from above. How can we refactor this to improve its time complexity?
const sumPowers2 = power => {
let sum = 0;
for (let i = 0; i < power; i++) {
sum += 2**i;
}
return sum;
}
We simply translate our equation into JavaScript!
const sumPowers2 = power => 2**(power + 1) - 1;
What’s the order of our new function?
O(1).
Regardless of the size of the input, our function will always perform the same number of operations.
How to Sum Consecutive Powers of 2
You don’t need to be a math whiz to be a good programmer, but there are a handful of equations you will want to add to your problem solving toolbox. In this tutorial, you learned how to sum consecutive powers of 2 with a simple and easy to remember equation. Knowing this equation will help you understand recursive runtimes and quickly calculate Big O time and space complexities.
Want to level up your problem solving skills? I write a weekly newsletter about programming, problem solving and lifelong learning.
Top comments (8)
If you like to save 4 mins of reading time, here's the summary:
Given an integer n, find the sum of 20 + 21 + ... + 2n.
If you speak binary, and knowing that:
10 - 1 = 1
100 - 1 = 11
1000 - 1 = 111
if n = 4, the answer will be 24+1 - 1.
You're welcome.
Nice, clean and simple. Was I too young or too stupid in school to not see the fascinating aspect of maths ? Or did I need the coding aspect to replace the confusing x with a named variable, less abstracted ?
Python wasn't yet taught in high-school, but if it had been, what a change it could have made in my life... mehh too bad, I regret nothing. I am now fully able to understand and enjoy simple equations like this. And that's good :)
I actually found this explanation pretty long winded and confusing.
This is shorter, to the point, and more general:
math.stackexchange.com/a/2482811/2...
Just plug in P = 2.
Granted, the approach is not exactly intuitive, but once you see how it's done, you can simply rederive it.
Heh thanks for your answer, that's probably that.
Too bad, it comes after the end of my high school and college studies. By that time, I was already rejecting maths completely. It's only a few years ago that I went back to it, to improve my code
Hello.
Umm, just curious.
Why don't you just tell the reader that the example you just show is geometric series.
And there is formula (and derivation about the formula itself if you want) about how to calculate the n terms of geometric sequence, and the sum of this geometric series.
Thanks for a good explanation. This can be also visualized as a sum of nodes in a binary tree.
Sum of GP in math presented with brilliance. Nice job
Very well explained! Kudos ^