A073122 -id:A073122 - cp's OEIS frontend

A065621 Reversing binary representation of n. Converting sum of powers of 2 in binary representation of a(n) to alternating sum gives n.

1, 2, 7, 4, 13, 14, 11, 8, 25, 26, 31, 28, 21, 22, 19, 16, 49, 50, 55, 52, 61, 62, 59, 56, 41, 42, 47, 44, 37, 38, 35, 32, 97, 98, 103, 100, 109, 110, 107, 104, 121, 122, 127, 124, 117, 118, 115, 112, 81, 82, 87, 84, 93, 94, 91, 88, 73, 74, 79, 76, 69, 70, 67, 64, 193

Offset: 1

Marc LeBrun, Nov 07 2001

a(0)=0. The alternation is applied only to the nonzero bits and does not depend on the exponent of two. All integers have a unique reversing binary representation (see cited exercise for proof). Complement of A048724.
A permutation of the "odious" numbers A000069.
Write n-1 and 2n-1 in binary and add them mod 2; example: n = 6, n-1 = 5 = 101 in binary, 2n-1 = 11 = 1011 in binary and their sum is 1110 = 14, so a(6) = 14. - Philippe Deléham, Apr 29 2005
As already pointed out, this is a permutation of the odious numbers A000069 and A010060(A000069(n)) = 1, so A010060(a(n)) = 1; and A010060(A048724(n)) = 0. - Philippe Deléham, Apr 29 2005. Also a(n) = A000069(A003188(n - 1)).

			a(5) = 13 = 8 + 4 + 1 -> 8 - 4 + 1 = 5.

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1969, Vol. 2, p. 178, (exercise 4.1. Nr. 27)

Reinhard Zumkeller, Table of n, a(n) for n = 1..8192

Cf. A003188, A065620, A048724, A072219, A073122.
Differs from A115857 for the first time at n=19, where a(19)=55, while A115857(19)=23. Cf. A104895, A115872, A114389, A114390, A105081.
Cf. A245471.

import Data.Bits (xor, (.&.))
a065621 n = n `xor` 2 * (n - n .&. negate n) :: Integer
-- Reinhard Zumkeller, Mar 26 2014

f[n_] := BitXor[n, 2 n + 1]; Array[f, 60, 0] (* Robert G. Wilson v, Jun 09 2010 *)

a(n)=if(n<2,1,if(n%2==0,2*a(n/2),2*a((n+1)/2)-2*(-1)^((n-1)/2)+1))

def a(n): return n^(2*(n - (n & -n))) # Indranil Ghosh, Jun 04 2017

def A065621(n): return n^ (n&~-n)<<1 # Chai Wah Wu, Jun 29 2022

a(n) = if n=0 or n=1 then n else b+2*a(b+(1-2*b)*n)/2) where b is the least significant bit in n.
a(n) = n XOR 2 (n - (n AND -n)).
a(1) = 1, a(2n) = 2*a(n), a(2n+1) = 2*a(n+1) - 2(-1)^n + 1. - Ralf Stephan, Aug 20 2003
a(n) = A048724(n-1) - (-1)^n. - Ralf Stephan, Sep 10 2003
a(n) = Sum_{k=0..n} (1-(-1)^round(-n/2^k))/2*2^k. - Benoit Cloitre, Apr 27 2005
Closely related to Gray codes in another way: a(n) = 2 * A003188(n-1) + (n mod 2); a(n) = 4 * A003188((n-1) div 2) + (n mod 4). - Matt Erbst (matt(AT)erbst.org), Jul 18 2006 [corrected by Peter Munn, Jan 30 2021]
a(n) = n XOR 2(n AND NOT -n). - Chai Wah Wu, Jun 29 2022
a(n) = A003188(2n-1). - Friedjof Tellkamp, Jan 18 2024

More terms from Ralf Stephan, Sep 08 2003

A256696 R(k), the minimal alternating binary representation of k, concatenated for k = 0, 1, 2,....

Original entry on oeis.org

0, 1, 2, 4, -1, 4, 8, -4, 1, 8, -2, 8, -1, 8, 16, -8, 1, 16, -8, 2, 16, -8, 4, -1, 16, -4, 16, -4, 1, 16, -2, 16, -1, 16, 32, -16, 1, 32, -16, 2, 32, -16, 4, -1, 32, -16, 4, 32, -16, 8, -4, 1, 32, -16, 8, -2, 32, -16, 8, -1, 32, -8, 32, -8, 1, 32, -8, 2, 32

Offset: 0

Clark Kimberling, Apr 09 2015

Suppose that b = (b(0), b(1), ... ) is an increasing sequence of positive integers satisfying b(0) = 1 and b(n+1) <= 2*b(n) for n >= 0.  Let B(n) be the least b(m) >= n.  Let R(0) = 1, and for n > 0, let R(n) = B(n) - R(B(n) - n).  The resulting sum of the form R(n) = B(n) - B(m(1)) + B(m(2)) - ... + ((-1)^k)*B(k) is the minimal alternating b-representation of n.  The sum B(n) + B(m(2)) + ... is the positive part of R(n), and the sum B(m(1)) + B(m(3)) + ... , the nonpositive part of R(n).  The number ((-1)^k)*B(k) is the trace of n.
If b(n) = 2^n, the sum R(n) is the minimal alternating binary representation of n.
A055975 = trace of n, for n >= 1.
A091072 gives the numbers having positive trace.
A091067 gives the numbers having negative trace.
A072339 = number of terms in R(n).
A073122 = sum of absolute values of the terms in R(n).

			R(0) = 0
