Show that every positive integer is an alternating sum of
strictly increasing powers of 2.
For example, 5=2^0 2^2 +2^3 and 8=2^3 +2^4 are alternating sums of strictly increasing powers of 2 (8=2^3 is ok too).
10=2^1 2^2 +2^4 is a strictly increasing sum but not alternating.
4=2^1 2^1 +2^2 is alternating but not strictly increasing.
(author: prof Dan Shapiro of Ohio State University)
I don't know if I can prove this, but I can show how it works with any number. For an example I will use 105 which is
1101001 in binary
subtract 10000000 leaving 10111 (notice this changes all digits from 0 to 1 and 1 to 0 except the last)
add 100000 giving 1001 (again changing all but last)
subtract 10000 leaving 111
add 1000 giving 1
subtract 1 leaving 0
written in base 10 this is
105128 = 23
23 + 32 = 9
916 = 7
7+8 = 1
11=0
so 12832+168+1=105
I see the pattern. When the number is written in binary with a leading 0, use the power of each digits whose following digit is different.
I think I can work out a proof in a separate post later.

Posted by Jer
on 20050614 17:03:51 