A048641 -id:A048641 - cp's OEIS frontend

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

N. J. A. Sloane

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

			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

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).

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

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.

C
```
int a(int n) { return n ^ (n>>1); }
```

import Data.Bits (xor, shiftR)
a003188 n = n `xor` (shiftR n 1) :: Integer
-- Reinhard Zumkeller, May 26 2013, Apr 28 2012

// 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

// 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

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

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

PARI
```
a(n)=bitxor(n,n>>1);
```

a(n)=sum(k=1,n,(-1)^((k/2^valuation(k,2)-1)/2)*2^valuation(k,2))

def A003188(n):
    return int(bin(n^(n//2))[2:],2) # Indranil Ghosh, Jan 23 2017

def A003188(n): return n^ n>>1 # Chai Wah Wu, Jun 29 2022

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

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
From Mikhail Kurkov, Sep 27 2023: (Start)
a(2^m + k) = a(2^m - k - 1) + 2^m for 0 <= k < 2^m, m >= 0.
a(n) = a(A053645(A054429(n))) + A053644(n) for n > 0.
a(n) = A063946(a(A053645(n)) + A053644(n)) for n > 0. (End)

cp's OEIS Frontend

A048644 Differences between partial sums of Gray code (A048641) and triangular numbers (A000217).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A003188 Decimal equivalent of Gray code for n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

C

Haskell

Magma

Magma

Maple

Mathematica

PARI

PARI

Python

Python

R

Formula