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

Author

Antti Karttunen, Feb 12 2016

Keywords

• nonn

Links

• Antti Karttunen, Table of n, a(n) for n = 0..8191
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Inverse: A268717.

Cf. A003188, A006068, A010060, A105081, A128309, A166519, A171977, A277822.

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

Programs

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

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

Scheme

(define (A268718 n) (if (zero? n) n (A105081 (A006068 n))))

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

From Alan Michael Gómez Calderón, May 29 2025: (Start)

a(n) - 1 = A268717(n+1) XOR (A171977(n)+1) for n >= 1;

a(2*n-1) - 1 = (2-A010060(n-1)) XOR (A166519(n-1)-1) for n >= 1;

a(2*n) - 1 = (a(2*(n+1)-1)-1) XOR 2^A277822(n) for n >= 1. (End)