login
Doubly-recursed cross-domain bijection from GF(2)[X] to N. Variant of A091205 and A106445.
6

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

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

%T 46,45,20,21,54,19,512,57,162,115,60,47,26,63,72,61,50,33,28,135,138,

%U 17,48,35,22,19683,92,39,90,37,40,207,42,83,108,29,38,75,64,225,114

%N Doubly-recursed cross-domain bijection from GF(2)[X] to N. Variant of A091205 and A106445.

%C Differs from A091205 for the first time at n=32, where A091205(32)=32, while a(32)=512. Differs from A106445 for the first time at n=13, where A106445(13)=11, while a(13)=23.

%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(a(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(e_j) * a(ir_k)^a(e_k) * ... = A000040(a(i))^a(e_i) * A000040(a(j))^a(e_j) * A000040(a(k))^a(e_k), 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.

%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), a(2)=2 and the square of the second prime is 3^2=9. a(13) = a(A014580(5)) = A000040(a(5)) = A000040(9) = 23. a(32) = a(A048723(2,5)) = a(2)^a(5) = 2^9 = 512. a(48) = a(3 X A048723(2,4)) = a(3) * a(2)^a(4) = 3 * 2^4 = 3 * 16 = 48.

%Y Inverse: A106446. Variant: A091205.

%K nonn

%O 0,3

%A _Antti Karttunen_, May 09 2005