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

Author

Robert G. Wilson v, Jul 15 2002

Keywords

• nonn
• easy
• nice

Comments

The minimal representation is unique.

Examples

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

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

Crossrefs

Cf. A072219, A073122.

Programs

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

Formula

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

Extensions

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