Digit sequence that is not prime in any base

Question

Is there a sequence of base-$b$ digits of length greater than one with all digits $\ne 0$ that does not represent a prime number in any base?

Example: $12_{10}=12$ is not prime, but $12_3=5$ is.

Answer 1

$121$. Suppose it is prime in base $b$. Then $b^2+2b+1=(b+1)(b+1)$ is prime.

Answer 2

Extending Jorge's example, $$\sum_{k=0}^{n}{\binom{n}{k}b^k}=(b+1)^n$$ is not prime in any base large enough to have the binomial coefficients as digits.

Answer 3

$112$ is always divisible by $2$ for bases above base $2$

$1111=11\times 101$ in any base.

Answer 4

The smallest example (unless you are in base 2) is $22=2 \cdot 11$

Answer 5

How about $121$. We have $1b^2+2b+1=(b+1)^2$.

Similarly for $1331$ we have $1b^3+3b^2+3b+1=(b+1)^3$.

Answer 6

If $d_nd_{n-1}\ldots d_0$ is a string of digits, it is convenient to consider the polynomial $f(x)=d_nx^n+d_{n-1}x^{n-1}+\ldots+d_0$. Then $(d_nd_{n-1}\ldots d_0)_b=f(b)$. The OP's question is related to the question "Which integer polynomials take only composite values?".

The answers given so far describe two different phenomena (both illustrated in Mark Bennet's answer).

1. If $f(x)$ factors as a polynomial, then $f(b)$ is composite for all sufficiently large $b$. For example, $1111_b=101_b\cdot 11_b$ is composite for all $b$, which is equivalent to the polynomial factorization $x^3+x^2+x+1=(x^2+1)(x+1)$.
2. Sometimes there is a particular prime $p$ that divides $f(x)$ for all integers $x$. For instance, $2$ always divides $112_b$ (equivalently, $2\big|\,f(b)$, where $f(x)=x^2+x+2$).

The Bunyakovsky conjecture would imply that these are the only reasons a polynomial takes only composite values.

Conjecture: Let $f(x)\in\mathbb{Z}[x]$ be non-constant with positive leading coefficient. Suppose:

• $f(x)$ is irreducible, and

• there is no integer $d>1$ such that $d\,\big|\,f(b)$ for all integers $b$.

Then $f(b)$ is prime for infinitely many positive integers $b$.

There are deterministic algorithms for checking whether a given polynomial satisfies the hypotheses of this conjecture.