|
| |
|
|
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
|
|
|
|
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(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)));
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
