login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003188 Decimal equivalent of Gray code for n.
(Formerly M2250)
107
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 the 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

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

N. J. A. Sloane, Table of n, a(n) for n = 0..1000

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

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

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

R. Stephan, Table of generating functions

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

Pierluigi Vellucci, 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([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.

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

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

CROSSREFS

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

Same sequence in binary: A014550, bisection: A048724. Cf. A038554, A048641, A048642, A055975 (first differences).

Sequence in context: A233275 A153142 A154447 * A269401 A268933 A268831

Adjacent sequences:  A003185 A003186 A003187 * A003189 A003190 A003191

KEYWORD

nonn,nice,easy

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 | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 24 05:47 EDT 2016. Contains 273236 sequences.