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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006068 a(n) is Gray-coded into n.
(Formerly M2253)
87
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, 19, 18, 23, 22, 20, 21, 63, 62, 60, 61, 56, 57, 59, 58, 48, 49, 51, 50, 55, 54, 52, 53, 32, 33, 35, 34, 39, 38, 36, 37, 47, 46, 44, 45, 40, 41, 43, 42, 127, 126, 124, 125, 120, 121 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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

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

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

T. D. Noe, Table of n, a(n) for n = 0..1023

Eric Rowland, Reem Yassawi, Profinite automata, arXiv:1403.7659 [math.DS], 2014. See p. 22.

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

Index entries for sequences that are permutations of the natural numbers

FORMULA

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.

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

a(n) XOR [a(n)/2] = n. - Paul D. Hanna, Jan 18 2012

A066194(n) = a(n-1) + 1, n>=1. - Philippe Deléham, Apr 29 2005

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

EXAMPLE

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

MATHEMATICA

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

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

PROG

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

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

a(n)= {

    my( s=1, ns );

    while ( 1,

        ns = n >> s;

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

        n = bitxor(n, ns);

        s <<= 1;

    );

    return ( n );

} /* Joerg Arndt, Jul 19 2012 */

(Haskell)

a006068 n = foldl xor 0 $

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

-- Reinhard Zumkeller, Apr 28 2012

CROSSREFS

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

Cf. A054429, A180200. -Reinhard Zumkeller, Aug 15 2010

Cf. A000079, A055975 (first differences).

Sequence in context: A233276 A276441 A153141 * A154436 A269402 A268934

Adjacent sequences:  A006065 A006066 A006067 * A006069 A006070 A006071

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

Formula and more terms from Henry Bottomley, Jan 10 2001

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified March 24 04:07 EDT 2017. Contains 283984 sequences.