R(1) = 1
R(2) = 2
R(3) = 4 - 1
R(4) = 4
R(9) = 8 - 4 + 1
R(11) = 16 - 8 + 4 - 1

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1981, Vol. 2 (2nd ed.), p. 196, Exercise 27.

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

Cf. A000079, A256655 (Fibonacci based), A055975, A091072, A091067, A072339, A073122, A256701, A256702.

z = 100; b[n_] := 2^n; bb = Table[b[n], {n, 0, 40}];
s[n_] := Table[b[n + 1], {k, 1, b[n]}];
h[0] = {1}; h[n_] := Join[h[n - 1], s[n - 1]];
g = h[10]; r[0] = {0};
r[n_] := If[MemberQ[bb, n], {n}, Join[{g[[n]]}, -r[g[[n]] - n]]]
u = Flatten[Table[r[n], {n, 0, z}]]

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.

Original entry on oeis.org

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

Offset: 1

Robert G. Wilson v, Jul 15 2002

The minimal representation is unique.

			a(6)=2 since 6=2^3-2^1 and 6 is not a power of two.

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1981, Vol. 2 (Second Edition), p. 196, (exercise 4.1. Nr. 27)

Michael De Vlieger, Table of n, a(n) for n = 1..16384

Cf. A072219, A073122.

(* 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

Conjecture: a(n)=1 if n=2^k, a(n)=a(2^k-i)+1 if 2^kJohn W. Layman, Jul 18 2002

Extended and edited by John W. Layman and T. D. Noe, Jul 18 2002

A256701 Positive part of the minimal alternating binary representation of n (defined at A245596).

Original entry on oeis.org

1, 2, 4, 4, 9, 8, 8, 8, 17, 18, 20, 16, 17, 16, 16, 16, 33, 34, 36, 36, 41, 40, 40, 32, 33, 34, 36, 32, 33, 32, 32, 32, 65, 66, 68, 68, 73, 72, 72, 72, 81, 82, 84, 80, 81, 80, 80, 64, 65, 66, 68, 68, 73, 72, 72, 64, 65, 66, 68, 64, 65, 64, 64, 64, 129, 130

Offset: 1

Clark Kimberling, Apr 09 2015

			R(1) = 1; positive part 1, nonpositive part 0
R(2) = 2; positive part 2, nonpositive part 0
R(3) = 4 - 1; positive part 4, nonpositive part 1
R(11) = 16 - 8 + 4 - 1; positive part 16+4 = 20; nonpositive part 8 + 1 = 9

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

Cf. A245596, A073122, A256702.

b[n_] := 2^n; bb = Table[b[n], {n, 0, 40}];
s[n_] := Table[b[n + 1], {k, 1, b[n]}];
h[0] = {1}; h[n_] := Join[h[n - 1], s[n - 1]];
g = h[10]; Take[g, 100]; r[0] = {0};
r[n_] := If[MemberQ[bb, n], {n}, Join[{g[[n]]}, -r[g[[n]] - n]]]
Table[Total[Abs[r[n]]], {n, 1, 100}] (* A073122 *)
u = Table[Total[(Abs[r[n]] + r[n])/2], {n, 1, 100}]  (* A256701 *)
v = Table[Total[(Abs[r[n]] - r[n])/2], {n, 1, 100}]  (* A256702 *)

A256701(n) - A256702(n) = n.

A256702 Nonpositive part of the minimal alternating binary representation of n (defined at A256696).

Original entry on oeis.org

0, 0, 1, 0, 4, 2, 1, 0, 8, 8, 9, 4, 4, 2, 1, 0, 16, 16, 17, 16, 20, 18, 17, 8, 8, 8, 9, 4, 4, 2, 1, 0, 32, 32, 33, 32, 36, 34, 33, 32, 40, 40, 41, 36, 36, 34, 33, 16, 16, 16, 17, 16, 20, 18, 17, 8, 8, 8, 9, 4, 4, 2, 1, 0, 64, 64, 65, 64, 68, 66, 65, 64, 72

Offset: 1

Clark Kimberling, Apr 09 2015

			R(1) = 1; positive part 1, nonpositive part 0.
R(2) = 2; positive part 2, nonpositive part 0.
R(3) = 4 - 1; positive part 4, nonpositive part 1.
R(11) = 16 - 8 + 4 - 1; positive part 16 + 4 = 20; nonpositive part 8 + 1 = 9.

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

Cf. A256696, A073122, A256701.

b[n_] := 2^n; bb = Table[b[n], {n, 0, 40}];
s[n_] := Table[b[n + 1], {k, 1, b[n]}];
h[0] = {1}; h[n_] := Join[h[n - 1], s[n - 1]];
g = h[10]; Take[g, 100]; r[0] = {0};
r[n_] := If[MemberQ[bb, n], {n}, Join[{g[[n]]}, -r[g[[n]] - n]]]
Table[Total[Abs[r[n]]], {n, 1, 100}] (* A073122 *)
u = Table[Total[(Abs[r[n]] + r[n])/2], {n, 1, 100}]  (* A256701 *)
v = Table[Total[(Abs[r[n]] - r[n])/2], {n, 1, 100}]  (* A256702 *)

A256701(n) - A256702(n) = n.

cp's OEIS Frontend

A065621 Reversing binary representation of n. Converting sum of powers of 2 in binary representation of a(n) to alternating sum gives n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Python

Formula

Extensions

A256696 R(k), the minimal alternating binary representation of k, concatenated for k = 0, 1, 2,....

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A256701 Positive part of the minimal alternating binary representation of n (defined at A245596).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A256702 Nonpositive part of the minimal alternating binary representation of n (defined at A256696).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula