login
Factorization-preserving bijection from GF(2)[X]-polynomials to nonnegative integers, version which fixes the elements that are irreducible in both semirings.
18

%I #17 Nov 12 2017 03:05:30

%S 0,1,2,3,4,9,6,7,8,21,18,11,12,13,14,27,16,81,42,19,36,49,22,39,24,5,

%T 26,63,28,33,54,31,32,93,162,91,84,37,38,99,72,41,98,15,44,189,78,47,

%U 48,77,10,243,52,57,126,17,56,117,66,59,108,61,62,147,64,441

%N Factorization-preserving bijection from GF(2)[X]-polynomials to nonnegative integers, version which fixes the elements that are irreducible in both semirings.

%C Like A091203 this is a factorization-preserving isomorphism from GF(2)[X]-polynomials to integers. The former are encoded in the binary representation of n like this: n=11, '1011' in binary, stands for polynomial x^3+x+1, n=25, '11001' in binary, stands for polynomial x^4+x^3+1. However, this version does not map the irreducible GF(2)[X] polynomials (A014580) straight to the primes (A000040), but instead fixes the intersection of those two sets (A091206), and maps the elements in their set-wise difference A014580 \ A000040 (= A091214) in numerical order to the set-wise difference A000040 \ A014580 (= A091209).

%C The composite values are defined by the multiplicativity. E.g., we have a(A048724(n)) = 3*a(n) and a(A001317(n)) = A000244(n) = 3^n for all n.

%C This map satisfies many of the same identities as A091203, e.g., we have A091219(n) = A008683(a(n)), A091220(n) = A000005(a(n)), A091221(n) = A001221(a(n)), A091222(n) = A001222(a(n)), A091225(n) = A010051(a(n)) and A091247(n) = A066247(a(n)) for all n >= 1.

%H Antti Karttunen, <a href="/A235042/b235042.txt">Table of n, a(n) for n = 0..8192</a>

%H <a href="/index/Ge#GF2X">Index entries for sequences operating on GF(2)[X]-polynomials</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) = p for those irreducible GF(2)[X]-polynomials whose binary encoding is a prime (i.e., p is in A091206), and for the rest of irreducible GF(2)[X]-polynomials (those which are encoded by a composite natural number, i.e., q is in A091214), a(q) = A091209(A235044(q)), and for reducible polynomials, a(i X j X k X ...) = a(i) * a(j) * a(k) * ..., where each i, j, k, ... is in A014580, X stands for carryless multiplication of GF(2)[X] polynomials (A048720) and * for the ordinary multiplication of integers (A004247).

%e Here (t X u) = A048720(t,u):

%e a(2)=2, a(3)=3 and a(7)=7, as 2, 3 and 7 are all in A091206.

%e a(4) = a(2 X 2) = a(2)*a(2) = 2*2 = 4.

%e a(5) = a(3 X 3) = a(3)*a(3) = 3*3 = 9.

%e a(9) = a(3 X 7) = a(3)*a(7) = 3*7 = 21.

%e a(10) = a(2 X 3 X 3) = a(2)*a(3)*a(3) = 2*3*3 = 18.

%e a(15) = a(3 X 3 X 3) = a(3)^3 = 3^3 = 27.

%e a(17) = a(3 X 3 X 3 X 3) = a(3)^4 = 3^4 = 81.

%e a(21) = a(7 X 7) = a(7)*a(7) = 7*7 = 49.

%e a(25) = 5, as 25 is the first term of A091214 and 5 is the first term of A091209.

%e a(50) = a(2 X 25) = a(2)*a(25) = 2*5 = 10.

%o (Scheme, with _Antti Karttunen_'s IntSeq-library)

%o (definec (A235042 n) (cond ((< n 2) n) ((= 1 (A010051 n) (A091225 n)) n) ((= 1 (A091225 n)) (A091209 (A235044 n))) (else (reduce * 1 (map A235042 (gf2xfactor n))))))

%Y Inverse: A235041. Fixed points: A235045.

%Y Cf. A010051, A004247, A091225, A091209, A235044.

%Y Similar cross-multiplicative permutations: A091203, A091205, A106443, A106445, A106447.

%K nonn

%O 0,3

%A _Antti Karttunen_, Jan 02 2014