A385678 Least prime p <= n^2 - 2*n + 4 such that the polynomial Sum_{k=1..n} phi(k)*x^(n-k) is irreducible modulo p, or 1 if such p does not exist, where phi is Euler's totient function given by A000010.

1, 2, 3, 1, 1, 7, 31, 13, 67, 7, 67, 13, 53, 7, 11, 19, 101, 239, 37, 23, 13, 103, 263, 89, 79, 29, 47, 23, 167, 317, 139, 73, 283, 7, 223, 71, 83, 29, 1117, 503, 83, 167, 811, 349, 17, 3, 263, 37, 157, 317, 11, 7, 43, 283, 17, 79, 193, 293, 257, 233

Offset: 1

Author

Zhi-Wei Sun, Aug 04 2025

Keywords

• nonn

Comments

Conjecture: a(n) > 1 for all n > 5.

Note that Sum_{k=1..4} phi(k)*x^(4-k) = (x + 1)*(x^2 + 2) and Sum_{k=1..5} phi(k)*x^(5-k) = (x^2 - x + 2)*(x^2 + 2*x + 2).

See also A385658 and A385676 for similar conjectures.

Links

• Zhi-Wei Sun, Table of n, a(n) for n = 1..400

Crossrefs

Cf. A000010, A000040, A385658, A385676.

Programs

Mathematica

P[n_, x_]:=P[n, x]=Sum[EulerPhi[k]*x^(n-k), {k, 1, n}];
tab={};Do[Do[If[IrreduciblePolynomialQ[P[n, x], Modulus->Prime[k]]==True, tab=Append[tab,Prime[k]]; Goto[aa]], {k, 1, PrimePi[n^2-2n+4]}];
tab=Append[tab,1]; Label[aa]; Continue, {n, 1, 60}];Print[tab]

PARI

a(n) = forprime(p=2, n^2 - 2*n + 4, if (polisirreducible(Mod(sum(k=1, n, eulerphi(k)*x^(n-k)), p)), return(p))); 1; \\ Michel Marcus, Aug 04 2025

Formula

a(9) = 67 since 67 = 9^2 - 2*9 + 4 is the least prime p such that the polynomial Sum_{k=1..9}phi(k)*x^(9-k) is irreducible modulo p.