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$ ?

#Exponents #Summing #Powersof2

Easy Math Editor

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.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 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"

Math	Appears 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}$

Comments

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

Josh Rowley - 7 years, 4 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.

Josh Speckman - 7 years, 4 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.

Samuraiwarm Tsunayoshi - 7 years, 4 months ago

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

Josh Speckman - 7 years, 4 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.

Samuraiwarm Tsunayoshi - 7 years, 4 months ago

@Samuraiwarm Tsunayoshi – 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.

Josh Speckman - 7 years, 4 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.

Curtis Clement - 6 years, 5 months ago

Math	Appears 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}$