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!)
A175198 a(n) is the smallest integer k such that the polynomial x^k + 1 over the integers mod 2 has exactly n distinct irreducible factors. 1
1, 3, 7, 27, 15, 21, 31, 45, 73, 91, 129, 85, 63, 93, 105, 275, 257, 219, 127, 189, 217, 453, 441, 357, 601, 741, 273, 837, 1191, 981, 513, 645, 903, 949, 255, 315, 1649, 341, 1103, 1235, 455, 651, 657, 1443, 775, 2795, 825, 1925, 1911, 771 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Example: the polynomial x^1649 + 1 over GF(2) is the product of 37 irreducible factors.

Records: 1, 3, 7, 27, 31, 45, 73, 91, 129, 275, 453, 601, 741, 837, 1191, 1649, 2795, 3045, 3913, 3955, 10719, 18875, 48631, 73143, 76373, 126191, 189061, 210105, 216481, 249891, 303021, 896041, 961185, 1063997, 1759603, 2555521, 3492783, 3923381, 5276409, 5529727, 6663515, 7234645, 8761553, 10488401, 11636993, 12290949, 20936365, 25099273, 25821285, 28081875, 28623469, 32848947, 48539883, 58885551, ..., . - Robert G. Wilson v, Feb 07 2018

REFERENCES

R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983, p. 65.

LINKS

Robert G. Wilson v, Table of n, a(n) for n = 1..10000 (first 300 terms from Charles R Greathouse IV)

Eric Weisstein's World on Math, Irreducible Polynomial

FORMULA

A000005(a(n)) <= n <= a(n). - Robert Israel, Feb 07 2018

EXAMPLE

For n=1, x+1 is irreducible hence a(1) = 1.

For n=2, x^3 + 1 = (x+1)(x^2+x+1) mod 2 hence a(2) = 3.

For n=3, x^7 + 1 = (x+1)(x^3 + x^2 + 1)(x^3 + x + 1) mod 2 hence a(3) = 7.

For n=4, x^27 + 1 = (x+1)(x^2 + x + 1)(x^18 + x^9 + 1)(x^6 + x^3 + 1) mod 2 hence a(4) = 27.

For n=5, x^15 + 1 = (x+1)(x^4 + x^3 + x^2 + x + 1)(x^2 + x + 1)(x^4 + x^3 + 1)(x^4 + x + 1) mod 2 hence a(5) = 15.

MAPLE

with(numtheory):T:=array(0..50000000):U=array(0..50000000 ):nn:=3000: for k from 1 to nn do:liste:=Factors(x^k+ 1) mod 2; t1 := liste[2]:t2:=(liste[2][i], i=1..nops(t1)):a :=nops(t1):T[k]:=a:U[k]:=k:od:mini:=T[1]:ii:=1: print(mini):for p from 1 to nn-1 do:for n from 1 to nn-1 do:if T[n] < mini then mini:= T[n]:ii:=n: indice:=U[n]: else fi:od:print(indice):print(mini):T[ii]:= 99999999: ii:=1:mini:=T[1] :od:

MATHEMATICA

With[{s = Array[Length@ FactorList[#, Modulus -> 2] &[x^# + 1] &, 500]}, Array[FirstPosition[s, #][[1]] &, 1 + LengthWhile[Differences@ #, # == 1 &], 2] &@ Union@ s] (* Michael De Vlieger, Feb 05 2018 *)

CountFactors[p_, n_] := CountFactors[p, n] = Module[{sum = 0, m = n, d, f, i}, While[ Mod[m, p] == 0, m /= p]; d = Divisors[m]; Do[f = d[[i]]; sum += EulerPhi[f]/MultiplicativeOrder[p, f], {i, Length[d]}]; sum](*after Shel Kaphan from A000374*); f[n_] := Block[{k = 1}, While[CountFactors[2, k] != n, k++]; k]; Array[f, 60] (* Robert G. Wilson v, Feb 07 2018 *)

PROG

(PARI) first(n)=my(v=vector(n), left=n, k, t); while(left, t=#factor(Mod('x^k+++1, 2))~; if(t<=n && v[t]==0, v[t]=k; left--)); v \\ Charles R Greathouse IV, Jan 28 2018

CROSSREFS

Cf. A023135, A000005, A000374, A023136-A023142.

Sequence in context: A019059 A305446 A334793 * A272530 A225038 A293564

Adjacent sequences:  A175195 A175196 A175197 * A175199 A175200 A175201

KEYWORD

nonn

AUTHOR

Michel Lagneau, Mar 02 2010

EXTENSIONS

Name corrected by Charles R Greathouse IV, Jan 28 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 May 12 02:23 EDT 2021. Contains 343808 sequences. (Running on oeis4.)