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

0, 1, 3, 2, 12, 5, 7, 4, 114, 16, 26, 8, 45, 10, 18, 6, 7562, 127, 191, 21, 462, 32, 56, 11, 1285, 53, 83, 14, 236, 23, 35, 9, 29172079, 7677, 9314, 141, 20528, 208, 312, 27, 115291, 489, 679, 39, 1943, 65, 98, 15, 865555, 1331, 1751, 62, 4111, 94, 150, 19, 30983, 255, 369, 29, 802, 42, 69, 13

Offset

0,3

Comments

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.

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.

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.

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

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

Links

Table of n, a(n) for n=0..63.

Index entries for Hofstadter-type sequences

Index entries for sequences that are permutations of the natural numbers

Formula

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

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

Prog

(Scheme, with memoization macro definec from Antti Karttunen's IntSeq-library)
(definec (A232752 n) (cond ((< n 2) n) ((even? n) (A005228 (+ 1 (A232752 (/ n 2))))) (else (A030124 (A232752 (/ (- n 1) 2))))))

Crossrefs

Inverse permutation: A232751.

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

Cf. also the permutation pair A167151 & A225850.

Sequence in context: A016560 A122407 A346122 * A195200 A098646 A129925

Adjacent sequences: A232749 A232750 A232751 * A232753 A232754 A232755

Keyword

nonn

Author

Antti Karttunen, Nov 30 2013

Status

approved