A254103 Permutation of natural numbers: a(0) = 0, a(2n) = (3*a(n))-1, a(2n+1) = floor((3*(1+a(n)))/2).

0, 1, 2, 3, 5, 4, 8, 6, 14, 9, 11, 7, 23, 13, 17, 10, 41, 22, 26, 15, 32, 18, 20, 12, 68, 36, 38, 21, 50, 27, 29, 16, 122, 63, 65, 34, 77, 40, 44, 24, 95, 49, 53, 28, 59, 31, 35, 19, 203, 103, 107, 55, 113, 58, 62, 33, 149, 76, 80, 42, 86, 45, 47, 25, 365, 184, 188, 96, 194, 99, 101, 52, 230, 117, 119, 61, 131, 67, 71, 37, 284, 144, 146, 75, 158, 81, 83, 43

Offset: 0

Author

Antti Karttunen, Jan 25 2015

Keywords

• nonn

Comments

This sequence can be represented as a binary tree. Each child to the left is obtained by multiplying the parent by three and subtracting one, and each child to the right is obtained by adding one to parent, multiplying by three, and then halving the result (discarding a possible remainder):

0

|

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

2 3

5......../ \........4 8......../ \........6

/ \ / \ / \ / \

/ \ / \ / \ / \

/ \ / \ / \ / \

14 9 11 7 23 13 17 10

41 22 26 15 32 18 20 12 68 36 38 21 50 27 29 16

etc.

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: A254104.

Cf. A007051, A016789, A032766, A140263, A191450, A246207.

Similar permutations: A048673, A183209.

Programs

Python

def a(n):
    if n==0: return 0
    if n%2==0: return 3*a(n//2) - 1
    else: return int((3*(1 + a((n - 1)//2)))/2)
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 06 2017

Formula

a(0) = 0, a(2n) = A016789(a(n)-1), a(2n+1) = A032766(1+a(n)).

a(0) = 0, a(2n) = (3*a(n))-1, a(2n+1) = floor((3*(1+a(n)))/2).

Other identities:

a(2^n) = A007051(n) for all n >= 0. [A property shared with A048673 and A183209.]