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

A268718 Permutation of natural numbers: a(0) = 0, a(n) = 1 + A003188(A006068(n)-1), where A003188 is binary Gray code and A006068 is its inverse.

Original entry on oeis.org

0, 1, 4, 2, 6, 8, 3, 7, 10, 12, 15, 11, 5, 13, 16, 14, 18, 20, 23, 19, 29, 21, 24, 22, 9, 25, 28, 26, 30, 32, 27, 31, 34, 36, 39, 35, 45, 37, 40, 38, 57, 41, 44, 42, 46, 48, 43, 47, 17, 49, 52, 50, 54, 56, 51, 55, 58, 60, 63, 59, 53, 61, 64, 62, 66, 68, 71, 67, 77, 69, 72, 70, 89, 73, 76, 74, 78, 80, 75, 79, 113, 81

Offset: 0

Antti Karttunen, Feb 12 2016

nonn

Antti Karttunen, Table of n, a(n) for n = 0..8191
Index entries for sequences that are permutations of the natural numbers

Inverse: A268717.
Cf. A003188, A006068, A010060, A105081, A128309, A166519, A171977, A277822.
Row 1 of array A268830.
Cf. A092246 (fixed points).
Cf. A268818 ("square" of this permutation).
Cf. A268822 ("shifted square"), A268824 ("shifted cube") and also A268826, A268828 and A268832 (higher "shifted powers").

