OFFSET
0,3
COMMENTS
Inverse of sequenceA006068considered 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 alsoA021913.-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
Pierluigi Vellucci and Alberto Maria Bersani,Ordering of nested square roots of 2 according to Gray code,arXiv:1604.00222 [math.NT], 2016.
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(0) = 0, a(n + 1) = a(n) XOR 2^A007814(n) - Jaume Simon Gispert (jaume(AT)nuem ), Sep 11 2004
Inverse of sequenceA006068.-Philippe Deléham,Apr 29 2005
a(n) = a(n-1) XORA006519(n). -Franklin T. Adams-Watters,Jul 18 2011
FromMikhail Kurkov,Sep 27 2023: (Start)
a(2^m + k) = a(2^m - k - 1) + 2^m for 0 <= k < 2^m, m >= 0.
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)
defA003188(n):
return int(bin(n^(n/2))[2:], 2) #Indranil Ghosh,Jan 23 2017
(Python)
defA003188(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
KEYWORD
AUTHOR
STATUS
approved