×

# 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
3 years, 11 months ago

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:

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.

- 3 years 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.

- 3 years, 11 months ago

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

- 3 years, 11 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.

- 3 years, 11 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.

- 3 years, 11 months ago

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

- 3 years, 11 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.

- 3 years, 11 months ago