cp's OEIS Frontend

A091202 Factorization-preserving isomorphism from nonnegative integers to binary codes for polynomials over GF(2).

%I A091202 #21 Jun 10 2018 21:13:59
%S A091202 0,1,2,3,4,7,6,11,8,5,14,13,12,19,22,9,16,25,10,31,28,29,26,37,24,21,
%T A091202 38,15,44,41,18,47,32,23,50,49,20,55,62,53,56,59,58,61,52,27,74,67,48,
%U A091202 69,42,43,76,73,30,35,88,33,82,87,36,91,94,39,64,121,46,97,100,111,98
%N A091202 Factorization-preserving isomorphism from nonnegative integers to binary codes for polynomials over GF(2).
%C A091202 E.g. we have the following identities: A000005(n) = A091220(a(n)), A001221(n) = A091221(a(n)), A001222(n) = A091222(a(n)), A008683(n) = A091219(a(n)), A014580(n) = a(A000040(n)), A049084(n) = A091227(a(n)).
%H A091202 Antti Karttunen, <a href="/A091202/b091202.txt">Table of n, a(n) for n = 0..8192</a>
%H A091202 A. Karttunen, <a href="/A091247/a091247.scm.txt">Scheme-program for computing this sequence.</a>
%H A091202 <a href="/index/Ge#GF2X">Index entries for sequences operating on GF(2)[X]-polynomials</a>
%H A091202 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A091202 a(0)=0, a(1)=1, a(p_i) = A014580(i) for primes p_i with index i and for composites a(p_i * p_j * ...) = a(p_i) X a(p_j) X ..., where X stands for carryless multiplication of GF(2)[X] polynomials (A048720).
%F A091202 Other identities. For all n >= 1, the following holds:
%F A091202 A091225(a(n)) = A010051(n). [Maps primes to binary representations of irreducible GF(2) polynomials, A014580, and nonprimes to union of {1} and the binary representations of corresponding reducible polynomials, A091242. The permutations A091204, A106442, A106444, A106446, A235041 and A245703 have the same property.]
%F A091202 From _Antti Karttunen_, Jun 10 2018: (Start)
%F A091202 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) = A305421(a(A064989(n))).
%F A091202 a(n) = A305417(A156552(n)) = A305427(A243071(n)).
%F A091202 (End)
%o A091202 (PARI)
%o A091202 A064989(n) = {my(f); f = factor(n); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f)};
%o A091202 A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
%o A091202 A305420(n) = { my(k=1+n); while(!A091225(k),k++); (k); };
%o A091202 A305421(n) = { my(f = subst(lift(factor(Pol(binary(n))*Mod(1, 2))),x,2)); for(i=1,#f~,f[i,1] = Pol(binary(A305420(f[i,1])))); fromdigits(Vec(factorback(f))%2,2); };
%o A091202 A091202(n) = if(n<=1,n,if(!(n%2),2*A091202(n/2),A305421(A091202(A064989(n))))); \\ _Antti Karttunen_, Jun 10 2018
%Y A091202 Inverse: A091203.
%Y A091202 Several variants exist: A235041, A091204, A106442, A106444, A106446.
%Y A091202 Cf. also A000005, A091220, A001221, A091221, A001222, A091222, A008683, A091219, A000040, A014580, A048720, A049084, A091227, A245703, A234741.
%Y A091202 Cf. also A302023, A302025, A305417, A305427 for other similar permutations.
%K A091202 nonn,look
%O A091202 0,3
%A A091202 _Antti Karttunen_, Jan 03 2004