3
$\begingroup$

Let $A$ be the set of numbers whose sum of digits is prime (http://oeis.org/A028834).

I would like to know if $A$ has zero natural density, that is, if $$\lim_{n \to +\infty} \frac{A(n)}{n} = 0,$$ where $A(n)$ is the number of elements of $A$ which are less than or equal to $n$.

Numerical experiments seems to indicate that $A(n) / n$ goes to zero, but very slowly.

$$\begin{matrix}n & A(n)/n \\ 10 & 0.400 \\ 10^2 & 0.370 \\ 10^3 & 0.340 \\ 10^4 & 0.301 \\ 10^5 & 0.267 \\ 10^6 & 0.249 \end{matrix}$$

Graph of $A(n) / n$

Thanks

Improve this question
$\endgroup$
1
  • 10
    $\begingroup$ If you look at numbers up to $10^n$, the $n$ digits are iid, so the sum would be approximately normal with mean $9n/2$ and standard deviation $c\sqrt n$. Your question boills down to knowing that the density of primes in intervals of length roughly $\sqrt n$ starting at $n$ converges uniformly to 0. $\endgroup$
    – Anthony Quas
    Jan 1, 2021 at 21:24

2 Answers 2

Reset to default
16
$\begingroup$

Yes, $A(n)$ has zero natural density. It suffices to prove this for $n$ which is a power of $10$. and it is possible to make this more precise. To see this, first let $n=10^k$ and note that for $X$ chosen uniformly among integers in $[0,n-1]$, the sum $S(X)$ of base 10 digits is the sum of $k$ i.i.d. random variables uniformly distributed among integers in $[0,9]$. By the Local Central Limit Theorem for i.i.d. lattice variables (see, e.g. [1], [2] for a precise formulation) the law of $S(X)$ is very well approximated by a normal density of standard deviation of order $\sqrt{k}$ centered at $4.5k$. Now use the elementary fact that for any $f(k) \to \infty$ and any $B>1$, the asymptotic frequency of primes in $[k, k+f(k)]$ is at most $\prod_{p \le B} (1-1/p) $. This product over primes tends to 0 as $B \to \infty$, proving the asymptotic density of $A(n)$ is zero.

Remark: Together with the PNT [3] one gets the prediction $$A(n)/n=\frac{1+o(1)}{\log \log(n)} \,,(*) $$ but the PNT does not imply this, one needs to use more precise information on the number of primes in short intervals, a topic of much research, see e.g. [4], [5] and the references therein. In particular, the sieve estimate of Montgomery-Vaughn (See Cor 3.4 in [4]) yields $$A(n)/n\le \frac{4+o(1)}{\log \log(n)} \,.$$

[1] https://encyclopediaofmath.org/wiki/Local_limit_theorems

[2] V.V. Petrov, "Sums of independent random variables" , Springer (1975) (Translated from Russian)

[3] https://en.wikipedia.org/wiki/Prime_number_theorem

[4] Montgomery, Hugh L., and Robert C. Vaughan. Multiplicative number theory I: Classical theory. Vol. 97. Cambridge university press, 2007.

[5] How many primes can there be in a short interval?

Improve this answer
$\endgroup$
7
  • $\begingroup$ There's something I don't get. Letting $k \to \infty$ and $n = 10^k$, it seems to me that you are saying that: (1) All but $o(n)$ elements of $A \cap [1, n]$ have sum of digits in $I = [4.5k - \sqrt{k}, 4.5k + \sqrt{k}]$ (2) The number of primes in $I$ is $o(|I|)$ (3) Hence $A(n) = o(n)$. I agree with (1) and (2) but I don't see how (3) follows. It might be that $I$ contains very few primes, but - since different elements of $A \cap [1, n]$ can have the same sum of digits - nevertheless $A \cap [1, n]$ is still big. Could you please give more details? $\endgroup$
    – dache1771
    Jan 1, 2021 at 22:35
  • 1
    $\begingroup$ Minor correction: From Montgomery--Vaughan (which is really Brun--Titchmarsh) one would get $A(n)/n \le (4+\epsilon)/\log \log n$. The point is that in an interval $[x,x+y]$ one has at most $2\pi(y)$ primes in M--V, and one loses another factor of $2$ because $y$ here is about $\sqrt{x}$ (i.e. $\log \sqrt{\log n}$ loses another $2$). $\endgroup$
    – Lucia
    Jan 2, 2021 at 0:36
  • 1
    $\begingroup$ @dache1771 It's not just (1); it's also that we can specify exactly what the distribution of sums looks like within that interval, because of the convergence to a normal distribution. In particular, it's impossible for the sum to 'concentrate' at any particular value, prime or otherwise. $\endgroup$
    – Steven Stadnicki
    Jan 2, 2021 at 2:11
  • $\begingroup$ @dache1771 First, (1) is not accurate since a Normal distribution is not limited to a fixed number of standard deviations. Please see the exact statement of the Local CLT in the sources I cited or in Durrett's textbook. That statement also answers your objection as noted by Steven Stadnicki. $\endgroup$
    – Yuval Peres
    Jan 2, 2021 at 3:07
  • 1
    $\begingroup$ @Lucia I agree, and corrected this in the text of the answer. Thanks for pointing out this correction. $\endgroup$
    – Yuval Peres
    Jan 2, 2021 at 3:14
6
$\begingroup$

The following paper by Glyn Harman (Counting primes whose sum of digits is prime. J. Integer Seq. 15 (2012), no. 2, Article 12.2.2, 7 pp) studies a more complicated situation: count primes $p \leq X$, where in addition the sum of digits (in a given base $b$) is also prime.

Harman achieves Mertens type results (Theorem 2), shows an asymptotic in the unweighted situation conditionally (Theorem 6), but also explains that a true asymptotic cannot be proved, unless one assumes stong assumptions on primes in short intervals, in the spirit of the Riemann Hypothesis, (which is also discussed in Yuval Peres' answer).

The current question does not require that the objects counted are primes themselves. Hence going through this paper and replacing $\sum_{ p \leq X\ }$ by $\sum_{n \leq X\ }$ should lead to the requested result, with a density of $\frac{1}{\log \log X}\ $ .

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.