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

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

Cf. A000523, A003188, A003987, A006068, A010060, A066194, A101080, A171977, A268718, A268726, A268727.

Row 1 and column 1 of array A268715 (without the initial zero).

Row 1 of array A268820.

Cf. A092246 (fixed points).

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

Cf. A268821 ("shifted square"), A268823 ("shifted cube") and also A268825, A268827 and A268831 ("shifted higher powers").

Programs

Mathematica

A003188[n_] := BitXor[n, Floor[n/2]]; A006068[n_] := If[n == 0, 0, BitXor @@ Table[Floor[n/2^m], {m, 0, Floor[Log[2, n]]}]]; a[n_] := If[n == 0, 0, A003188[1 + A006068[n-1]]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Feb 23 2016 *)

PARI

A003188(n) = bitxor(n, floor(n/2));
A006068(n) = if(n<2, n, {my(m = A006068(floor(n/2))); 2*m + (n%2 + m%2)%2});
for(n=0, 100, print1(if(n<1, 0, A003188(1 + A006068(n - 1)))", ")) \\ Indranil Ghosh, Mar 31 2017

Python

def A003188(n): return n^(n//2)
def A006068(n):
    if n<2: return n
    m = A006068(n//2)
    return 2*m + (n%2 + m%2)%2
def a(n): return 0 if n<1 else A003188(1 + A006068(n - 1))
print([a(n) for n in range(0, 101)]) # Indranil Ghosh, Mar 31 2017

Python

def A268717(n):
    k, m = n-1, n-1>>1
    while m > 0:
        k ^= m
        m >>= 1
    return k+1^ k+1>>1 # Chai Wah Wu, Jun 29 2022

Scheme

(define (A268717 n) (if (zero? n) n (A003188 (A066194 n))))

Formula

a(n) = A003188(A066194(n)) = A003188(1+A006068(n-1)).

Other identities. For all n >= 0:

A101080(n,a(n+1)) = 1. [The Hamming distance between n and a(n+1) is always one.]

A268726(n) = A000523(A003987(n, a(n+1))). [A268726 gives the index of the toggled bit.]

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

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

a(n) = (A268718(n-1)-1) XOR (A171977(n-1)+1) for n >= 2. (End)