Unusual binary representation (Posted on 2005-06-14)

	Submitted by McWorter
No Rating
Solution:	(Hide)
Every positive integer can be written in base 2. An example should suffice to show how to construct a strictly increasing alternating sum of powers of 2 for any given positive integer. Suppose our number in base two representation is n=110011101. Consider the string of 3 consecutive 1's in this representation. If we add 1000 in base two to n we get n=110011101 + 100 ___________ 110100001 The sum has zeros where the string of 1's were in n and a 1 in the next higher place. So n=2^0+2^2+2^3+2^4+2^7+2^8=2^0+2^5+2^7+2^8-2^2=2^0-2^3+2^5+2^7+2^8. Almost done; must do something about 2^5+2^7+2^8. We can do the same thing we just did to the highest two consecutive powers of 2. 2^7+2^8= 110000000 + 2^7= 10000000 __________________ 1000000000 So 2^7+2^8=2^9-2^7, and we can now write n=2^0-2^3+2^5-2^7+2^9, an alternating sum of strictly increasing powers of 2. In general, replace sums of consecutive powers of 2 with the difference between the next higher power of 2 and the first power of 2 in the string.

	Subject	Author	Date
	re: a slightly different proof	Bob Smith	2005-06-21 01:21:27
	a slightly different proof	Paul	2005-06-18 01:46:25
	prove	armando	2005-06-15 14:18:44
	Proof (Based on what was said earlier)	Gamer	2005-06-15 02:14:45
	re(2): Negabinary	Richard	2005-06-15 01:48:53
	re: Negabinary	Old Original Oskar!	2005-06-15 00:09:14
	Negabinary	Richard	2005-06-14 21:54:24
	Answer	e.g.	2005-06-14 20:18:19
	No Subject	Jer	2005-06-14 17:03:51