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

%I #23 Nov 11 2017 16:49:17

%S 0,1,2,3,4,25,6,7,8,5,50,11,12,13,14,43,16,55,10,19,100,9,22,87,24,

%T 321,26,15,28,91,86,31,32,29,110,79,20,37,38,23,200,41,18,115,44,125,

%U 174,47,48,21,642,89,52,117,30,227,56,53,182,59,172,61,62,27,64

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

%C Like A091202 this is a factorization-preserving isomorphism from integers to GF(2)[X]-polynomials. The latter 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 primes (A000040) straight to the irreducible GF(2)[X] polynomials (A014580), but instead fixes the intersection of those two sets (A091206), and maps the elements in their set-wise difference A000040 \ A014580 (= A091209) in numerical order to the set-wise difference A014580 \ A000040 (= A091214).

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

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

%H Antti Karttunen, <a href="/A235041/b235041.txt">Table of n, a(n) for n = 0..10000</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 primes p whose binary representations encode also irreducible GF(2)[X]-polynomials (i.e., p is in A091206), and for the rest of the primes q (those whose binary representation encode composite GF(2)[X]-polynomials, i.e., q is in A091209), a(q) = A091214(A235043(q)), and for composite natural numbers, a(p * q * r * ...) = a(p) X a(q) X a(r) X ..., where p, q, r, ... are primes and X stands for the carryless multiplication (A048720) of GF(2)[X] polynomials encoded as explained in the Comments section.

%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*2) = a(2) X a(2) = 2 X 2 = 4.

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

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

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

%e Similarly, a(17) = 55, as 17 is the second term of A091209 and 55 is the second term of A091214.

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

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

%o (definec (A235041 n) (cond ((< n 2) n) ((= 1 (A010051 n) (A091225 n)) n) ((= 1 (A010051 n)) (A091214 (A235043 n))) (else (reduce A048720bi 1 (map A235041 (ifactor n)))))) ;; ifactor gives all the prime-divisors of n.

%Y Inverse: A235042. Fixed points: A235045.

%Y Cf. A010051, A048720, A091225, A091214, A235043, A048724, A115857, A115872.

%Y Similar cross-multiplicative permutations: A091202, A091204, A106442, A106444, A106446.

%K nonn

%O 0,3

%A _Antti Karttunen_, Jan 02 2014