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

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, 26, 63, 28, 33, 54, 31, 32, 93, 162, 91, 84, 37, 38, 99, 72, 41, 98, 15, 44, 189, 78, 47, 48, 77, 10, 243, 52, 57, 126, 17, 56, 117, 66, 59, 108, 61, 62, 147, 64, 441

Offset

0,3

Comments

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).

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.

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.

Links

Antti Karttunen, Table of n, a(n) for n = 0..8192

Index entries for sequences operating on GF(2)[X]-polynomials

Index entries for sequences that are permutations of the natural numbers

Formula

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).

Example

Here (t X u) = A048720(t,u):
a(2)=2, a(3)=3 and a(7)=7, as 2, 3 and 7 are all in A091206.
a(4) = a(2 X 2) = a(2)*a(2) = 2*2 = 4.
a(5) = a(3 X 3) = a(3)*a(3) = 3*3 = 9.
a(9) = a(3 X 7) = a(3)*a(7) = 3*7 = 21.
a(10) = a(2 X 3 X 3) = a(2)*a(3)*a(3) = 2*3*3 = 18.
a(15) = a(3 X 3 X 3) = a(3)^3 = 3^3 = 27.
a(17) = a(3 X 3 X 3 X 3) = a(3)^4 = 3^4 = 81.
a(21) = a(7 X 7) = a(7)*a(7) = 7*7 = 49.
a(25) = 5, as 25 is the first term of A091214 and 5 is the first term of A091209.
a(50) = a(2 X 25) = a(2)*a(25) = 2*5 = 10.

Prog

(Scheme, with Antti Karttunen's IntSeq-library)
(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))))))

Crossrefs

Inverse: A235041. Fixed points: A235045.

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

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

Sequence in context: A236852 A363318 A236837 * A234742 A277711 A060866

Adjacent sequences: A235039 A235040 A235041 * A235043 A235044 A235045

Keyword

nonn

Author

Antti Karttunen, Jan 02 2014

Status

approved