|
%I #36 Mar 02 2019 03:03:41
%S 1,3,7,27,15,21,31,45,73,91,129,85,63,93,105,275,257,219,127,189,217,
%T 453,441,357,601,741,273,837,1191,981,513,645,903,949,255,315,1649,
%U 341,1103,1235,455,651,657,1443,775,2795,825,1925,1911,771
%N 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.
%C Example: the polynomial x^1649 + 1 over GF(2) is the product of 37 irreducible factors.
%C 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
%D R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983, p. 65.
%H Robert G. Wilson v, <a href="/A175198/b175198.txt">Table of n, a(n) for n = 1..10000</a> (first 300 terms from Charles R Greathouse IV)
%H Eric Weisstein's World on Math, <a href="http://mathworld.wolfram.com/IrreduciblePolynomial.html">Irreducible Polynomial</a>
%F A000005(a(n)) <= n <= a(n). - _Robert Israel_, Feb 07 2018
%e For n=1, x+1 is irreducible hence a(1) = 1.
%e For n=2, x^3 + 1 = (x+1)(x^2+x+1) mod 2 hence a(2) = 3.
%e For n=3, x^7 + 1 = (x+1)(x^3 + x^2 + 1)(x^3 + x + 1) mod 2 hence a(3) = 7.
%e 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.
%e 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.
%p 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:
%t 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 *)
%t 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 *)
%o (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
%Y Cf. A023135, A000005, A000374, A023136-A023142.
%K nonn
%O 1,2
%A _Michel Lagneau_, Mar 02 2010
%E Name corrected by _Charles R Greathouse IV_, Jan 28 2018
|
