A276442 Permutation of natural numbers: a(1) = 1; a(2n) = A088359(a(n)), a(2n+1) = A087686(1+a(n)), where A088359 & A087686 = numbers that occur only once & more than once in A004001.

1, 3, 2, 6, 7, 5, 4, 11, 14, 13, 15, 10, 12, 9, 8, 20, 26, 25, 30, 23, 29, 28, 31, 19, 24, 22, 27, 18, 21, 17, 16, 37, 47, 46, 57, 44, 56, 55, 62, 41, 53, 52, 61, 50, 60, 59, 63, 36, 45, 43, 54, 40, 51, 49, 58, 35, 42, 39, 48, 34, 38, 33, 32, 70, 85, 84, 105, 82, 104, 103, 120, 79, 101, 100, 119, 98, 118, 117, 126, 75, 95, 94

Offset: 1

Author

Antti Karttunen, Sep 03 2016

Keywords

• nonn
• base
• tabf

Comments

This sequence can be represented as a binary tree. Each left hand child is produced as A088359(n), and each right hand child as A087686(1+n), when their parent contains n:

|

...................1...................

3 2

6......../ \........7 5......../ \........4

/ \ / \ / \ / \

/ \ / \ / \ / \

/ \ / \ / \ / \

11 14 13 15 10 12 9 8

20 26 25 30 23 29 28 31 19 24 22 27 18 21 17 16

etc.

As in the mirror image permutation A267112, the level k of the tree contains all numbers of binary width k like many other base-2 related permutations (A003188, A054429, A233278, etc). For a proof, see A267110, which gives the contents of each parent node (for a node containing n > 1).

Links

• Antti Karttunen, Table of n, a(n) for n = 1..8191
• T. Kubo and R. Vakil, On Conway's recursive sequence, Discr. Math. 152 (1996), 225-252.
• Index entries for sequences related to binary expansion of n
• Index entries for Hofstadter-type sequences
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Inverse: A276441.

Cf. A004001, A087686, A088359, A267110.

Related or similar permutations: A003188, A054429, A233276, A233278, A267112, A276344, A276346, A276444.

Programs

Scheme

(definec (A276442 n) (cond ((< n 2) n) ((even? n) (A088359 (A276442 (/ n 2)))) (else (A087686 (+ 1 (A276442 (/ (- n 1) 2)))))))

Formula

a(1) = 1; after which, a(2n) = A088359(a(n)), a(2n+1) = A087686(1+a(n)).

As a composition of other permutations:

a(n) = A267112(A054429(n)).

a(n) = A276344(A233278(n)).

a(n) = A276346(A233276(n)).

a(n) = A276444(A003188(n)).