

A235041


Factorizationpreserving bijection from nonnegative integers to GF(2)[X]polynomials, version which fixes the elements that are irreducible in both semirings.


13



0, 1, 2, 3, 4, 25, 6, 7, 8, 5, 50, 11, 12, 13, 14, 43, 16, 55, 10, 19, 100, 9, 22, 87, 24, 321, 26, 15, 28, 91, 86, 31, 32, 29, 110, 79, 20, 37, 38, 23, 200, 41, 18, 115, 44, 125, 174, 47, 48, 21, 642, 89, 52, 117, 30, 227, 56, 53, 182, 59, 172, 61, 62, 27, 64
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Like A091202 this is a factorizationpreserving isomorphism from integers to GF(2)[X]polynomials. The latter are encoded in the binary representation of n like this: n=11, '1011' in binary, stands for polynomial x^3+x+1, n=25, '11001' in binary, stands for polynomial x^4+x^3+1. However, this version does not map the primes (A000040) straight to the irreducible GF(2)[X] polynomials (A014580), but instead fixes the intersection of those two sets (A091206), and maps the elements in their setwise difference A000040 \ A014580 (= A091209) in numerical order to the setwise difference A014580 \ A000040 (= A091214).
The composite values are defined by the multiplicativity. E.g., we have a(3n) = A048724(a(n)) and a(3^n) = A001317(n) for all n.
This map satisfies many of the same identities as A091202, e.g., we have A000005(n) = A091220(a(n)), A001221(n) = A091221(a(n)), A001222(n) = A091222(a(n)) and A008683(n) = A091219(a(n)) for all n >= 1.


LINKS

Antti Karttunen, Table of n, a(n) for n = 0..10000
Index entries for sequences operating on GF(2)[X]polynomials
Index entries for sequences that are permutations of the natural numbers


FORMULA

a(0)=0, a(1)=1, a(p) = p for those primes p whose binary representations encode also irreducible GF(2)[X]polynomials (i.e., p is in A091206), and for the rest of the primes q (those whose binary representation encode composite GF(2)[X]polynomials, i.e., q is in A091209), a(q) = A091214(A235043(q)), and for composite natural numbers, a(p * q * r * ...) = a(p) X a(q) X a(r) X ..., where p, q, r, ... are primes and X stands for the carryless multiplication (A048720) of GF(2)[X] polynomials encoded as explained in the Comments section.


EXAMPLE

Here (t X u) = A048720(t,u):
a(2)=2, a(3)=3 and a(7)=7, as 2, 3 and 7 are all in A091206.
a(4) = a(2*2) = a(2) X a(2) = 2 X 2 = 4.
a(9) = a(3*3) = a(3) X a(3) = 3 X 3 = 5.
a(5) = 25, as 5 is the first term of A091209 and 25 is the first term of A091214.
a(10) = a(2*5) = a(2) X a(5) = 2 X 25 = 50.
Similarly, a(17) = 55, as 17 is the second term of A091209 and 55 is the second term of A091214.
a(21) = a(3*7) = a(3) X a(7) = 3 X 7 = 9.


PROG

(Scheme, with Antti Karttunen's IntSeqlibrary)
(definec (A235041 n) (cond ((< n 2) n) ((= 1 (A010051 n) (A091225 n)) n) ((= 1 (A010051 n)) (A091214 (A235043 n))) (else (reduce A048720bi 1 (map A235041 (ifactor n)))))) ;; ifactor gives all the primedivisors of n.


CROSSREFS

Inverse: A235042. Fixed points: A235045.
Cf. A010051, A048720, A091225, A091214, A235043, A048724, A115857, A115872.
Similar crossmultiplicative permutations: A091202, A091204, A106442, A106444, A106446.
Sequence in context: A265484 A000336 A287433 * A080613 A055006 A139050
Adjacent sequences: A235038 A235039 A235040 * A235042 A235043 A235044


KEYWORD

nonn


AUTHOR

Antti Karttunen, Jan 02 2014


STATUS

approved



