A091202 - OEIS

%I #21 Jun 10 2018 21:13:59

%S 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 38,15,44,41,18,47,32,23,50,49,20,55,62,53,56,59,58,61,52,27,74,67,48,

%U 69,42,43,76,73,30,35,88,33,82,87,36,91,94,39,64,121,46,97,100,111,98

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

%C 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 Antti Karttunen, <a href="/A091202/b091202.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, 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 Other identities. For all n >= 1, the following holds:

%F 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 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) = A305421(a(A064989(n))).

%F a(n) = A305417(A156552(n)) = A305427(A243071(n)).

%F (End)

%o (PARI)

%o 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 A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));

%o A305420(n) = { my(k=1+n); while(!A091225(k),k++); (k); };

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

%Y Inverse: A091203.

%Y Several variants exist: A235041, A091204, A106442, A106444, A106446.

%Y Cf. also A000005, A091220, A001221, A091221, A001222, A091222, A008683, A091219, A000040, A014580, A048720, A049084, A091227, A245703, A234741.

%Y Cf. also A302023, A302025, A305417, A305427 for other similar permutations.

%K nonn,look

%O 0,3

%A _Antti Karttunen_, Jan 03 2004