A003188 Decimal equivalent of Gray code for n. (Formerly M2250)

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

Offset

0,3

Comments

Inverse of sequence A006068 considered as a permutation of the nonnegative integers, i.e., A006068(A003188(n)) = n = A003188(A006068(n)). - Howard A. Landman, Sep 25 2001

Restricts to a permutation of each {2^(i - 1) .. 2^i - 1}. - Jason Kimberley, Apr 02 2012

a(n) mod 2 = floor(((n + 1) mod 4) / 2), see also A021913. - Reinhard Zumkeller, Apr 28 2012

Invented by Emile Baudot (1845-1903), originally called a "cyclic-permuted" code. Gray codes are named after Frank Gray, who patented their use for shaft encoders in 1953. [F. Gray, "Pulse Code Communication", U.S. Patent 2,632,058, March 17, 1953.] - Robert G. Wilson v, Jun 22 2014

For n >= 2, let G_n be the graph whose vertices are labeled as 0,1,...,2^n-1, and two vertices are adjacent if and only if their binary expansions differ in exactly one bit, then a(0),a(1),...,a(2^n-1),a(0) is a Hamilton cycle in G_n. - Jianing Song, Jun 01 2022

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

Indranil Ghosh, Table of n, a(n) for n = 0..32767 (first 1001 terms from N. J. A. Sloane)

M. W. Bunder, K. P. Tognetti, and G. E. Wheeler, On binary reflected Gray codes and functions, Discr. Math., 308 (2008), 1690-1700.

Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.

Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.

Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 39.

P. Mathonet, M. Rigo, M. Stipulanti and N. Zénaïdi, On digital sequences associated with Pascal's triangle, arXiv:2201.06636 [math.NT], 2022.

J. A. Oteo and J. Ros, A Fractal Set from the Binary Reflected Gray Code, J. Phys. A: Math Gen. 38 (2005) 8935-8949.

Ed Pegg, Jr., Sequence Pictures, Math Games column, Dec 08 2003.

Ed Pegg, Jr., Sequence Pictures, Math Games column, Dec 08 2003 [Cached copy, with permission (pdf only)]

Ralf Stephan, Some divide-and-conquer sequences ...

Ralf Stephan, Table of generating functions

Paul Tarau, Isomorphic Data Encodings and their Generalization to Hylomorphisms on Hereditarily Finite Data Types

Pierluigi Vellucci and Alberto Maria Bersani, Ordering of nested square roots of 2 according to Gray code, arXiv:1604.00222 [math.NT], 2016.

Index entries for sequences that are permutations of the natural numbers

Formula

a(n) = 2*a(floor(n/2)) + A021913(n - 1). - Henry Bottomley, Apr 05 2001

a(n) = n XOR floor(n/2), where XOR is the binary exclusive OR operator. - Paul D. Hanna, Jun 04 2002

G.f.: (1/(1-x)) * Sum_{k>=0} 2^k*x^2^k/(1 + x^2^(k+1)). - Ralf Stephan, May 06 2003

a(0) = 0, a(2n) = 2a(n) + [n odd], a(2n + 1) = 2a(n) + [n even]. - Ralf Stephan, Oct 20 2003

a(0) = 0, a(n) = 2 a(floor(n/2)) + mod(floor((n + 1)/2), 2).

a(n) = Sum_{k=1..n} 2^A007814(k) * (-1)^((k/2^A007814(k) - 1)/2). - Ralf Stephan, Oct 29 2003

a(0) = 0, a(n + 1) = a(n) XOR 2^A007814(n) - Jaume Simon Gispert (jaume(AT)nuem.com), Sep 11 2004

Inverse of sequence A006068. - Philippe Deléham, Apr 29 2005

a(n) = a(n-1) XOR A006519(n). - Franklin T. Adams-Watters, Jul 18 2011

Example

For n = 13, the binary reflected Gray code representation of n is '1011' and 1011_2 = 11_10. So, a(13) = 11. - Indranil Ghosh, Jan 23 2017

Maple

with(combinat); graycode(6); # to produce first 64 terms
printf(cat(` %.6d`$64), op(map(convert, graycode(6), binary))); lprint(); # to produce binary strings
# alternative:
read("transforms"):
A003188 := proc(n)
    XORnos(n, floor(n/2)) ;
end proc: # R. J. Mathar, Mar 09 2015
# another Maple program:
a:= n-> Bits[Xor](n, iquo(n, 2)):
seq(a(n), n=0..70);  # Alois P. Heinz, Aug 16 2020

Mathematica

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

Prog

(PARI) a(n)=bitxor(n, n>>1);
(PARI) a(n)=sum(k=1, n, (-1)^((k/2^valuation(k, 2)-1)/2)*2^valuation(k, 2))
(C) int a(int n) { return n ^ (n>>1); }
(Magma) // A recursive algorithm
N := 10; s := [[]];
for n in [1..N] do
for j in [#s..1 by -1] do
   Append(~s, Append(s[j], 1));
   Append(~s[j], 0);
end for;
end for;
[SequenceToInteger(b, 2):b in s]; // Jason Kimberley, Apr 02 2012
(Magma) // A direct algorithm
I2B := func< i | [b eq 1: b in IntegerToSequence(i, 2)]>;
B2I := func< s | SequenceToInteger([b select 1 else 0:b in s], 2)>;
[B2I(Xor(I2B(i), I2B(i div 2)cat[false])):i in [1..127]]; //Jason Kimberley, Apr 02 2012
(Haskell)
import Data.Bits (xor, shiftR)
a003188 n = n `xor` (shiftR n 1) :: Integer
-- Reinhard Zumkeller, May 26 2013, Apr 28 2012
(Python)
def A003188(n):
    return int(bin(n^(n/2))[2:], 2) # Indranil Ghosh, Jan 23 2017
(Python)
def A003188(n): return n^ n>>1 # Chai Wah Wu, Jun 29 2022
(R)
maxn <- 63 # by choice
a <- 1
for(n in 1:maxn){ a[2*n  ] <- 2*a[n] + (n%%2 != 0)
                  a[2*n+1] <- 2*a[n] + (n%%2 == 0)}
(a <- c(0, a))
# Yosu Yurramendi, Apr 10 2020
(C#)
static uint a(this uint n) => (n >> 1) ^ n; // Frank Hollstein, Mar 12 2021

Crossrefs

a(2*A003714(n)) = 3*A003714(n) for all n. - Antti Karttunen, Apr 26 1999

Cf. A014550 (in binary), A055975 (first differences), A048724 (even bisection), A065621 (odd bisection).

Cf. A006068, A038554, A048641, A048642.

Sequence in context: A233275 A153142 A154447 * A269401 A268933 A360982

Adjacent sequences: A003185 A003186 A003187 * A003189 A003190 A003191

Keyword

nonn,nice,easy,look

Author

N. J. A. Sloane

Status

approved