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)
(In reply to
re: Negabinary by Old Original Oskar!)
You are right if zero coefficents are disallowed. But (-2)^n does alternate and its sign can be stolen and given instead to the 1 or 0 coefficients of the negabinary number, so if 0 coefficients are allowed, then you get an alternating representation of the form
b_0*2^0 - b_1*2^1 + b_2*2^2 - ...
where the b_i are unique coefficients, 1 or 0. You can make a good case, however, that allowing 0's is a underhanded way to destroy the purity of alternatingness.
|
|
Posted by Richard
on 2005-06-15 01:48:53 |
re(2): Negabinary
