login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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(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];

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 18 11:20 EDT 2021. Contains 347518 sequences. (Running on oeis4.)