login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006068 a(n) is Gray-coded into n.
(Formerly M2253)
132

%I M2253

%S 0,1,3,2,7,6,4,5,15,14,12,13,8,9,11,10,31,30,28,29,24,25,27,26,16,17,

%T 19,18,23,22,20,21,63,62,60,61,56,57,59,58,48,49,51,50,55,54,52,53,32,

%U 33,35,34,39,38,36,37,47,46,44,45,40,41,43,42,127,126,124,125,120,121

%N a(n) is Gray-coded into n.

%C Equivalently, if binary expansion of n has m bits (say), compute derivative of n (A038554), getting sequence n' of length m-1; sort on n'.

%C Inverse of sequence A003188 considered as a permutation of the nonnegative integers, i.e., a(A003188(n)) = n = A003188(a(n)). - _Howard A. Landman_, Sep 25 2001

%C The sequence exhibits glide reflections that grow fractally. These show up well on the scatterplot, also audibly using the "listen" link. - _Peter Munn_, Aug 18 2019

%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 T. D. Noe, <a href="/A006068/b006068.txt">Table of n, a(n) for n = 0..1023</a>

%H Eric Rowland, Reem Yassawi, <a href="https://arxiv.org/abs/1403.7659">Profinite automata</a>, arXiv:1403.7659 [math.DS], 2014. See p. 22.

%H Paul Tarau, <a href="http://www.cse.unt.edu/~tarau/research/2009/fISO.pdf">Isomorphic Data Encodings and their Generalization to Hylomorphisms on Hereditarily Finite Data Types</a>; see also <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.212.3832">alternate link</a>.

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%F a(n) = 2*a(ceiling((n+1)/2)) + A010060(n-1). If 3*2^(k-1) < n <= 2^(k+1), a(n) = 2^(k+1) - 1 - a(n-2^k); if 2^(k+1) < n <= 3*2^k, a(n) = a(n-2^k) + 2^k. - _Henry Bottomley_, Jan 10 2001

%F a(n) = n XOR [n/2] XOR [n/4] XOR [n/8] ... XOR [n/2^m] where m = [log(n)/log(2)] (for n>0) and [x] is integer floor of x. - _Paul D. Hanna_, Jun 04 2002

%F a(n) XOR [a(n)/2] = n. - _Paul D. Hanna_, Jan 18 2012

%F A066194(n) = a(n-1) + 1, n>=1. - _Philippe Deléham_, Apr 29 2005

%F a(n) = if n<2 then n else 2*m + (n mod 2 + m mod 2) mod 2, with m=a(floor(n/2)). - _Reinhard Zumkeller_, Aug 10 2010

%F a(n XOR m) = a(n) XOR a(m), where XOR is the bitwise exclusive-or operator, A003987. - _Peter Munn_, Dec 14 2019

%e The first few values of n' are -,-,1,0,10,11,01,00,100,101,111,110,010,011,001,000,... (for n=0..15) and to put these in lexicographic order we must take n in the order 0,1,3,2,7,6,4,5,15,14,12,13,8,9,11,10,...

%p a:= proc(n) option remember; `if`(n<2, n,

%p Bits[Xor](n, a(iquo(n, 2))))

%p end:

%p seq(a(n), n=0..100); # _Alois P. Heinz_, Apr 17 2018

%t a[n_] := BitXor @@ Table[Floor[n/2^m], {m, 0, Floor[Log[2, n]]}]; a[0]=0; Table[a[n], {n, 0, 69}] (* _Jean-François Alcover_, Jul 19 2012, after _Paul D. Hanna_ *)

%t Table[Fold[BitXor, n, Quotient[n, 2^Range[BitLength[n] - 1]]], {n, 0, 70}] (* _Jan Mangaldan_, Mar 20 2013 *)

%o (PARI) {a(n)=local(B=n);for(k=1,floor(log(n+1)/log(2)),B=bitxor(B,n\2^k));B} /* _Paul D. Hanna_, Jan 18 2012 */

%o (PARI) /* the following routine needs only O(log_2(n)) operations */

%o a(n)= {

%o my( s=1, ns );

%o while ( 1,

%o ns = n >> s;

%o if ( 0==ns, break() );

%o n = bitxor(n, ns);

%o s <<= 1;

%o );

%o return ( n );

%o } /* _Joerg Arndt_, Jul 19 2012 */

%o (Haskell)

%o a006068 n = foldl xor 0 $

%o map (div n) $ takeWhile (<= n) a000079_list :: Integer

%o -- _Reinhard Zumkeller_, Apr 28 2012

%o (Python)

%o def a(n):

%o s=1

%o while True:

%o ns=n>>s

%o if ns==0: break

%o n=n^ns

%o s<<=1

%o return n

%o print [a(n) for n in range(101)] # _Indranil Ghosh_, Jun 07 2017, after PARI code by _Joerg Arndt_

%o (R)

%o a <- c(1,3,2)

%o maxn <- 63 # by choice

%o for(n in 2:maxn){

%o if(a[n]%%2 == 0) {a[2*n] <- 2*a[n] ; a[2*n+1] <- 2*a[n]+1}

%o else {a[2*n] <- 2*a[n]+1 ; a[2*n+1] <- 2*a[n]}

%o }

%o a

%o # _Yosu Yurramendi_, Jan 15 2020

%Y Cf. A038554, A005811, A003188, A014550, A003100.

%Y Cf. A054429, A180200. - _Reinhard Zumkeller_, Aug 15 2010

%Y Cf. A000079, A055975 (first differences).

%Y A003987, A010060 are used to express relationship between terms of this sequence.

%K nonn,easy,nice,look,hear

%O 0,3

%A _N. J. A. Sloane_

%E More terms from _Henry Bottomley_, Jan 10 2001

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 10 05:04 EDT 2020. Contains 333392 sequences. (Running on oeis4.)