login
A235042
Factorization-preserving bijection from GF(2)[X]-polynomials to nonnegative integers, version which fixes the elements that are irreducible in both semirings.
18
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.
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.
Similar cross-multiplicative permutations: A091203, A091205, A106443, A106445, A106447.
Sequence in context: A236852 A363318 A236837 * A234742 A277711 A060866
KEYWORD
nonn
AUTHOR
Antti Karttunen, Jan 02 2014
STATUS
approved