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

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

%S 0,1,2,3,4,9,6,5,8,15,18,7,12,11,10,27,16,81,30,13,36,25,14,33,24,17,

%T 22,45,20,21,54,19,512,57,162,55,60,23,26,63,72,29,50,51,28,135,66,31,

%U 768,35,34,19683,44,39,90,37,40,99,42,41,108,43,38,75,64,225,114,47

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

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

%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. For irreducible GF(2)[X] polynomials ir_i with index i (i.e. A014580(i)), a(ir_i) = A000040(i) and for composite polynomials n = A048723(ir_i, e_i) X A048723(ir_j, e_j) X A048723(ir_k, e_k) X ..., a(n) = a(ir_i)^a(e_i) * a(ir_j)^(a(1+e_j)-1) * a(ir_k)^(a(1+e_k)-1) * ... = A000040(i)^a(e_i) * A000040(j)^(a(1+e_j)-1) * A000040(k)^(a(1+e_k)-1), 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, while * is the ordinary multiplication and ^ is the ordinary exponentiation. Here ir_i is the most significant (largest) irreducible polynomial in the factorization of n; its exponent e_i is not incremented before the recursion step, while the exponents of less significant factors 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) = 9, as 5 encodes the GF(2)[X] polynomial x^2+1, which is the square of the second irreducible GF(2)[X] polynomial x+1 (encoded as 3) and the square of the second prime is 3^2=9. a(32) = a(A048723(2,5)) = 2^a(5) = 2^9 = 512. a(48) = a(3 X A048723(2,4)) = 3 * 2^(a(4+1)-1) = 3 * 2^(9-1) = 3 * 256 = 768.

%Y Inverse: A106442. a(n) = A075164(A106453(n)).

%K nonn

%O 0,3

%A _Antti Karttunen_, May 09 2005