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

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

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice
• look
• hear

Comments

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

Examples

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

References

• 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).

Links

• 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

Crossrefs

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.

Programs

Haskell

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

Maple

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

Mathematica

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

PARI

{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 */

PARI

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

Python

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

R

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

Formula

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

Extensions

More terms from Henry Bottomley, Jan 10 2001