cp's OEIS Frontend

Conjecture: For any integers n >= m > 0, there are infinitely many positive integers s > p_n such that the number sum_{k=m}^n p_k*s^{n-k} (i.e., [p_m,...,p_n] in base s) is prime; moreover the smallest such an integer s (denoted by s(m,n)) does not exceed (n+1)*(m+n+1).

Note that s(1,n) = a(n) and s(4,21) = 546 < (21+1)*(21+4+1) = 572.

A related conjecture of the author states that for each n=2,3,... the polynomial sum_{k=1}^n p_k*x^(n-k) is irreducible modulo some prime. See also the author's comments on A000040.

The conjecture can be further extended as follows: If a_1 < ... < a_n are distinct integers with a_n prime, then there are infinitely many integers b > a_n such that [a_1,a_2,...,a_n] in base b is prime.

For example, [2,3,...,210,211] in base 55272 and[17,19,27,34,38,41] in base 300 are both prime.

See A224197 for a more general conjecture.

Conjecture: a(n) does not exceed the (4n-3)-th prime for each n>0. Moreover, for any integers m>1 and n>0 the polynomial sum_{k=0}^n (k+1)^m*x^{n-k} is irreducible modulo some prime, and its Galois group over the rationals is isomorphic to the symmetric group S_n. Also, for m,n=2,3,... there are infinitely many integers b > n^m such that [n^m,...,2^m,1^m] in base b is prime.

We have a similar conjecture with the above (k+1)^m replaced by (2k+1)^m.

Conjecture: (i) a(n) does not exceed n^2+n+5 for each n>0, and the Galois group of sum_{k=0}^n C_k*x^{n-k} over the rationals is isomorphic to the symmetric group S_n.

(ii) For any positive integer n, the polynomial sum_{k=0}^n binomial(2k,k)*x^{n-k} is irreducible modulo some prime if and only if n is not of the form 2k(k+1), where k is a positive integer.

(iii) For any positive integer n, the polynomial sum_{k=0}^n T_k*x^{n-k} is irreducible modulo some prime not exceeding n^2+n+5, where T_k referes to the central trinomial coefficient A002426(k) which is the coefficient of x^k in the expansion of (x^2+x+1)^k.

Conjecture: a(n) < 4n^2-1 for all n>0.

Conjecture: a(n) < n^2 for all n > 1.

Conjecture: a(n) <= (n+4)*(n+5)+1 for all n>0.

Conjecture: a(n) <= n^2+12 for all n>0.

Such a phenomenon happens quite often. In fact, for many interesting integer sequences a(k) (k=1,2,3,...), each of the polynomials x^n + sum_{k=0}^n a(k)*x^{n-k} (n>0) is irreducible modulo some prime not exceeding a*n^2+b*n+c, where a, b, c are suitable nonnegative constants.

It is well known that (x^{p^n}-1)/(x^{p^{n-1}}-1) is irreducible over the rationals for any prime p and positive integer n.

We have the following "Reciprocity Law": For any positive integer n and primes p > 2 and q, the cyclotomic polynomial (x^{p^n}-1)/(x^{p^{n-1}}-1) is irreducible modulo q if and only if q is a primitive root modulo p^n.

This can be proved as follows: As any monic irreducible polynomial over F_q=Z/qZ of degree k divides x^{q^k}-x in the ring F_q[x], the polynomial f(x)= (x^{p^n}-1)/(x^{p^{n-1}}-1) in F_q[x] has an irreducible factor of degree k < deg f if and only if f(x) is not coprime to x^{q^k}-x for some k < p^n-p^{n-1}. Note that gcd(x^{p^n}-1,x^{q^k-1}-1) = x^{gcd(p^n,q^k-1)}-1. If p^n | q^k-1, then x^{p^n}-1 | x^{q^k}-x and hence f(x) divides x^{q^k}-x; if p^n does not divide q^k-1, then gcd(x^{p^n}-1,x^{q^k-1}-1) divides x^{p^{n-1}}-1 and hence f(x) is coprime to x^{q^k}-x. Thus, f(x) is irreducible modulo q, if and only if p^n | q^k-1 for no 0 < k < p^n-p^{n-1}, i.e., q is a primitive root modulo p^n.

By the above "Reciprocity Law" in the case n=1, we have a(k) = A002233(k) for all k > 1.

Conjecture: a(n) <= sqrt(7*p_n) for all n>0.

Conjecture: a(n) <= n^2+22 for all n>0.

We have similar conjectures with 2k+1 in the definition replaced by (2k+1)^m (m=2,3,...).