A254103 - OEIS

%I #26 Mar 11 2021 18:03:13

%S 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,

%T 38,21,50,27,29,16,122,63,65,34,77,40,44,24,95,49,53,28,59,31,35,19,

%U 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

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

%C 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):

%C                                      0

%C                                      |

%C                   ...................1...................

%C                  2                                       3

%C        5......../ \........4                   8......../ \........6

%C       / \                 / \                 / \                 / \

%C      /   \               /   \               /   \               /   \

%C     /     \             /     \             /     \             /     \

%C   14       9          11       7          23       13         17       10

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

%C etc.

%H Antti Karttunen, <a href="/A254103/b254103.txt">Table of n, a(n) for n = 0..8191</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

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

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

%F Other identities:

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

%o (Scheme, with memoizing macro definec)

%o ;; First a stand-alone version for MIT/GNU Scheme:

%o (definec (A254103 n) (cond ((zero? n) n) ((even? n) (+ -1 (* 3 (A254103 (/ n 2))))) (else (floor->exact (/ (* 3 (+ 1 (A254103 (/ (- n 1) 2)))) 2)))))

%o (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.

%o (Python)

%o def a(n):

%o     if n==0: return 0

%o     if n%2==0: return 3*a(n//2) - 1

%o     else: return int((3*(1 + a((n - 1)//2)))/2)

%o print([a(n) for n in range(101)]) # _Indranil Ghosh_, Jun 06 2017

%Y Inverse: A254104.

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

%Y Similar permutations: A048673, A183209.

%K nonn

%O 0,3

%A _Antti Karttunen_, Jan 25 2015