Alternating Sums of powers of 2

Mar 2011
8
0
Hello,
Here's an interesting problem that I have solved, but would like someone else's input simply to see if people come up with the same solution or possibly find a more elegant one. I hope anyone who tries this has fun with the problem!

Which numbers can be written by selecting a subset of the powers of two and alternating them (positive-negative,..., negative-positive,...) and list them in increasing order to form a sum. *A sum cannot be made by simply one power of two, namely n=n. SO, can ALL positive integers be written this way? how many ways can a number 'n' be written as an alternating sum of powers of two?

Thanks in advance,
Rutzer
 
Last edited by a moderator:

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
I think that all numbers can be written in this form, yes. I think there's a nice bijection with the binary digits of the number by taking the consecutive 1 bits and representing them as the difference of two powers of two.
 
Mar 2011
8
0
Excellent, it seems we think alike! I took the binary approach as well. but I also saw the possibility for an induction... thanks for your response.
rutzer
 
Last edited by a moderator:
Feb 2019
1
0
chengdu china
I agree that all numbers seem to be expressible in this way and this can be shown with binary. I also think there are 2 ways to express all non-powers of 2, 1 ways to express powers of 2.
 
Last edited by a moderator: