|
%I #14 Jun 09 2018 19:00:28
%S 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,
%T 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,
%U 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
%N Running index for the lexicographically least irreducible factor when (0,1)-polynomial obtained from the binary expansion of n is factored over Q.
%H Antti Karttunen, <a href="/A305437/b305437.txt">Table of n, a(n) for n = 1..65537</a>
%e Numbers 1 .. 6 encode the following (0,1)-polynomials by their binary representation:
%e 1 -> 1 [Empty factorization]
%e 2 -> x [Irreducible, the only and thus also the least factor is x]
%e 3 -> x + 1 [Irreducible, the least factor is (x+1)]
%e 4 -> x^2 = (x)(x) [The least factor (x) occurred already for the first time at n=2, thus a(4) = 2.]
%e 5 -> x^2 + 1 [Irreducible, the least factor is (x^2 + 1)]
%e 6 -> x^2 + x = (x)(x+1) [The least factor (x) occurred already at n=2, thus a(6) = 2.]
%e 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.
%e 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.
%e 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.
%o (PARI)
%o allocatemem(2^30);
%o default(parisizemax,2^31);
%o up_to = 65537;
%o 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; };
%o 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); };
%o lexleastpolfactor(n) = if(1==n,0,my(fs = factor(Pol(binary(n)))[,1]~); vecsort(fs,pollexcmp)[1]);
%o v305437 = rgs_transform(vector(up_to,n,lexleastpolfactor(n)));
%o A305437(n) = v305437[n];
%Y Cf. A206074, A305300.
%Y Cf. A305438 (ordinal transform).
%Y Cf. also A055396, A302786.
%K nonn
%O 1,2
%A _Antti Karttunen_, Jun 09 2018
|
