×

# 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, 1 month ago

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. · 2 years, 3 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. · 3 years, 1 month ago

That's what I was thinking of. There actually is a similar property, but you need more numbers. Which ones? · 3 years, 1 month 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, 1 month 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, 1 month 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, 1 month ago