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
    Commented 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
  • 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
    Commented 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
    Commented Jan 2, 2021 at 2:11
  • 1
    $\begingroup$ @Lucia I agree, and corrected this in the text of the answer. Thanks for pointing out this correction. $\endgroup$
    – Yuval Peres
    Commented Jan 2, 2021 at 3:14
  • 1
    $\begingroup$ Beautiful answer! $\endgroup$
    – Greg Martin
    Commented Jan 3, 2021 at 2:10
  • 1
    $\begingroup$ Let $P$ be a subset of $\mathbb N$ whose asyptotic density is 0. Let $B$ be the set of numbers whose sum of digits is in $P$. Using the same arguments as above, one can prove that $B$ has zero asymtotic density. This applies for exemple to $P=\{n^2, n\in\mathbb N\}$ or $P$ the set of practical numbers. $\endgroup$
    – G. Melfi
    Commented Nov 1, 2023 at 13:42
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .