|
| |
|
|
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.
|
|
2
| |
|
|
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
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,3
|
|
|
COMMENTS
| The minimal representation is unique.
The Mathematica program computes a(n) for n = 1 to 2^m.
|
|
|
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)
|
|
|
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
| Needs["DiscreteMath`Combinatorica`"]; sumit[s_List] := Module[{i, ss=0}, Do[If[OddQ[i], ss+=s[[ -i]], ss-=s[[ -i]]], {i, Length[s]}]; ss]; m=8; powers=Table[2^i, {i, 0, m}]; lst=Table[2m, {2^m}]; Do[t=NthSubset[i, powers]; lst[[sumit[t]]]=Min[lst[[sumit[t]]], Length[t]], {i, 2^(m+1)-1}]; lst
|
|
|
CROSSREFS
| Cf. A072219, A073122.
Sequence in context: A109082 A126303 A157810 * A175548 A038571 A008687
Adjacent sequences: A072336 A072337 A072338 * A072340 A072341 A072342
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| Robert G. Wilson v (rgwv(AT)rgwv.com), Jul 15 2002
|
|
|
EXTENSIONS
| Extended and edited by John W. Layman (layman(AT)math.vt.edu) and T. D. Noe (noe(AT)sspectra.com), Jul 18 2002
|
| |
|
|
