A066194 A permutation of the integers (a fractal sequence): a(n) = A006068(n-1) + 1.

1, 2, 4, 3, 8, 7, 5, 6, 16, 15, 13, 14, 9, 10, 12, 11, 32, 31, 29, 30, 25, 26, 28, 27, 17, 18, 20, 19, 24, 23, 21, 22, 64, 63, 61, 62, 57, 58, 60, 59, 49, 50, 52, 51, 56, 55, 53, 54, 33, 34, 36, 35, 40, 39, 37, 38, 48, 47, 45, 46, 41, 42, 44, 43, 128, 127, 125, 126, 121, 122

Offset: 1

Author

Wouter Meeussen, Dec 15 2001

Keywords

• easy
• nonn

Comments

With an initial zero, inverse of the Gray Code (A003188). See also A006068. - Robert G. Wilson v, Jun 22 2014

I suspect the above comment refers to function A105081(n) = 1 + A003188(n - 1), n >= 1. - Antti Karttunen, Feb 15 2016

Examples

			Third nesting gives {1,2,4,3, 8,7,5,6} by means of joining the lists {1,2,4,3} = second nesting and {8,7,6,5} permuted by {1,2,4,3} giving {8,7,5,6}.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..8192 (first 1024 terms from Robert G. Wilson v)
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Inverse: A105081.

Cf. A003188, A006068, A268717.

Programs

Mathematica

Nest[ Join[ #, (Length[ #] + Range[ Length[ #], 1, -1 ])[[ # ]]] &, {1}, 7 ]
GrayCode[n_] := BitXor[n, Floor[n/2]]; t = Array[ GrayCode, 1000, 0]; Table[ Position[ t, n], {n, 0, 100}] // Flatten (* Robert G. Wilson v, Jun 22 2014 *)

Python

def A066194(n):
    k, m = n-1, n-1>>1
    while m > 0:
        k ^= m
        m >>= 1
    return k+1 # Chai Wah Wu, Jul 01 2022

Scheme

(define (A066194 n) (+ 1 (A006068 (- n 1)))) ;; Antti Karttunen, Feb 14 2016

Formula

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

a(n) = A006068(A268717(n)), composition of related permutations. - Antti Karttunen, Feb 14 2016

a(n) = 1 + Sum_{j=1..n-1} (1/6)*(-3 + (-1)^A007814(j) + 2^(A007814(j) + 3))*(-1)^(A000120(j) + 1). - John Erickson, Oct 18 2018

Extensions

Deléham's formula added to the name by Antti Karttunen, Feb 14 2016