|
Search: id:A072339
|
|
|
| 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. |
|
+0
3
|
|
| 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; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
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 this_sequence A038571 A008687 A080801
Adjacent sequences: A072336 A072337 A072338 this_sequence 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
|
|
|
Search completed in 0.002 seconds
|
