# Something interesting about powers of 2

Let's say we have all of the powers of $2$ from $2^0$ to $2^6$. In other words, ${1,2,4,8,16,32,64}$. What is the smallest number than you cannot make using at most one of each of these numbers? We can make $1$, we can make $2$, we can make $3$, and in fact we can make all of the integers up to $127$. In general, if we have the powers of $2$ up to $2^n$, we can make all of the integers up to $2^{n+1} - 1$. Why is this? Is there a similar property for powers of $3$, or $4$? Note by Josh Speckman
6 years, 7 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

We could show it inductively, something along the lines of: Say that using each power of 2 up to $2^n$ at most once allows us to make every number up to $2^{n+1}-1$. Then, when we add $2^{n+1}$ to the list of powers of 2 that we are allowed to use then every integer x where $2^{n+1}+1 \le x \le 2^{n+2} -1$ can be made from the sum $(x-2^{n+1}) + 2^{n+1}$. This is valid because $1 \le x-2^{n+1} \le 2^{n+1}-1$ and we know that all of these numbers can be made using powers of 2 no greater than $2^n$ at most once. Also, making the value $2^{n+1}$ itself is trivial. It can be shown to be true for some base case so we are done

- 6 years, 7 months ago

I actually had a different method in mind (kind of the same), but this is also really good. I hadn't though of it that way before.

- 6 years, 7 months ago

You can change every number to base 2, so you get...

$1_{2},10_{2},100_{2},...,100000...0_{2} (n 0's)$.

You can choose any number if you want or you don't want, so you get $2^{n+1}$ ways. But you can't choose nothing, so you get $2^{n+1} - 1$ ways.

You know that no two numbers are the same, so there'll be $2^{n+1} - 1$ numbers, which covers every number.

Powers of 3, 4, etc. doesn't have similar property as you can't make number 2 and other numbers from powers of 3, 4, etc.

- 6 years, 7 months ago

That's what I was thinking of. There actually is a similar property, but you need more numbers. Which ones?

- 6 years, 7 months ago

Powers of 3, 4, etc. have a pattern for that, but it's unpredictable, because there're huge gaps between $a^{k}$ and $a^{k+1}$ for any non-negative integer a>2, k.

- 6 years, 7 months ago

You would need (for powers of $3$, the integers ${1,2,3,4,5,9,10,11,27,28,29,\cdots}$. It's not as pretty, but it works. In general, for any integer $n$, you need ${n^0,n^0 + 1,n^0 + 2,n^1,n^1 + 1,n^1 + 2,n^2,n^2 + 1,\cdots}$ because you need to be able to make every place in the base $n$ representation of every number be in the set ${1,2,3,\cdots,n-1}$. However, using this method, we overcount. So powers of 2 make a much more elegant framework, but you can do it with other integers.

- 6 years, 7 months ago

This is what is know as binary code, which is used to represent everything that a computer does because the nth position of the 1 represents $2^{n}$, but 0 has no value. However, it is still significant as it shifts the positions of the 1's which have some value base 2. Also, to put it simply 1=on/pulse, 0=off/no pulse. Now I will prove that the code can be used to represent every value. It goes as follows: lets choose any value ${x}$. Now think of it as a piece of paper that you cut in half. Then you one of those pieces in half and so on, Numerically this is: $\frac{1}{2}$ + $\frac{1}{2}$ = $\frac{1}{2}$ + $\frac{1}{4}$ + $\frac{1}{4}$ = $\frac{1}{2}$ + $\frac{1}{4}$ + $\frac{1}{8}$ + $\frac{1}{8}$ = ..... . This is true for $2^{n}$ for all positive integers n, by repeating the argument. However, there sum is not infinite! - it stops at 1, which is why you always produce ${x}$-1 (i.e. 32+16+8+4+2+1 = 64 -1). To prove that it produces all the even numbers, it is easy to see that all even numbers are a sum of $2^{a}$ + $2^{b}$ because it is possible to divide both sides by 2 in each case. All you have to do to produce all the odd numbers is to add 1.

- 5 years, 9 months ago