A073122 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.

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, 42, 45, 36, 37, 34, 33, 32, 97, 98, 101, 100, 109, 106, 105, 104, 121, 122, 125, 116, 117, 114, 113, 80, 81, 82, 85, 84, 93, 90, 89, 72, 73, 74, 77, 68, 69, 66, 65, 64, 193

Offset: 1

Author

T. D. Noe, Jul 17 2002

Keywords

• easy
• nice
• nonn

Comments

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.

No term has odd part congruent to 3 modulo 4. - Charlie Neder, Oct 28 2018

Examples

			a(11) = 29 because 29 = 16 + 8 + 4 + 1 and 16 - 8 + 4 - 1 = 11.
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
		

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

• Clark Kimberling, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A065621, A072219, A072339, A256696.

Programs

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=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
				

Formula

a(2n) = 2 * a(n). [Corrected by Sean A. Irvine, Nov 17 2024]

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