A265263 -id:A265263 - cp's OEIS frontend

A377440 Lexicographically latest sequence of nonnegative integers such that for any n >= 0, A265263(n) = A265263(a(n)).

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

Offset: 0

Rémy Sigrist, Oct 28 2024

This sequence is a self-inverse permutation of the nonnegative integers that preserves the binary length.

			The first terms are:
  n   a(n)  A265263(n)  A265263(a(n))
  --  ----  ----------  -------------
   0     0           0              0
   1     1           1              1
   2     3           2              2
   3     2           2              2
   4     6           4              4
   5     5           4              4
   6     4           4              4
   7     7           5              5
   8    12           8              8
   9    10           8              8
  10     9           8              8
  11    13           9              9
  12     8           8              8
  13    11           9              9
  14    15          10             10
  15    14          10             10

Rémy Sigrist, Table of n, a(n) for n = 0..8191
Rémy Sigrist, PARI program
Index entries for sequences that are permutations of the natural numbers

Cf. A265263, A367307.

PARI
```
\\ See Links section.
```

A006068 a(n) is Gray-coded into n.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

Equivalently, if binary expansion of n has m bits (say), compute derivative of n (A038554), getting sequence n' of length m-1; sort on n'.
Inverse of sequence A003188 considered as a permutation of the nonnegative integers, i.e., a(A003188(n)) = n = A003188(a(n)). - Howard A. Landman, Sep 25 2001
The sequence exhibits glide reflections that grow fractally. These show up well on the scatterplot, also audibly using the "listen" link. - Peter Munn, Aug 18 2019
Each bit at bit-index k (counted from the right hand end, with the least significant bit having bit-index 0) in the binary representation of a(n) is the parity of the number of 1's among the bits of the binary representation of n that have a bit-index of k or higher. - Frederik P.J. Vandecasteele, May 26 2025

			The first few values of n' are -,-,1,0,10,11,01,00,100,101,111,110,010,011,001,000,... (for n=0..15) and to put these in lexicographic order we must take n in the order 0,1,3,2,7,6,4,5,15,14,12,13,8,9,11,10,...

M. Gardner, Mathematical Games, Sci. Amer. Vol. 227 (No. 2, Feb. 1972), p. 107.
M. Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 15.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..1023
Joerg Arndt, Matters Computational (The Fxtbook), section 1.16 Gray code, C code inverse_gray_code() with "version 3" giving the PARI code here.
Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, Finding structure in sequences of real numbers via graph theory: a problem list, arXiv:2012.04625, Dec 08, 2020
Eric Rowland and Reem Yassawi, Profinite automata, arXiv:1403.7659 [math.DS], 2014. See p. 22.
Paul Tarau, Isomorphic Data Encodings and their Generalization to Hylomorphisms on Hereditarily Finite Data Types; see also alternate link.
Index entries for sequences that are permutations of the natural numbers

Cf. A038554, A005811, A003188, A014550, A003100, A265263, A377404.
Cf. A054429, A180200. - Reinhard Zumkeller, Aug 15 2010
Cf. A000079, A055975 (first differences), A209281 (binary weight).
A003987, A010060 are used to express relationship between terms of this sequence.

a006068 n = foldl xor 0 $
                  map (div n) $ takeWhile (<= n) a000079_list :: Integer
-- Reinhard Zumkeller, Apr 28 2012

a:= proc(n) option remember; `if`(n<2, n,
      Bits[Xor](n, a(iquo(n, 2))))
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Apr 17 2018

a[n_] := BitXor @@ Table[Floor[n/2^m], {m, 0, Floor[Log[2, n]]}]; a[0]=0; Table[a[n], {n, 0, 69}] (* Jean-François Alcover, Jul 19 2012, after Paul D. Hanna *)
Table[Fold[BitXor, n, Quotient[n, 2^Range[BitLength[n] - 1]]], {n, 0, 70}] (* Jan Mangaldan, Mar 20 2013 *)

{a(n)=local(B=n);for(k=1,floor(log(n+1)/log(2)),B=bitxor(B,n\2^k));B} /* Paul D. Hanna, Jan 18 2012 */

/* the following routine needs only O(log_2(n)) operations */
a(n)= {
    my( s=1, ns );
    while ( 1,
        ns = n >> s;
        if ( 0==ns, break() );
        n = bitxor(n, ns);
        s <<= 1;
    );
    return ( n );
} /* Joerg Arndt, Jul 19 2012 */

def a(n):
    s=1
    while True:
        ns=n>>s
        if ns==0: break
        n=n^ns
        s<<=1
    return n
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 07 2017, after PARI code by Joerg Arndt

