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

%I #26 Jun 10 2018 21:14:06

%S 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 22,45,20,21,54,19,32,57,162,55,60,23,26,63,72,29,50,51,28,135,66,31,

%U 48,35,34,243,44,39,90,37,40,99,42,41,108,43,38,75,64,225,114,47,324

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

%C 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 Antti Karttunen, <a href="/A091203/b091203.txt">Table of n, a(n) for n = 0..8192</a>

%H A. Karttunen, <a href="/A091247/a091247.scm.txt">Scheme-program for computing this sequence.</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. 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 Other identities. For all n >= 1, the following holds:

%F 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 From _Antti Karttunen_, Jun 10 2018: (Start)

%F 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 a(n) = A005940(1+A305418(n)) = A163511(A305428(n)).

%F A046523(a(n)) = A278233(n).

%F (End)

%o (PARI)

%o A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ From A003961

%o A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));

%o A305419(n) = if(n<3,1, my(k=n-1); while(k>1 && !A091225(k),k--); (k));

%o 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(n) = if(n<=1,n,if(!(n%2),2*A091203(n/2),A003961(A091203(A305422(n))))); \\ _Antti Karttunen_, Jun 10 2018

%Y Inverse: A091202.

%Y Several variants exist: A235042, A091205, A106443, A106445, A106447.

%Y 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 Cf. also A302024, A302026, A305418, A305428 for other similar permutations.

%K nonn

%O 0,3

%A _Antti Karttunen_, Jan 03 2004