login
Permutation of natural numbers: a(0) = 0, a(3n) = 1 + 2*a(2n - 1), a(3n+1) = 1 + 2*a(2n), a(3n+2) = 2*a(n+1).
10

%I #21 Mar 24 2021 09:52:00

%S 0,1,2,3,5,4,7,11,6,9,15,10,23,13,8,19,31,14,21,47,22,27,17,12,39,63,

%T 18,29,43,30,95,45,20,55,35,46,25,79,26,127,37,16,59,87,38,61,191,62,

%U 91,41,28,111,71,42,93,51,94,159,53,44,255,75,54,33,119,34,175,77,24,123,383,78,125,183,126,83,57,36,223,143,58,85,187,86,103,189,60

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

%H Antti Karttunen, <a href="/A254104/b254104.txt">Table of n, a(n) for n = 0..9842</a>

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

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

%F Other identities:

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

%o (Scheme, with memoizing macro definec)

%o (definec (A254104 n) (cond ((< n 1) n) ((= 2 (modulo n 3)) (* 2 (A254104 (/ (+ n 1) 3)))) (else (+ 1 (* 2 (A254104 (+ -1 (inv_for_A032766 n))))))))

%o (define (inv_for_A032766 n) (+ (* 2 (floor->exact (/ n 3))) (modulo n 3)))

%o (Python)

%o def a(n):

%o if n==0: return 0

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

%o elif n%3==1: return 1 + 2*a(2*(n - 1)//3)

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

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

%Y Inverse: A254103.

%Y Cf. A007051, A016789, A032766, A064216, A253887.

%K nonn

%O 0,3

%A _Antti Karttunen_, Jan 25 2015