{0}~Join~Table[1 + BitXor[#, Floor[#/2]] &[BitXor @@ Table[Floor[n/2^m], {m, 0, Floor[Log[2, n]]}] - 1], {n, 81}] (* Michael De Vlieger, Feb 29 2016, after Jean-François Alcover at A006068 and Robert G. Wilson v at A003188 *)

a003188(n)=bitxor(n, n>>1);
a006068(n)= {
    my( s=1, ns );
    while ( 1,
        ns = n >> s;
        if ( 0==ns, break() );
        n = bitxor(n, ns);
        s <<= 1;
    );
    return (n);
} \\ by Joerg Arndt
a(n)=if(n==0, 0, 1 + a003188(a006068(n) - 1)); \\ Indranil Ghosh, Jun 07 2017

def a003188(n): return n^(n>>1)
def a006068(n):
    s=1
    while True:
        ns=n>>s
        if ns==0: break
        n=n^ns
        s<<=1
    return n
def a(n): return 0 if n==0 else 1 + a003188(a006068(n) - 1) # Indranil Ghosh, Jun 07 2017

(define (A268718 n) (if (zero? n) n (A105081 (A006068 n))))

a(0) = 0, and for n >= 1, a(n) = A105081(A006068(n)) = 1 + A003188(A006068(n)-1).
Other identities. For all n >= 1:
a(A128309(n)) = A128309(n)+2. [Maps any even odious number to that number + 2.]
From Alan Michael Gómez Calderón, May 29 2025: (Start)
a(n) - 1 = A268717(n+1) XOR (A171977(n)+1) for n >= 1;
a(2*n-1) - 1 = (2-A010060(n-1)) XOR (A166519(n-1)-1) for n >= 1;
a(2*n) - 1 = (a(2*(n+1)-1)-1) XOR 2^A277822(n) for n >= 1. (End)

A066194 A permutation of the integers (a fractal sequence): a(n) = A006068(n-1) + 1.

Original entry on oeis.org

1, 2, 4, 3, 8, 7, 5, 6, 16, 15, 13, 14, 9, 10, 12, 11, 32, 31, 29, 30, 25, 26, 28, 27, 17, 18, 20, 19, 24, 23, 21, 22, 64, 63, 61, 62, 57, 58, 60, 59, 49, 50, 52, 51, 56, 55, 53, 54, 33, 34, 36, 35, 40, 39, 37, 38, 48, 47, 45, 46, 41, 42, 44, 43, 128, 127, 125, 126, 121, 122

Offset: 1

Wouter Meeussen, Dec 15 2001

With an initial zero, inverse of the Gray Code (A003188). See also A006068. - Robert G. Wilson v, Jun 22 2014

I suspect the above comment refers to function A105081(n) = 1 + A003188(n - 1), n >= 1. - Antti Karttunen, Feb 15 2016

			Third nesting gives {1,2,4,3, 8,7,5,6} by means of joining the lists {1,2,4,3} = second nesting and {8,7,6,5} permuted by {1,2,4,3} giving {8,7,5,6}.

Antti Karttunen, Table of n, a(n) for n = 1..8192 (first 1024 terms from Robert G. Wilson v)
Index entries for sequences that are permutations of the natural numbers

Inverse: A105081.

Cf. A003188, A006068, A268717.

Nest[ Join[ #, (Length[ #] + Range[ Length[ #], 1, -1 ])[[ # ]]] &, {1}, 7 ]
GrayCode[n_] := BitXor[n, Floor[n/2]]; t = Array[ GrayCode, 1000, 0]; Table[ Position[ t, n], {n, 0, 100}] // Flatten (* Robert G. Wilson v, Jun 22 2014 *)

def A066194(n):
    k, m = n-1, n-1>>1
    while m > 0:
        k ^= m
        m >>= 1
    return k+1 # Chai Wah Wu, Jul 01 2022

(define (A066194 n) (+ 1 (A006068 (- n 1)))) ;; Antti Karttunen, Feb 14 2016

a(n) = A006068(n-1) + 1, n >= 1. - Philippe Deléham, Apr 29 2005
a(n) = A006068(A268717(n)), composition of related permutations. - Antti Karttunen, Feb 14 2016
a(n) = 1 + Sum_{j=1..n-1} (1/6)*(-3 + (-1)^A007814(j) + 2^(A007814(j) + 3))*(-1)^(A000120(j) + 1). - John Erickson, Oct 18 2018

Deléham's formula added to the name by Antti Karttunen, Feb 14 2016

A182310 a(0)=0, a(n+1) = (a(n) XOR floor(a(n)/2)) + 1, where XOR is the bitwise exclusive-or operator.

Original entry on oeis.org

0, 1, 2, 4, 7, 5, 8, 13, 12, 11, 15, 9, 14, 10, 16, 25, 22, 30, 18, 28, 19, 27, 23, 29, 20, 31, 17, 26, 24, 21, 32, 49, 42, 64, 97, 82, 124, 67, 99, 83, 123, 71, 101, 88, 117, 80, 121, 70, 102, 86, 126, 66, 100, 87, 125, 68, 103, 85, 128, 193, 162, 244, 143

Offset: 0

Alex Ratushnyak, Apr 24 2012

As n -> infinity, a(n) -> infinity.

			a(5) = ( a(4) XOR floor(a(4)/2) ) + 1 = (7 XOR 3) + 1 = 4+1 = 5.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Eric Weisstein's World of Mathematics, XOR
Wikipedia, Bitwise operation XOR

Cf. A105081, A182417.

#include 
#include 
typedef unsigned long long ULL;
int main(int argc, char **argv) {
  ULL a=0, i=0, p, prev;
  while(1) {
    prev = a,   a = (a^(a/2)) + 1;
  #if 0  // "if 1" to print indices of 2^x
    ++i;
    if ( (i & ((1<<30)-1))==0 )  printf(".");
    if ((a^prev) > prev)
       printf("\n%llu at %llu,  log2: %llu ", a, i, (ULL)(100.0*log2(i)));
  #else
    printf("%llu, ", prev);
  #endif
    // Test reversion:
    p=a-1;
    ULL t=p/2;
    while (t)  p^=t, t/=2;
    if (p!=prev) printf("Reversion failed!"), exit(1);
  }
  return 0;
}  // from Alex Ratushnyak, Apr 26 2012

import Data.Bits (xor)
a182310 n = a182310_list !! n
a182310_list = 0 : map (+ 1)
   (zipWith xor a182310_list $ map (`div` 2) a182310_list) :: [Integer]
-- Reinhard Zumkeller, Apr 25 2012

a:= proc(n) option remember; `if`(n=0, 0, 1+
     (t-> Bits[Xor](t, iquo(t, 2)))(a(n-1)))
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Jun 29 2021

NestList[BitXor[#,Floor[#/2]]+1&,0,70] (* Harvey P. Dale, Apr 18 2015 *)

terms(n) = my(x=0, i=0); while(i < n, print1(x, ", "); x=bitxor(x, floor(x/2)) + 1; i++)
/* Print initial 200 terms as follows: */
terms(200) \\ Felix Fröhlich, Jun 29 2021

a(n) = A105081(a(n-1)+1). - Jon Maiga, Jun 27 2021

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

A268718 Permutation of natural numbers: a(0) = 0, a(n) = 1 + A003188(A006068(n)-1), where A003188 is binary Gray code and A006068 is its inverse.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Python

Scheme

Formula

A066194 A permutation of the integers (a fractal sequence): a(n) = A006068(n-1) + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Scheme

Formula

Extensions

A182310 a(0)=0, a(n+1) = (a(n) XOR floor(a(n)/2)) + 1, where XOR is the bitwise exclusive-or operator.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Haskell

Maple

Mathematica

PARI

Formula