A235041 -id:A235041 - cp's OEIS frontend

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

0, 1, 2, 3, 4, 9, 6, 7, 8, 21, 18, 11, 12, 13, 14, 27, 16, 81, 42, 19, 36, 49, 22, 39, 24, 5, 26, 63, 28, 33, 54, 31, 32, 93, 162, 91, 84, 37, 38, 99, 72, 41, 98, 15, 44, 189, 78, 47, 48, 77, 10, 243, 52, 57, 126, 17, 56, 117, 66, 59, 108, 61, 62, 147, 64, 441

Offset: 0

Antti Karttunen, Jan 02 2014

nonn

Like A091203 this is a factorization-preserving isomorphism from GF(2)[X]-polynomials to integers. The former 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 irreducible GF(2)[X] polynomials (A014580) straight to the primes (A000040), but instead fixes the intersection of those two sets (A091206), and maps the elements in their set-wise difference A014580 \ A000040 (= A091214) in numerical order to the set-wise difference A000040 \ A014580 (= A091209).
The composite values are defined by the multiplicativity. E.g., we have a(A048724(n)) = 3*a(n) and a(A001317(n)) = A000244(n) = 3^n for all n.
This map satisfies many of the same identities as A091203, e.g., we have A091219(n) = A008683(a(n)), A091220(n) = A000005(a(n)), A091221(n) = A001221(a(n)), A091222(n) = A001222(a(n)), A091225(n) = A010051(a(n)) and A091247(n) = A066247(a(n)) for all n >= 1.

			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 X 2) = a(2)*a(2) = 2*2 = 4.
a(5) = a(3 X 3) = a(3)*a(3) = 3*3 = 9.
a(9) = a(3 X 7) = a(3)*a(7) = 3*7 = 21.
a(10) = a(2 X 3 X 3) = a(2)*a(3)*a(3) = 2*3*3 = 18.
a(15) = a(3 X 3 X 3) = a(3)^3 = 3^3 = 27.
a(17) = a(3 X 3 X 3 X 3) = a(3)^4 = 3^4 = 81.
a(21) = a(7 X 7) = a(7)*a(7) = 7*7 = 49.
a(25) = 5, as 25 is the first term of A091214 and 5 is the first term of A091209.
a(50) = a(2 X 25) = a(2)*a(25) = 2*5 = 10.

Inverse: A235041. Fixed points: A235045.
Cf. A010051, A004247, A091225, A091209, A235044.
Similar cross-multiplicative permutations: A091203, A091205, A106443, A106445, A106447.

a(0)=0, a(1)=1, a(p) = p for those irreducible GF(2)[X]-polynomials whose binary encoding is a prime (i.e., p is in A091206), and for the rest of irreducible GF(2)[X]-polynomials (those which are encoded by a composite natural number, i.e., q is in A091214), a(q) = A091209(A235044(q)), and for reducible polynomials, a(i X j X k X ...) = a(i) * a(j) * a(k) * ..., where each i, j, k, ... is in A014580, X stands for carryless multiplication of GF(2)[X] polynomials (A048720) and * for the ordinary multiplication of integers (A004247).

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

Original entry on oeis.org

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, 38, 15, 44, 61, 18, 137, 32, 43, 94, 49, 20, 55, 62, 53, 56, 97, 58, 115, 100, 27, 26, 37, 48, 69, 42, 113, 76, 73, 30, 79, 88, 33, 122, 319, 36, 41, 274, 39, 64, 121, 86, 185

Offset: 0

Antti Karttunen, Jan 03 2004. Name changed Aug 16 2014

nonn

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))).

On the other hand, when this permutation is restricted to the nonprime numbers (A018252), permutation A245814 is induced.

Antti Karttunen, Table of n, a(n) for n = 0..8192
A. Karttunen, Scheme-program for computing this sequence.
Index entries for sequences operating on GF(2)[X]-polynomials
Index entries for sequences that are permutations of the natural numbers

Inverse: A091205.
Similar or related permutations: A091202, A106442, A106444, A106446, A235041, A245703, A245814, A245822.
Cf. A000040, A007097, A010051, A014580, A018252, A048720, A061775, A091225, A091230, A091238, A091242.

v014580 = vector(2^18); A014580(n) = v014580[n];
isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from Charles R Greathouse IV
i=0; n=2; while((n < 2^22), if(isA014580(n), i++; v014580[i] = n); n++)
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))}));
for(n=0, 8192, write("b091204.txt", n, " ", A091204(n)));
\\ Antti Karttunen, Aug 16 2014

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).
As a composition of related permutations:
a(n) = A245703(A245822(n)).
Other identities.
For all n >= 0, the following holds:
a(A007097(n)) = A091230(n). [Maps iterates of primes to the iterates of A014580. Permutation A245703 has the same property]
For all n >= 1, the following holds:
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.]

A235043 Partial sums of the characteristic function of A091209.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10

Offset: 0

Antti Karttunen, Jan 02 2014

nonn

Note that this also works as an inverse function of A091209 in a sense that a(A091209(n)) = n for all n>=1.

Antti Karttunen, Table of n, a(n) for n = 0..10007

Used to compute A235041. Cf. A010051, A091247, A235044.

(define (A235043 n) (if (zero? n) n (+ (A235043 (- n 1)) (+ (* (A010051 n) (A091247 n))))))

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A235043 Partial sums of the characteristic function of A091209.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme