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,3

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

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

Prog

(Scheme, with memoizing macro definec)
;; First a stand-alone version for MIT/GNU Scheme:
(definec (A254103 n) (cond ((zero? n) n) ((even? n) (+ -1 (* 3 (A254103 (/ n 2))))) (else (floor->exact (/ (* 3 (+ 1 (A254103 (/ (- n 1) 2)))) 2)))))
(definec (A254103 n) (cond ((< n 1) n) ((even? n) (A016789 (- (A254103 (/ n 2)) 1))) (else (A032766 (+ 1 (A254103 (/ (- n 1) 2))))))) ;; Above represented with A-numbers.
(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

Crossrefs

Inverse: A254104.

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

Similar permutations: A048673, A183209.

Sequence in context: A102398 A118317 A127522 * A048673 A288119 A292575

Adjacent sequences: A254100 A254101 A254102 * A254104 A254105 A254106

Keyword

nonn

Author

Antti Karttunen, Jan 25 2015

Status

approved