A106442 - OEIS

%I #7 Mar 31 2012 14:02:20

%S 0,1,2,3,4,7,6,11,8,5,14,13,12,19,22,9,16,25,10,31,28,29,26,37,24,21,

%T 38,15,44,41,18,47,128,23,50,49,20,55,62,53,56,59,58,61,52,27,74,67,

%U 192,69,42,43,76,73,30,35,88,33,82,87,36,91,94,39,64,121,46,97,100,111,98

%N Exponent-recursed cross-domain bijection from N to GF(2)[X]. Position of A075166(n) in A106456.

%C This map from the multiplicative domain of N to that of GF(2)[X] preserves Catalan-family structures, e.g. A106454(n) = a(A075164(n)), A075163(n) = A106453(a(n)), A075165(n) = A106455(a(n)), A075166(n) = A106456(a(n)), A075167(n) = A106457(a(n)). Shares with A091202 and A106444 the property that maps A000040(n) to A014580(n). Differs from the former for the first time at n=32, where A091202(32)=32, while a(32)=128. Differs from the latter for the first time at n=48, where A106444(48)=48, while a(48)=192.

%H A. Karttunen, <a href="/A091247/a091247.scm.txt">Scheme-program for computing this sequence.</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, a(p_i) = A014580(i) for primes p_i with index i and for composites n = p_i^e_i * p_j^e_j * p_k^e_k * ..., a(n) = A048723(a(p_i), a(e_i)) X A048723(a(p_j), a(1+e_j)-1) X A048723(a(p_k), a(1+e_k)-1) X ..., where X stands for carryless multiplication of GF(2)[X] polynomials (A048720) and A048723(n, y) raises the n-th GF(2)[X] polynomial to the y:th power. Here p_i is the most significant prime in the factorization of n; its exponent e_i is not incremented before the recursion step, while the exponents of less significant primes e_j, e_k, ... are incremented by one before recursing and the result of the recursion is decremented by one before use.

%e a(5) = 7, as 5 is the 3rd prime and the third irreducible GF(2)[X] polynomial x^2+x+1 is encoded as A014580(3) = 7. a(32) = a(2^5) = A048723(A014580(1),a(5)) = A048723(2,7) = 128. a(48) = a(3 * 2^4) = 3 X A048723(2,a(4+1)-1) = 3 X A048723(2,7-1) = 3 X 64 = 192.

%Y Inverse: A106443. a(n) = A106454(A075163(n)).

%K nonn

%O 0,3

%A _Antti Karttunen_, May 09 2005