cp's OEIS Frontend

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.

%I A072339 #17 Feb 25 2023 09:39:40
%S A072339 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,
%T A072339 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,
%U A072339 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
%N 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.
%C A072339 The minimal representation is unique.
%D A072339 D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1981, Vol. 2 (Second Edition), p. 196, (exercise 4.1. Nr. 27)
%H A072339 Michael De Vlieger, <a href="/A072339/b072339.txt">Table of n, a(n) for n = 1..16384</a>
%F A072339 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
%e A072339 a(6)=2 since 6=2^3-2^1 and 6 is not a power of two.
%t A072339 (* computes a(n) for n = 1 to 2^m *)
%t A072339 sumit[s_List] := Module[{i, ss=0}, Do[If[OddQ[i], ss+=s[[ -i]], ss-=s[[ -i]]], {i, Length[s]}]; ss];
%t A072339 m=8;
%t A072339 powers= Rest@ Subsets[Table[2^i, {i, 0, m}]];
%t A072339 lst=Table[2m, {2^m}];
%t A072339 Do[t = powers[[i]]; lst[[sumit[t]]]=Min[lst[[sumit[t]]], Length[t]], {i, 2^(m+1)-1}];
%t A072339 lst
%Y A072339 Cf. A072219, A073122.
%K A072339 nonn,easy,nice
%O A072339 1,3
%A A072339 _Robert G. Wilson v_, Jul 15 2002
%E A072339 Extended and edited by _John W. Layman_ and _T. D. Noe_, Jul 18 2002