cp's OEIS Frontend

A091204 Factorization and index-recursion preserving isomorphism from nonnegative integers to polynomials over GF(2).

%I A091204 #25 Aug 18 2014 00:50:46
%S A091204 0,1,2,3,4,7,6,11,8,5,14,25,12,19,22,9,16,47,10,31,28,29,50,13,24,21,
%T A091204 38,15,44,61,18,137,32,43,94,49,20,55,62,53,56,97,58,115,100,27,26,37,
%U A091204 48,69,42,113,76,73,30,79,88,33,122,319,36,41,274,39,64,121,86,185
%N A091204 Factorization and index-recursion preserving isomorphism from nonnegative integers to polynomials over GF(2).
%C A091204 This "deeply multiplicative" isomorphism is one of the deep variants of A091202 which satisfies most of the same identities as the latter, but it additionally preserves also the structures where we recurse on prime's index. E.g. we have: A091230(n) = a(A007097(n)) and A061775(n) = A091238(a(n)). This is because the permutation induces itself when it is restricted to the primes: a(n) = A091227(a(A000040(n))).
%C A091204 On the other hand, when this permutation is restricted to the nonprime numbers (A018252), permutation A245814 is induced.
%H A091204 Antti Karttunen, <a href="/A091204/b091204.txt">Table of n, a(n) for n = 0..8192</a>
%H A091204 A. Karttunen, <a href="/A091247/a091247.scm.txt">Scheme-program for computing this sequence.</a>
%H A091204 <a href="/index/Ge#GF2X">Index entries for sequences operating on GF(2)[X]-polynomials</a>
%H A091204 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A091204 a(0)=0, a(1)=1, a(p_i) = A014580(a(i)) for primes 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 A091204 As a composition of related permutations:
%F A091204 a(n) = A245703(A245822(n)).
%F A091204 Other identities.
%F A091204 For all n >= 0, the following holds:
%F A091204 a(A007097(n)) = A091230(n). [Maps iterates of primes to the iterates of A014580. Permutation A245703 has the same property]
%F A091204 For all n >= 1, the following holds:
%F A091204 A091225(a(n)) = A010051(n). [Maps primes bijectively to binary representations of irreducible GF(2) polynomials, A014580, and nonprimes to union of {1} and the binary representations of corresponding reducible polynomials, A091242, in some order. The permutations A091202, A106442, A106444, A106446, A235041 and A245703 have the same property.]
%o A091204 (PARI)
%o A091204 v014580 = vector(2^18); A014580(n) = v014580[n];
%o A091204 isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from _Charles R Greathouse IV_
%o A091204 i=0; n=2; while((n < 2^22), if(isA014580(n), i++; v014580[i] = n); n++)
%o A091204 A091204(n) = if(n<=1, n, if(isprime(n), A014580(A091204(primepi(n))), {my(pfs, t, bits, i); pfs=factor(n); pfs[,1]=apply(t->Pol(binary(A091204(t))), pfs[,1]); sum(i=1, #bits=Vec(factorback(pfs))%2, bits[i]<<(#bits-i))}));
%o A091204 for(n=0, 8192, write("b091204.txt", n, " ", A091204(n)));
%o A091204 \\ _Antti Karttunen_, Aug 16 2014
%Y A091204 Inverse: A091205.
%Y A091204 Similar or related permutations: A091202, A106442, A106444, A106446, A235041, A245703, A245814, A245822.
%Y A091204 Cf. A000040, A007097, A010051, A014580, A018252, A048720, A061775, A091225, A091230, A091238, A091242.
%K A091204 nonn
%O A091204 0,3
%A A091204 _Antti Karttunen_, Jan 03 2004. Name changed Aug 16 2014