cp's OEIS Frontend

A091203 Factorization-preserving isomorphism from binary codes of GF(2) polynomials to integers.

%I A091203 #26 Jun 10 2018 21:14:06
%S A091203 0,1,2,3,4,9,6,5,8,15,18,7,12,11,10,27,16,81,30,13,36,25,14,33,24,17,
%T A091203 22,45,20,21,54,19,32,57,162,55,60,23,26,63,72,29,50,51,28,135,66,31,
%U A091203 48,35,34,243,44,39,90,37,40,99,42,41,108,43,38,75,64,225,114,47,324
%N A091203 Factorization-preserving isomorphism from binary codes of GF(2) polynomials to integers.
%C A091203 E.g. we have the following identities: A000040(n) = a(A014580(n)), 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)), A091227(n) = A049084(a(n)), A091247(n) = A066247(a(n)).
%H A091203 Antti Karttunen, <a href="/A091203/b091203.txt">Table of n, a(n) for n = 0..8192</a>
%H A091203 A. Karttunen, <a href="/A091247/a091247.scm.txt">Scheme-program for computing this sequence.</a>
%H A091203 <a href="/index/Ge#GF2X">Index entries for sequences operating on GF(2)[X]-polynomials</a>
%H A091203 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A091203 a(0)=0, a(1)=1. For n's coding an irreducible polynomial ir_i, that is if n=A014580(i), we have a(n) = A000040(i) and for composite polynomials a(ir_i X ir_j X ...) = p_i * p_j * ..., where p_i = A000040(i) and X stands for carryless multiplication of GF(2)[X] polynomials (A048720) and * for the ordinary multiplication of integers (A004247).
%F A091203 Other identities. For all n >= 1, the following holds:
%F A091203 A010051(a(n)) = A091225(n). [After a(1)=1, maps binary representations of irreducible GF(2) polynomials, A014580, to primes and the binary representations of corresponding reducible polynomials, A091242, to composite numbers. The permutations A091205, A106443, A106445, A106447, A235042 and A245704 have the same property.]
%F A091203 From _Antti Karttunen_, Jun 10 2018: (Start)
%F A091203 For n <= 1, a(n) = n, for n > 1, a(n) = 2*a(n/2) if n is even, and if n is odd, then a(n) = A003961(a(A305422(n))).
%F A091203 a(n) = A005940(1+A305418(n)) = A163511(A305428(n)).
%F A091203 A046523(a(n)) = A278233(n).
%F A091203 (End)
%o A091203 (PARI)
%o A091203 A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ From A003961
%o A091203 A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
%o A091203 A305419(n) = if(n<3,1, my(k=n-1); while(k>1 && !A091225(k),k--); (k));
%o A091203 A305422(n) = { my(f = subst(lift(factor(Pol(binary(n))*Mod(1, 2))),x,2)); for(i=1,#f~,f[i,1] = Pol(binary(A305419(f[i,1])))); fromdigits(Vec(factorback(f))%2,2); };
%o A091203 A091203(n) = if(n<=1,n,if(!(n%2),2*A091203(n/2),A003961(A091203(A305422(n))))); \\ _Antti Karttunen_, Jun 10 2018
%Y A091203 Inverse: A091202.
%Y A091203 Several variants exist: A235042, A091205, A106443, A106445, A106447.
%Y A091203 Cf. also A000005, A000040, A001221, A001222, A004247, A008683, A010051, A014580, A048720, A049084, A066247, A091219, A091220, A091221, A091222, A091225, A091227, A091247, A234741, A234742, A245703, A245704, A278233.
%Y A091203 Cf. also A302024, A302026, A305418, A305428 for other similar permutations.
%K A091203 nonn
%O A091203 0,3
%A A091203 _Antti Karttunen_, Jan 03 2004