nmax <- 63 # by choice
a <- vector()
for(n in 1:nmax){
  ones <- which(as.integer(intToBits(n)) == 1)
  nbit <- as.integer(intToBits(n))[1:tail(ones, n = 1)]
  level <- 0; anbit <- nbit; anbit.s <- nbit
  while(sum(anbit.s) > 0){
    s <- 2^level; if(s > length(anbit.s)) break
    anbit.s <- c(anbit[-(1:s)], rep(0,s))
    anbit <- bitwXor(anbit, anbit.s)
    level <- level + 1
  }
  a <- c(a, sum(anbit*2^(0:(length(anbit) - 1))))
}
(a <- c(0,a))
# Yosu Yurramendi, Oct 12 2021, after PARI code by Joerg Arndt

a(n) = 2*a(ceiling((n+1)/2)) + A010060(n-1). If 3*2^(k-1) < n <= 2^(k+1), a(n) = 2^(k+1) - 1 - a(n-2^k); if 2^(k+1) < n <= 3*2^k, a(n) = a(n-2^k) + 2^k. - Henry Bottomley, Jan 10 2001
a(n) = n XOR [n/2] XOR [n/4] XOR [n/8] ... XOR [n/2^m] where m = [log(n)/log(2)] (for n>0) and [x] is integer floor of x. - Paul D. Hanna, Jun 04 2002
a(n) XOR [a(n)/2] = n. - Paul D. Hanna, Jan 18 2012
A066194(n) = a(n-1) + 1, n>=1. - Philippe Deléham, Apr 29 2005
a(n) = if n<2 then n else 2*m + (n mod 2 + m mod 2) mod 2, with m=a(floor(n/2)). - Reinhard Zumkeller, Aug 10 2010
a(n XOR m) = a(n) XOR a(m), where XOR is the bitwise exclusive-or operator, A003987. - Peter Munn, Dec 14 2019
a(0) = 0. For all n >= 0 if a(n) is even a(2*n) = 2*a(n), a(2*n+1) = 2*a(n)+1, else a(2*n) = 2*a(n)+1, a(2*n+1) = 2*a(n). - Yosu Yurramendi, Oct 12 2021
Conjecture: a(n) = a(A053645(A063946(n))) + A053644(n) for n > 0 with a(0) = 0. - Mikhail Kurkov, Sep 09 2023
a(n) = 2*A265263(n) - 2*A377404(n) - A010060(n). - Alan Michael Gómez Calderón, Jun 26 2025

More terms from Henry Bottomley, Jan 10 2001

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

A377404 In the binary expansion of n, replace the first, third, fifth, etc. 1's by 0's.

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 2, 2, 0, 1, 2, 2, 4, 4, 4, 5, 0, 1, 2, 2, 4, 4, 4, 5, 8, 8, 8, 9, 8, 9, 10, 10, 0, 1, 2, 2, 4, 4, 4, 5, 8, 8, 8, 9, 8, 9, 10, 10, 16, 16, 16, 17, 16, 17, 18, 18, 16, 17, 18, 18, 20, 20, 20, 21, 0, 1, 2, 2, 4, 4, 4, 5, 8, 8, 8, 9, 8, 9, 10, 10

Offset: 0

Rémy Sigrist, Oct 28 2024

Each 1 in the binary expansion of n appears either in a(n) or in A265263(n).

			The first terms, in decimal and in binary, are:
  n   a(n)  bin(n)  bin(a(n))
  --  ----  ------  ---------
   0     0       0          0
   1     0       1          0
   2     0      10          0
   3     1      11          1
   4     0     100          0
   5     1     101          1
   6     2     110         10
   7     2     111         10
   8     0    1000          0
   9     1    1001          1
  10     2    1010         10
  11     2    1011         10
  12     4    1100        100
  13     4    1101        100
  14     4    1110        100
  15     5    1111        101

Rémy Sigrist, Table of n, a(n) for n = 0..8192
Index entries for sequences related to binary expansion of n

Cf. A000120, A265263.

a(n) = { my (b = binary(n), h = 0); for (i = 1, #b, if (b[i] && h++%2==1, b[i]
= 0;);); fromdigits(b, 2); }

a(n) = n - A265263(n).
a(2*n) = 2*a(n).
A000120(a(n)) = floor(A000120(n)/2).

cp's OEIS Frontend

A377440 Lexicographically latest sequence of nonnegative integers such that for any n >= 0, A265263(n) = A265263(a(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A006068 a(n) is Gray-coded into n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

R

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

A377404 In the binary expansion of n, replace the first, third, fifth, etc. 1's by 0's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula