login
Permutation of natural numbers: a(0)=0, a(1)=1, a(2n)=A005228(1+(a(n))), a(2n+1)=A030124(a(n)).
11

%I #15 Dec 05 2013 08:43:24

%S 0,1,3,2,12,5,7,4,114,16,26,8,45,10,18,6,7562,127,191,21,462,32,56,11,

%T 1285,53,83,14,236,23,35,9,29172079,7677,9314,141,20528,208,312,27,

%U 115291,489,679,39,1943,65,98,15,865555,1331,1751,62,4111,94,150,19,30983,255,369,29,802,42,69,13

%N Permutation of natural numbers: a(0)=0, a(1)=1, a(2n)=A005228(1+(a(n))), a(2n+1)=A030124(a(n)).

%C This is one example of the generic class of "entangling of two pairs of complementary sets" permutations of natural numbers. In this case, the Hofstadter's complementary pair A005228 & A030124 is entangled with complementary pair of A005843 & A005408, the even & odd numbers.

%C Note how, apart from 1, all the other terms of A005228 (1, 3, 7, 12, 18, 26, ...) occur in even positions, and all the terms of A030124 (2, 4, 5, 6, 8, 9, 10, 11, 13, 14, ...) occur in odd positions.

%C Moreover, at the positions given by two's powers, from 2^1 = 2 onwards, a(2^n) = 3, 12, 114, 7562, 29172079, ... the values are iterates of function b(n) = A005228(n+1) from b(1)=3 onward: b(1)=3, b(b(1))=12, b(b(b(1)))=114, b(b(b(b(1))))=7562, and so on.

%C In the same way, at the positions given by A000225, from 2^2 - 1 = 3 onwards, the iterates of A030124 appear, A030124(1), A030124(A030124(1)), A030124(A030124(A030124(1))), and so on, as: 2, 4, 6, 9, 13, 17, ... (= A232739).

%C The permutation A227413 is obtained in analogous way by entangling primes and composites with even and odd numbers.

%H <a href="/index/Ho#Hofstadter">Index entries for Hofstadter-type sequences</a>

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

%F a(0)=0, a(1)=1, and for even n > 1, a(n) = A005228(1+(a(n/2))), for odd n > 1, a(n) = A030124(a((n-1)/2)).

%F For all n >=1, a(A000225(n+1)) = A232739(n).

%o (Scheme, with memoization macro definec from Antti Karttunen's IntSeq-library)

%o (definec (A232752 n) (cond ((< n 2) n) ((even? n) (A005228 (+ 1 (A232752 (/ n 2))))) (else (A030124 (A232752 (/ (- n 1) 2))))))

%Y Inverse permutation: A232751.

%Y Cf. A227413, A005228, A030124, A005843 & A005408, A000079, A000225, A232739.

%Y Cf. also the permutation pair A167151 & A225850.

%K nonn

%O 0,3

%A _Antti Karttunen_, Nov 30 2013