A232752 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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