What percentage of positive integers, written in base 10, are composite regardless of what base they are interpreted in?

Question

There is a sequence of numbers (OEIS A121719) with the following defenition:

If the string of base-$10$ digits corresponding to the positive integer $k$ is composite when interpreted in any possible base $b$, then $k$ is in the sequence.

After writing a program to find values of the sequence, I was curious whether the percentage of numbers $k<n$ in the sequence approaches a certain value as $n$ increases. I will now formally define my question:

$A$ is the set of all positive integers in the sequence defined above.

$$C(n)=1\:\text{if}\:n\in A,\:\text{otherwise}\:0$$ $$L=\lim_{n\to\infty}\frac{1}{n}\sum^n_{i=1} C(i)$$ I would like to know:

1. Does the limit $L$ exist?
2. Is $L>0$?
3. Is there some method to find $L$ or the first $n$ digits of $L$?

Answer 1

I claim that assuming the Bunyakovsky conjecture and the extended Riemann hypothesis (i.e. RH for all Dedekind zeta functions), the limit $L$ exists and equals $$ L = \frac{59/18 + 1/5^4 + 1/7^6}{10} = \frac{4340435807}{13235512500} \approx 0.32793862776. $$ (Both of these hypotheses seem like really big hammers, but I'm pretty sure there is no easy way around either of them.)

Proof: Identify nonnegative integers $k$ with the polynomials $f_k(x)$ whose coefficients are their base-10 expansions. The Bunyakovsky conjecture predicts that any $f_k(x)$ not satisfying condition 2 or 3 will produce infinitely many prime values at positive integer inputs. In particular, it will produce some primes at inputs $b$ which are large enough (say, $b \geq 10$) for $k$ to be interpreted in base $b$. This implies, conditional on Bunyakovsky, that every term of the sequence must satisfy condition 2 or 3 from the comment on OEIS.

Let's consider condition 3. Any common divisor of the values of $f_k(x)$ is in particular a divisor of $f_k(0)$, namely the last digit of $k$. This implies that if the last digit of $k$ is nonzero, $k$ can never satisfy condition 3 for any prime $p > 7$. Of course, if the last digit of $k$ is zero (and $k > 10$), then $k$ automatically satisfies condition 2. So it suffices to consider condition 3 with $p = 2, 3, 5$, and $7$, along with condition 2.

Now consider condition 2. It's relatively uncommon for a polynomial with small integer coefficients to be reducible. In fact, assuming the extended Riemann hypothesis, Corollary 3 of this recent paper of Breuillard and Varjú implies that as $d \to \infty$, the proportion of degree-$d$ polynomials with $\{0, \dots, 9\}$ coefficients that are reducible is $\frac{1}{10} + O(d^{-1/2})$. (Take $\mu$ to be the uniform distribution on $\{0, \dots, 9\}$ and $N = 1$. The $\frac{1}{10}$ comes from polynomials vanishing at 0; i.e. integers $k$ that are divisible by 10.) So as $k \to \infty$, we can ignore condition 2 except as it pertains to multiples of 10.

At this point, it's just a matter of going through the casework of condition 3 for $p = 2, 3, 5, 7$. You can check that $f_k(x) = \sum_i a_i x^i$ satisfies condition 3 for a given $p$ if and only if the following two hypotheses hold: (a) $p$ divides $a_0$, and (b) for all $0 \leq t < p-1$, $p$ divides $$ \sum_{i > 0, i \equiv t \pmod{p-1}} a_i. $$ (Equivalently, $f_k(x)$ lies in the ideal $(p, x^p - x) \subset \mathbb Z[x]$.) As $k \to \infty$, (b) happens with probability $1/p^{p-1}$, independently of $a_0$. So the probability that $n$ is in the sequence given each possible last digit is as follows:

0. $P = 1$ (condition 2)
1. $P = 0$
2. $P = 1/2$ ($p = 2$)
3. $P = 1/9$ ($p = 3$)
4. $P = 1/2$ ($p = 2$)
5. $P = 1/5^4$ ($p = 5$)
6. $P = 5/9$ ($p = 2$ or $3$)
7. $P = 1/7^6$ ($p = 7$)
8. $P = 1/2$ ($p = 2$)
9. $P = 1/9$ ($p = 3$)

(Note that for $a_0 = 6$, the conditions coming from $p = 2$ and $p = 3$ are independent as $k \to \infty$.) Averaging these ten probabilities gives the final answer.