The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A003188 Decimal equivalent of Gray code for n. (Formerly M2250) 212
 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 (list; graph; refs; listen; history; text; internal format)
 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 27 10:09 EDT 2023. Contains 365688 sequences. (Running on oeis4.)