|
|
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.
|
|
4
|
|
|
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;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|