A072339 Any number n can be written (in two ways, one with m even and one with m odd) in the form n = 2^k_1 - 2^k_2 + 2^k_3 - ... + 2^k_m where the signs alternate and k_1 > k_2 > k_3 > ... >k_m >= 0; sequence gives minimal value of m.

1, 1, 2, 1, 3, 2, 2, 1, 3, 3, 4, 2, 3, 2, 2, 1, 3, 3, 4, 3, 5, 4, 4, 2, 3, 3, 4, 2, 3, 2, 2, 1, 3, 3, 4, 3, 5, 4, 4, 3, 5, 5, 6, 4, 5, 4, 4, 2, 3, 3, 4, 3, 5, 4, 4, 2, 3, 3, 4, 2, 3, 2, 2, 1, 3, 3, 4, 3, 5, 4, 4, 3, 5, 5, 6, 4, 5, 4, 4, 3, 5, 5, 6, 5, 7, 6, 6, 4, 5, 5, 6, 4, 5, 4, 4, 2, 3, 3, 4, 3, 5, 4, 4, 3, 5

Offset

1,3

Comments

The minimal representation is unique.

References

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1981, Vol. 2 (Second Edition), p. 196, (exercise 4.1. Nr. 27)

Links

Michael De Vlieger, Table of n, a(n) for n = 1..16384

Formula

Conjecture: a(n)=1 if n=2^k, a(n)=a(2^k-i)+1 if 2^k<n+i<2^(k+1). - John W. Layman, Jul 18 2002

Example

a(6)=2 since 6=2^3-2^1 and 6 is not a power of two.

Mathematica

(* computes a(n) for n = 1 to 2^m *)
sumit[s_List] := Module[{i, ss=0}, Do[If[OddQ[i], ss+=s[[ -i]], ss-=s[[ -i]]], {i, Length[s]}]; ss];
m=8;
powers= Rest@ Subsets[Table[2^i, {i, 0, m}]];
lst=Table[2m, {2^m}];
Do[t = powers[[i]]; lst[[sumit[t]]]=Min[lst[[sumit[t]]], Length[t]], {i, 2^(m+1)-1}];
lst

Crossrefs

Cf. A072219, A073122.

Sequence in context: A126303 A306467 A157810 * A342507 A261337 A374998

Adjacent sequences: A072336 A072337 A072338 * A072340 A072341 A072342

Keyword

nonn,easy,nice

Author

Robert G. Wilson v, Jul 15 2002

Extensions

Extended and edited by John W. Layman and T. D. Noe, Jul 18 2002

Status

approved