A073122 - OEIS

%I #22 Nov 17 2024 15:41:16

%S 1,2,5,4,13,10,9,8,25,26,29,20,21,18,17,16,49,50,53,52,61,58,57,40,41,

%T 42,45,36,37,34,33,32,97,98,101,100,109,106,105,104,121,122,125,116,

%U 117,114,113,80,81,82,85,84,93,90,89,72,73,74,77,68,69,66,65,64,193

%N Minimal reversing binary representation of n. Converting sum of powers of 2 in binary representation of a(n) to alternating sum gives n. See A072339.

%C The minimal representation is unique. The number of powers of 2 can be either even or odd. Compare with A065621, in which the number of powers of 2 is odd. The Mathematica program computes the representation for numbers 1 to 2^m. a(0) = 0.

%C No term has odd part congruent to 3 modulo 4. - _Charlie Neder_, Oct 28 2018

%D 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 Clark Kimberling, <a href="/A073122/b073122.txt">Table of n, a(n) for n = 1..1000</a>

%F a(2n) = 2 * a(n). [Corrected by _Sean A. Irvine_, Nov 17 2024]

%F Express n as a sum of terms 2^x - 2^y, x > y, such that each term defines a run of 1's in n's binary expansion. Then a(n) is the sum of all 2^x + 2^y, with the exception that a term 2^(x+1) - 2^x at the end of a representation becomes 2^x. - _Charlie Neder_, Oct 28 2018

%e a(11) = 29 because 29 = 16 + 8 + 4 + 1 and 16 - 8 + 4 - 1 = 11.

%e a(100) = 164 because 100 in binary is 1100100. The two runs of ones correspond to 2^7 - 2^5 and 2^3 - 2^2, but since 2^3 - 2^2 is the last term of the representation, it can be replaced with 2^2. Therefore, a(100) = 2^7 + 2^5 + 2^2. - _Charlie Neder_, Oct 28 2018

%t 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=7; powers=Table[2^i, {i, 0, m}]; lst=Table[2m, {2^m}]; lst2=Table[0, {2^m}]; Do[t=NthSubset[i, powers]; len=Length[t]; st=sumit[t]; If[len<lst[[st]], lst[[st]]=len; lst2[[st]]=Plus@@t], {i, 2^(m+1)-1}]; lst2

%Y Cf. A065621, A072219, A072339, A256696.

%K easy,nice,nonn

%O 1,2

%A _T. D. Noe_, Jul 17 2002