OFFSET
0,3
COMMENTS
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))).
LINKS
FORMULA
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).
As a composition of related permutations:
Other identities.
For all n >= 0, the following holds:
a(A091230(n)) = A007097(n). [Maps iterates of A014580 to the iterates of primes. Permutation A245704 has the same property.]
For all n >= 1, the following holds:
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.]
PROG
(PARI)
allocatemem(123456789);
v091226 = vector(2^22);
isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from Charles R Greathouse IV
n=2; while((n < 2^22), if(isA014580(n), v091226[n] = v091226[n-1]+1, v091226[n] = v091226[n-1]); n++)
A091226(n) = v091226[n];
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)}));
for(n=0, 8192, write("b091205.txt", n, " ", A091205(n)));
\\ Antti Karttunen, Aug 16 2014
CROSSREFS
KEYWORD
nonn
AUTHOR
Antti Karttunen, Jan 03 2004
EXTENSIONS
Name changed by Antti Karttunen, Aug 16 2014
STATUS
approved