|
%I M2250 #182 Apr 22 2024 21:00:33
%S 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,
%T 23,22,18,19,17,16,48,49,51,50,54,55,53,52,60,61,63,62,58,59,57,56,40,
%U 41,43,42,46,47,45,44,36,37,39,38,34,35,33,32,96,97,99,98,102,103,101
%N Decimal equivalent of Gray code for n.
%C 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
%C Restricts to a permutation of each {2^(i - 1) .. 2^i - 1}. - _Jason Kimberley_, Apr 02 2012
%C a(n) mod 2 = floor(((n + 1) mod 4) / 2), see also A021913. - _Reinhard Zumkeller_, Apr 28 2012
%C 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
%C 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
%D M. Gardner, Mathematical Games, Sci. Amer. Vol. 227 (No. 2, Feb. 1972), p. 107.
%D M. Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 15.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Indranil Ghosh, <a href="/A003188/b003188.txt">Table of n, a(n) for n = 0..32767</a> (first 1001 terms from N. J. A. Sloane)
%H M. W. Bunder, K. P. Tognetti, and G. E. Wheeler, <a href="http://dx.doi.org/10.1016/j.disc.2006.12.004">On binary reflected Gray codes and functions</a>, Discr. Math., 308 (2008), 1690-1700.
%H Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>, Preprint 2016.
%H Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="https://doi.org/10.1145/3127585">Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications</a>, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
%H Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://arxiv.org/abs/2210.10968">Identities and periodic oscillations of divide-and-conquer recurrences splitting at half</a>, arXiv:2210.10968 [cs.DS], 2022, p. 39.
%H P. Mathonet, M. Rigo, M. Stipulanti and N. Zénaïdi, <a href="https://arxiv.org/abs/2201.06636">On digital sequences associated with Pascal's triangle</a>, arXiv:2201.06636 [math.NT], 2022.
%H J. A. Oteo and J. Ros, <a href="http://dx.doi.org/10.1088/0305-4470/38/41/007">A Fractal Set from the Binary Reflected Gray Code</a>, J. Phys. A: Math Gen. 38 (2005) 8935-8949.
%H Ed Pegg, Jr., <a href="http://www.mathpuzzle.com/MAA/07-Sequence%20Pictures/mathgames_12_08_03.html">Sequence Pictures</a>, Math Games column, Dec 08 2003.
%H Ed Pegg, Jr., <a href="/A000043/a000043_2.pdf">Sequence Pictures</a>, Math Games column, Dec 08 2003 [Cached copy, with permission (pdf only)]
%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>
%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>
%H Paul Tarau, <a href="http://logic.csci.unt.edu/tarau/research/2009/fISO.pdf">Isomorphic Data Encodings and their Generalization to Hylomorphisms on Hereditarily Finite Data Types</a>
%H Pierluigi Vellucci and Alberto Maria Bersani, <a href="http://arxiv.org/abs/1604.00222">Ordering of nested square roots of 2 according to Gray code</a>, arXiv:1604.00222 [math.NT], 2016.
%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F a(n) = 2*a(floor(n/2)) + A021913(n - 1). - _Henry Bottomley_, Apr 05 2001
%F a(n) = n XOR floor(n/2), where XOR is the binary exclusive OR operator. - _Paul D. Hanna_, Jun 04 2002
%F G.f.: (1/(1-x)) * Sum_{k>=0} 2^k*x^2^k/(1 + x^2^(k+1)). - _Ralf Stephan_, May 06 2003
%F a(0) = 0, a(2n) = 2a(n) + [n odd], a(2n + 1) = 2a(n) + [n even]. - _Ralf Stephan_, Oct 20 2003
%F a(0) = 0, a(n) = 2 a(floor(n/2)) + mod(floor((n + 1)/2), 2).
%F a(n) = Sum_{k=1..n} 2^A007814(k) * (-1)^((k/2^A007814(k) - 1)/2). - _Ralf Stephan_, Oct 29 2003
%F a(0) = 0, a(n + 1) = a(n) XOR 2^A007814(n) - Jaume Simon Gispert (jaume(AT)nuem.com), Sep 11 2004
%F Inverse of sequence A006068. - _Philippe Deléham_, Apr 29 2005
%F a(n) = a(n-1) XOR A006519(n). - _Franklin T. Adams-Watters_, Jul 18 2011
%F From _Mikhail Kurkov_, Sep 27 2023: (Start)
%F a(2^m + k) = a(2^m - k - 1) + 2^m for 0 <= k < 2^m, m >= 0.
%F a(n) = a(A053645(A054429(n))) + A053644(n) for n > 0.
%F a(n) = A063946(a(A053645(n)) + A053644(n)) for n > 0. (End)
%e 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
%p with(combinat); graycode(6); # to produce first 64 terms
%p printf(cat(` %.6d`$64), op(map(convert, graycode(6), binary))); lprint(); # to produce binary strings
%p # alternative:
%p read("transforms"):
%p A003188 := proc(n)
%p XORnos(n,floor(n/2)) ;
%p end proc: # _R. J. Mathar_, Mar 09 2015
%p # another Maple program:
%p a:= n-> Bits[Xor](n, iquo(n, 2)):
%p seq(a(n), n=0..70); # _Alois P. Heinz_, Aug 16 2020
%t f[n_] := BitXor[n, Floor[n/2]]; Array[f, 70, 0] (* _Robert G. Wilson v_, Jun 09 2010 *)
%o (PARI) a(n)=bitxor(n,n>>1);
%o (PARI) a(n)=sum(k=1,n,(-1)^((k/2^valuation(k,2)-1)/2)*2^valuation(k,2))
%o (C) int a(int n) { return n ^ (n>>1); }
%o (Magma) // A recursive algorithm
%o N := 10; s := [[]];
%o for n in [1..N] do
%o for j in [#s..1 by -1] do
%o Append(~s,Append(s[j],1));
%o Append(~s[j],0);
%o end for;
%o end for;
%o [SequenceToInteger(b,2):b in s]; // _Jason Kimberley_, Apr 02 2012
%o (Magma) // A direct algorithm
%o I2B := func< i | [b eq 1: b in IntegerToSequence(i,2)]>;
%o B2I := func< s | SequenceToInteger([b select 1 else 0:b in s],2)>;
%o [B2I(Xor(I2B(i),I2B(i div 2)cat[false])):i in [1..127]]; //_Jason Kimberley_, Apr 02 2012
%o (Haskell)
%o import Data.Bits (xor, shiftR)
%o a003188 n = n `xor` (shiftR n 1) :: Integer
%o -- _Reinhard Zumkeller_, May 26 2013, Apr 28 2012
%o (Python)
%o def A003188(n):
%o return int(bin(n^(n/2))[2:],2) # _Indranil Ghosh_, Jan 23 2017
%o (Python)
%o def A003188(n): return n^ n>>1 # _Chai Wah Wu_, Jun 29 2022
%o (R)
%o maxn <- 63 # by choice
%o a <- 1
%o for(n in 1:maxn){ a[2*n ] <- 2*a[n] + (n%%2 != 0)
%o a[2*n+1] <- 2*a[n] + (n%%2 == 0)}
%o (a <- c(0,a))
%o # _Yosu Yurramendi_, Apr 10 2020
%o (C#)
%o static uint a(this uint n) => (n >> 1) ^ n; // _Frank Hollstein_, Mar 12 2021
%Y a(2*A003714(n)) = 3*A003714(n) for all n. - _Antti Karttunen_, Apr 26 1999
%Y Cf. A014550 (in binary), A055975 (first differences), A048724 (even bisection), A065621 (odd bisection).
%Y Cf. A006068, A038554, A048641, A048642.
%K nonn,nice,easy,look,changed
%O 0,3
%A _N. J. A. Sloane_
|
