A104895 -id:A104895 - 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

A065620 a(0)=0; thereafter a(2n) = 2a(n), a(2n+1) = -2a(n) + 1.

Original entry on oeis.org

0, 1, 2, -1, 4, -3, -2, 3, 8, -7, -6, 7, -4, 5, 6, -5, 16, -15, -14, 15, -12, 13, 14, -13, -8, 9, 10, -9, 12, -11, -10, 11, 32, -31, -30, 31, -28, 29, 30, -29, -24, 25, 26, -25, 28, -27, -26, 27, -16, 17, 18, -17, 20, -19, -18, 19, 24, -23, -22, 23, -20, 21, 22, -21, 64, -63, -62, 63, -60, 61, 62, -61, -56

Offset: 0

Marc LeBrun, Nov 07 2001

Reversing binary value of n: convert sum of powers of 2 in binary representation of n to alternating sum.

The alternation is applied only to the nonzero bits and does not depend on the exponent of 2. All integers have a unique reversing binary representation (see cited Knuth exercise for proof).

			11 = 1 + 2 + 8 -> 1 - 2 + 8 = 7 = a(11).

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

N. J. A. Sloane, Table of n, a(n) for n = 0..20000 (First 8192 terms from Reinhard Zumkeller)

Cf. A010060, A048724, A065621, A246159, A246160, A265263.

The negative of entry A104895.

import Data.List (transpose)
a065620 n = a065620_list !! n
a065620_list = 1 : concat (transpose [zs, map ((+ 1) . negate) zs])
               where zs = map (* 2) a065620_list
-- Reinhard Zumkeller, Mar 26 2014

f:=proc(n) option remember; if n=0 then 0 elif (n mod 2) = 0 then 2*f(n/2) else 1-2*f((n-1)/2); fi; end;
[seq(f(n),n=0..100)]; # N. J. A. Sloane, Apr 25 2018

a[0] = 0; a[n_]:= a[n]= If[OddQ[n], 1 - 2*a[(n-1)/2], 2*a[n/2]]; Array[a, 100, 0] (* Amiram Eldar, Sep 05 2023 *)

A065620(n,c=1)=sum(i=0,logint(n+!n,2),if(bittest(n,i),(-1)^c++<M. F. Hasler, Apr 16 2018

def a(n): return n if n<3 else 2*a(n/2) if n%2==0 else -2*a((n - 1)/2) + 1 # Indranil Ghosh, Jun 07 2017

def A065620(n):
    c, a, b = 0, -1, 1
    for j in bin(n)[-1:1:-1]:
        if int(j):
            c += (a:=-a)*b
        b <<= 1
    return c # Chai Wah Wu, Sep 19 2023

(definec (A065620 n) (cond ((zero? n) n) ((even? n) (* 2 (A065620 (/ n 2)))) (else (+ 1 (* -2 (A065620 (/ (- n 1) 2)))))))
;; using memoization-macro definec from IntSeq-library of Antti Karttunen, Aug 18 2014

a(n) = if n<2 then n else b+2*(1-2*b)*a((n-b)/2) where b is the least significant bit in n.
From Antti Karttunen, Aug 18 2014: (Start)
a(n) = A246160(n) - A246159(n).
a(A065621(n)) = n.
a(A048724(n)) = -n. (End)
a(n) = -A104895(n). - M. F. Hasler, Apr 16 2018
a(n) = (2*A265263(n) - n) * (2*A010060(n) - 1). - Alan Michael Gómez Calderón, Jul 01 2025

Formula fixed by Reinhard Zumkeller, Mar 26 2014
Extended to a(0) = 0 by M. F. Hasler, Apr 16 2018
Edited by N. J. A. Sloane, Apr 25 2018

A104894 Binary array, related to the Thue-Morse sequence A010060, read by downward antidiagonals.

Original entry on oeis.org

0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1

Offset: 0

Philippe Deléham, Apr 24 2005

			Row n consists of repetitions of the first 2^(n+1) terms of A010060:
.
 n\k| 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15  ...
---------------------------------------------------------
  0 | 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...
  1 | 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, ...
  2 | 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, ...
  3 | 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, ...
  4 | 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, ...
  5 | 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, ...
  6 | 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, ...
  7 | 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, ...
  ...
Columns written in base 10 (see Table 2 of reference) give 0, -1, -2, 1, -4, 3, 2, -3, -8, 7, 6, -7, 4, -5, -6, 5, ... (see A104895).

Paolo Xausa, Table of n, a(n) for n = 0..11324 (first 150 antidiagonals, flattened).
David Applegate, Benoit Cloitre, Philippe Deléham and N. J. A. Sloane, Sloping binary numbers: a new sequence related to the binary numbers [pdf, ps].

Cf. A010060, A104895.

Table[ThueMorse[Mod[n-k, 2^(k+1)]], {n, 0, 15}, {k, 0, n}] (* Paolo Xausa, Apr 04 2024 *)

T(n,k) = A010060(k mod 2^(n+1)). - Paolo Xausa, Apr 04 2024

a(48) = 0 removed by Paolo Xausa, Apr 04 2024

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

A065620 a(0)=0; thereafter a(2n) = 2a(n), a(2n+1) = -2a(n) + 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Python

Scheme

Formula

Extensions

A104894 Binary array, related to the Thue-Morse sequence A010060, read by downward antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions