Something interesting about powers of 2

Let's say we have all of the powers of 2 2 from 20 2^0 to 26 2^6 . In other words, 1,2,4,8,16,32,64 {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 1 , we can make 2 2 , we can make 3 3 , and in fact we can make all of the integers up to 127 127 . In general, if we have the powers of 2 2 up to 2n 2^n , we can make all of the integers up to 2n+11 2^{n+1} - 1 . Why is this? Is there a similar property for powers of 3 3 , or 4 4 ?

Note by Josh Speckman
5 years, 6 months ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 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"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

We could show it inductively, something along the lines of: Say that using each power of 2 up to 2n 2^n at most once allows us to make every number up to 2n+11 2^{n+1}-1 . Then, when we add 2n+1 2^{n+1} to the list of powers of 2 that we are allowed to use then every integer x where 2n+1+1x2n+21 2^{n+1}+1 \le x \le 2^{n+2} -1 can be made from the sum (x2n+1)+2n+1 (x-2^{n+1}) + 2^{n+1} . This is valid because 1x2n+12n+11 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 2n 2^n at most once. Also, making the value 2n+1 2^{n+1} itself is trivial. It can be shown to be true for some base case so we are done

Josh Rowley - 5 years, 6 months ago

Log in to reply

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 - 5 years, 6 months ago

Log in to reply

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

12,102,1002,...,100000...02(n0s)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 2n+12^{n+1} ways. But you can't choose nothing, so you get 2n+112^{n+1} - 1 ways.

You know that no two numbers are the same, so there'll be 2n+112^{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 - 5 years, 6 months ago

Log in to reply

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

Josh Speckman - 5 years, 6 months ago

Log in to reply

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

Samuraiwarm Tsunayoshi - 5 years, 6 months ago

Log in to reply

@Samuraiwarm Tsunayoshi You would need (for powers of 3 3 , the integers 1,2,3,4,5,9,10,11,27,28,29, {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 n , you need n0,n0+1,n0+2,n1,n1+1,n1+2,n2,n2+1, {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 n representation of every number be in the set 1,2,3,,n1 {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 - 5 years, 6 months ago

Log in to reply

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 2n2^{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{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: 12\frac{1}{2} + 12\frac{1}{2} = 12\frac{1}{2} + 14\frac{1}{4} + 14\frac{1}{4} = 12\frac{1}{2} + 14\frac{1}{4} + 18\frac{1}{8} + 18\frac{1}{8} = ..... . This is true for 2n2^{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{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 2a2^{a} + 2b2^{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 - 4 years, 8 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...