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

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

Offset

0,3

Comments

Like A091202 this is a factorization-preserving 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 set-wise difference A000040 \ A014580 (= A091209) in numerical order to the set-wise 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 IntSeq-library)
(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 prime-divisors of n.

Crossrefs

Inverse: A235042. Fixed points: A235045.

Cf. A010051, A048720, A091225, A091214, A235043, A048724, A115857, A115872.

Similar cross-multiplicative 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