cp's OEIS Frontend

A091205 Factorization and index-recursion preserving isomorphism from binary codes of GF(2) polynomials to integers.

%I A091205 #34 Jun 17 2015 09:30:21
%S A091205 0,1,2,3,4,9,6,5,8,15,18,7,12,23,10,27,16,81,30,13,36,25,14,69,24,11,
%T A091205 46,45,20,21,54,19,32,57,162,115,60,47,26,63,72,61,50,33,28,135,138,
%U A091205 17,48,35,22,243,92,39,90,37,40,207,42,83,108,29,38,75,64,225,114,103
%N A091205 Factorization and index-recursion preserving isomorphism from binary codes of GF(2) polynomials to integers.
%C A091205 This "deeply multiplicative" bijection is one of the deep variants of A091203 which satisfy most of the same identities as the latter, but it additionally preserves also the structures where we recurse on irreducible polynomial's A014580-index. E.g., we have: A091238(n) = A061775(a(n)). The reason this holds is that when the permutation is restricted to the binary codes for irreducible polynomials over GF(2) (A014580), it induces itself: a(n) = A049084(a(A014580(n))).
%C A091205 On the other hand, when this permutation is restricted to the union of {1} and reducible polynomials over GF(2) (A091242), permutation A245813 is induced.
%H A091205 Antti Karttunen, <a href="/A091205/b091205.txt">Table of n, a(n) for n = 0..8192</a>
%H A091205 A. Karttunen, <a href="/A091247/a091247.scm.txt">Scheme-program for computing this sequence.</a>
%H A091205 <a href="/index/Ge#GF2X">Index entries for sequences operating on GF(2)[X]-polynomials</a>
%H A091205 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A091205 a(0)=0, a(1)=1. For n that is coding an irreducible polynomial, that is if n = A014580(i), we have a(n) = A000040(a(i)) and for reducible polynomials a(ir_i X ir_j X ...) = a(ir_i) * a(ir_j) * ..., where ir_i = A014580(i), X stands for carryless multiplication of polynomials over GF(2) (A048720) and * for the ordinary multiplication of integers (A004247).
%F A091205 As a composition of related permutations:
%F A091205 a(n) = A245821(A245704(n)).
%F A091205 Other identities.
%F A091205 For all n >= 0, the following holds:
%F A091205 a(A091230(n)) = A007097(n). [Maps iterates of A014580 to the iterates of primes. Permutation A245704 has the same property.]
%F A091205 For all n >= 1, the following holds:
%F A091205 A010051(a(n)) = A091225(n). [After a(1)=1, maps binary representations of irreducible GF(2) polynomials, A014580, bijectively to primes and the binary representations of corresponding reducible polynomials, A091242, to composite numbers, in some order. The permutations A091203, A106443, A106445, A106447, A235042 and A245704 have the same property.]
%o A091205 (PARI)
%o A091205 allocatemem(123456789);
%o A091205 v091226 = vector(2^22);
%o A091205 isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from _Charles R Greathouse IV_
%o A091205 n=2; while((n < 2^22), if(isA014580(n), v091226[n] = v091226[n-1]+1, v091226[n] = v091226[n-1]); n++)
%o A091205 A091226(n) = v091226[n];
%o A091205 A091205(n) = if(n<=1,n,if(isA014580(n),prime(A091205(A091226(n))),{my(irfs,t); irfs=subst(lift(factor(Mod(1,2)*Pol(binary(n)))),x,2); irfs[,1]=apply(t->A091205(t),irfs[,1]); factorback(irfs)}));
%o A091205 for(n=0, 8192, write("b091205.txt", n, " ", A091205(n)));
%o A091205 \\ _Antti Karttunen_, Aug 16 2014
%Y A091205 Inverse: A091204.
%Y A091205 Similar or related permutations: A091203, A106443, A106445, A106447, A235042, A245704, A245813, A245821.
%Y A091205 Cf. A000040, A007097, A010051, A014580, A049084, A061775, A091238, A091225, A091226, A091230, A091242.
%K A091205 nonn
%O A091205 0,3
%A A091205 _Antti Karttunen_, Jan 03 2004
%E A091205 Name changed by _Antti Karttunen_, Aug 16 2014