A305421 GF(2)[X] factorization prime shift towards larger terms.

1, 3, 7, 5, 21, 9, 11, 15, 49, 63, 13, 27, 19, 29, 107, 17, 273, 83, 25, 65, 69, 23, 121, 45, 31, 53, 151, 39, 35, 189, 37, 51, 251, 819, 173, 245, 41, 43, 233, 195, 47, 207, 93, 57, 997, 139, 55, 119, 127, 33, 1911, 95, 79, 441, 59, 105, 367, 101, 61, 455, 67, 111, 475, 85, 1281, 269, 73, 1365, 81, 503, 457, 287, 87, 123, 1549, 125, 179, 315

Offset: 1

Author

Antti Karttunen, Jun 07 2018

Keywords

• nonn

Comments

Permutation of the odd numbers, A005408.

Let a x b stand for the carryless binary multiplication of positive integers a and b, that is, the result of operation A048720(a,b). With n having a unique factorization as A014580(i) x A014580(j) x ... x A014580(k), 1 <= i <= j <= ... <= k, a(n) = A014580(1+i) x A014580(1+j) x ... x A014580(1+k).

Examples

			For n = 12, which by its binary representation '1100' corresponds with (0,1)-polynomial x^3 + x^2, which over GF(2)[X] is factored as (x)(x)(x+1), i.e., 12 = A048720(2,A048720(2,3)) = A048720(A014580(1), A048720(A014580(1),A014580(2))), we then form a(12) as A048720(A014580(2), A048720(A014580(2),A014580(3))) = A048720(3,A048720(3,7)) = 27. Note that x, x+1 and x^2 + x + 1 are the three smallest irreducible (0,1)-polynomials when factored over GF(2)[X], and their binary representations 2, 3 and 7 are the three initial terms of A014580.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..21845
• Index entries for sequences related to polynomials in ring GF(2)[X]

Crossrefs

Cf. A305422 (a left inverse).

Cf. A001317, A014580, A091225, A193231, A268389, A305420, A305423.

Cf. also A003961, A300841.

Programs

PARI

A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
A305420(n) = { my(k=1+n); while(!A091225(k),k++); (k); };
A305421(n) = { my(f = subst(lift(factor(Pol(binary(n))*Mod(1, 2))),x,2)); for(i=1,#f~,f[i,1] = Pol(binary(A305420(f[i,1])))); fromdigits(Vec(factorback(f))%2,2); };

Formula

For all n >= 1:

A305422(a(n)) = n.

A268389(a(n)) = A007814(n).

a(A000079(n)) = A001317(n).