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 \)?

## Comments

Sort by:

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

Log in to reply

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 · 2 years, 11 months ago

Log in to reply

– Josh Speckman · 2 years, 11 months ago

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

– Samuraiwarm Tsunayoshi · 2 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.Log in to reply

– Josh Speckman · 2 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.Log in to reply

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

xwhere \( 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 · 2 years, 11 months agoLog in to reply

– Josh Speckman · 2 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.Log in to reply