A268718 Permutation of natural numbers: a(0) = 0, a(n) = 1 + A003188(A006068(n)-1), where A003188 is binary Gray code and A006068 is its inverse.

0, 1, 4, 2, 6, 8, 3, 7, 10, 12, 15, 11, 5, 13, 16, 14, 18, 20, 23, 19, 29, 21, 24, 22, 9, 25, 28, 26, 30, 32, 27, 31, 34, 36, 39, 35, 45, 37, 40, 38, 57, 41, 44, 42, 46, 48, 43, 47, 17, 49, 52, 50, 54, 56, 51, 55, 58, 60, 63, 59, 53, 61, 64, 62, 66, 68, 71, 67, 77, 69, 72, 70, 89, 73, 76, 74, 78, 80, 75, 79, 113, 81

Offset

0,3

Links

Antti Karttunen, Table of n, a(n) for n = 0..8191

Index entries for sequences that are permutations of the natural numbers

Formula

a(0) = 0, and for n >= 1, a(n) = A105081(A006068(n)) = 1 + A003188(A006068(n)-1).

Other identities. For all n >= 1:

a(A128309(n)) = A128309(n)+2. [Maps any even odious number to that number + 2.]

Mathematica

{0}~Join~Table[1 + BitXor[#, Floor[#/2]] &[BitXor @@ Table[Floor[n/2^m], {m, 0, Floor[Log[2, n]]}] - 1], {n, 81}] (* Michael De Vlieger, Feb 29 2016, after Jean-François Alcover at A006068 and Robert G. Wilson v at A003188 *)

Prog

(Scheme) (define (A268718 n) (if (zero? n) n (A105081 (A006068 n))))
(PARI)
a003188(n)=bitxor(n, n>>1);
a006068(n)= {
    my( s=1, ns );
    while ( 1,
        ns = n >> s;
        if ( 0==ns, break() );
        n = bitxor(n, ns);
        s <<= 1;
    );
    return (n);
} \\ by Joerg Arndt
a(n)=if(n==0, 0, 1 + a003188(a006068(n) - 1)); \\ Indranil Ghosh, Jun 07 2017
(Python)
def a003188(n): return n^(n>>1)
def a006068(n):
    s=1
    while True:
        ns=n>>s
        if ns==0: break
        n=n^ns
        s<<=1
    return n
def a(n): return 0 if n==0 else 1 + a003188(a006068(n) - 1) # Indranil Ghosh, Jun 07 2017

Crossrefs

Inverse: A268717.

Cf. A003188, A006068, A105081, A128309.

Row 1 of array A268830.

Cf. A092246 (fixed points).

Cf. A268818 ("square" of this permutation).

Cf. A268822 ("shifted square"), A268824 ("shifted cube") and also A268826, A268828 and A268832 (higher "shifted powers").

Sequence in context: A086399 A105365 A077157 * A306874 A114478 A367882

Adjacent sequences: A268715 A268716 A268717 * A268719 A268720 A268721

Keyword

nonn

Author

Antti Karttunen, Feb 12 2016

Status

approved