

A305437


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


3



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


LINKS

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


EXAMPLE

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.


PROG

(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(adbd))); for(i=0, ad, e = polcoeff(a, adi)  polcoeff(b, adi); 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];


CROSSREFS

Cf. A206074, A305300.
Cf. A305438 (ordinal transform).
Cf. also A055396, A302786.
Sequence in context: A162322 A336155 A196930 * A111982 A323236 A319702
Adjacent sequences: A305434 A305435 A305436 * A305438 A305439 A305440


KEYWORD

nonn


AUTHOR

Antti Karttunen, Jun 09 2018


STATUS

approved



