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,2

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

Links

Antti Karttunen, Table of n, a(n) for n = 1..21845

Index entries for sequences related to polynomials in ring GF(2)[X]

Formula

For all n >= 1:

A305422(a(n)) = n.

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

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

Example

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.

Prog

(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); };

Crossrefs

Cf. A305422 (a left inverse).

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

Cf. also A003961, A300841.

Sequence in context: A115765 A282598 A269369 * A354544 A112071 A231609

Adjacent sequences: A305418 A305419 A305420 * A305422 A305423 A305424

Keyword

nonn

Author

Antti Karttunen, Jun 07 2018

Status

approved