A305437 Running index for the lexicographically least irreducible factor when (0,1)-polynomial obtained from the binary expansion of n is factored over Q.

1, 2, 3, 2, 4, 2, 5, 2, 3, 2, 6, 2, 7, 2, 3, 2, 8, 2, 9, 2, 10, 2, 11, 2, 12, 2, 3, 2, 13, 2, 14, 2, 3, 2, 5, 2, 15, 2, 3, 2, 16, 2, 17, 2, 3, 2, 18, 2, 5, 2, 3, 2, 19, 2, 20, 2, 3, 2, 21, 2, 22, 2, 3, 2, 4, 2, 23, 2, 24, 2, 25, 2, 26, 2, 3, 2, 27, 2, 28, 2, 29, 2, 30, 2, 4, 2, 31, 2, 32, 2, 33, 2, 10, 2, 4, 2, 34, 2, 3, 2, 35, 2, 36, 2, 3

Offset: 1

Author

Antti Karttunen, Jun 09 2018

Keywords

• nonn

Examples

			Numbers 1 .. 6 encode the following (0,1)-polynomials by their binary representation:
  1 -> 1       [Empty factorization]
  2 -> x       [Irreducible, the only and thus also the least factor is x]
  3 -> x + 1   [Irreducible, the least factor is (x+1)]
  4 -> x^2      = (x)(x)   [The least factor (x) occurred already for the first time at n=2, thus a(4) = 2.]
  5 -> x^2 + 1 [Irreducible, the least factor is (x^2 + 1)]
  6 -> x^2 + x  = (x)(x+1) [The least factor (x) occurred already at n=2, thus a(6) = 2.]
Binary representation of 7 is "111", encoding (0,1)-polynomial x^2 + x + 1, which is irreducible over Q, so it is the first time that polynomial occurs as a "smallest" (lexicographically least) irreducible factor, while before it, already four different kinds of "smallest" factors have occurred, thus a(7) = 5.
The second time the same factor occurs as the smallest one is for n=35, whose binary representation "100011" encodes polynomial x^5 + x + 1 = (x^2 + x + 1)(x^3 - x^2 + 1) , thus a(35) = 5 also.
The third time the same factor occurs as the smallest one is for n=49, whose binary representation "110001" encodes polynomial x^5 + x^4 + 1 = (x^2 + x + 1)(x^3 - x + 1), thus a(49) = 5 also.
		

Links

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

Crossrefs

Cf. A206074, A305300.

Cf. A305438 (ordinal transform).

Cf. also A055396, A302786.

Programs

PARI

allocatemem(2^30);
default(parisizemax,2^31);
up_to = 65537;
rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
pollexcmp(a,b) = { my(ad = poldegree(a), bd = poldegree(b),e); if(ad != bd, return(sign(ad-bd))); for(i=0,ad,e = polcoeff(a,ad-i) - polcoeff(b,ad-i); if(0!=e, return(sign(e)))); (0); };
lexleastpolfactor(n) = if(1==n,0,my(fs = factor(Pol(binary(n)))[,1]~); vecsort(fs,pollexcmp)[1]);
v305437 = rgs_transform(vector(up_to,n,lexleastpolfactor(n)));
A305437(n) = v305437[n];