# Can we find prime numbers with any sum of digits (except those divisible by three)

I guess that this question is not something new and that there must be people who wanted to know if this question has an affirmative answer, but I would like to share it with you, because I really do not know if this is known or not?

Let us define sum of digits (in base 10) function $sd_{10}$ over the set of natural numbers in an obvious way as $sd_{10}(n)=\sum_{i=0}^ma_i$, where we have that $n=\sum_{i=0}^m a_i \cdot 10^i$.

If we choose some number, for example $7$ ,then we can find prime number which has its sum of digits equal to $7$, for example $61$.

If we choose some number divisible by $3$ as the sum of digits then we cannot find a prime number that has that sum of digits because it is known that the number is divisible by $3$ if and only if sum of its digits is divisible by $3$.

Let us also suppose here, because of the easier phrasing of the question, that the number $1$ is also prime so that if we choose that the sum of digits is $1$ we have a solution which equals $1$.

Is it true that for every $n \in \mathbb N \setminus \{3k : k \in \mathbb N\}$ there exists at least one prime number $p$ which is such that we have $sd_{10}(p)=n$?

• The approximately $10^n/n \ln 10$ primes below $10^n$ all have $sd_{10}\le 9n$, so there should be plenty of opportunities to "hit" any allowed value ... – Hagen von Eitzen Apr 30 '16 at 22:39
• I couldn't even consider it a heuristic.. – Paolo Leonetti Apr 30 '16 at 22:40
• @HagenvonEitzen Is there any conjectured approximate value for questions like these? – Farewell Apr 30 '16 at 22:42
• @PaoloLeonetti $1$, because I stated in the question that we take $1$ as prime because of the easier phrasing of the question. – Farewell Apr 30 '16 at 22:43
• @Farewell: Most mathematicians would prefer to specify $n > 1$, rather than arbitrarily declare $1$ to be prime. It's sort of like saying "for the purposes of this question, let us consider $1$ to be even". (But it's not quite that bad, because in the dim and distant past there were mathematicians who counted $1$ as prime.) – TonyK May 1 '16 at 18:40

Ruling out $n=1$ and $3|n$ we have the following conjecture :

For every natural number $n$, there is a prime with digitsum $n$.

The conjecture is definitely true for $2\le n\le 200$ (I found proven primes with PARI/GP) and very probably true for $2\le n\le 1000$ (The numbers I found passed $10$ strong probable-prime-tests)

Since there are infinite many numbers with digit-sum $n$ for every $n$, and many of these numbers are "small", it is very likely that we find a prime for every $n$.

This should give an overhelming heuristical argument to believe that the claim is true for all $n$.

A proof of this conjecture is very probably currently out of reach.

• You wrote "Perhaps someone can calculate the number of integers with digitsum n for a given n.". There is an infinite number of integers with digit sum $n$ for every $n$. – Farewell May 1 '16 at 18:23
• Oops, you are right. This makes the probability that the claim is true even much higher. – Peter May 1 '16 at 18:24
• Yes indeed. :) :) – Farewell May 1 '16 at 18:25
• Now you wrote "Since there are infinite many numbers with digit-sum n for every n, and many of these numbers are "small", it is very likely that we find a prime for every n." But many of these numbers are, on the contrary, big, because you can choose some number that has the sum of the first $k$ digits equal to $n-1$, then after that $k$ digits you can add as many zeros as you want, and then choose the last digit $1$ to obtain a sum $n$, right? – Farewell May 1 '16 at 18:30
• But there are also many "small" such numbers, numbers with, lets say, $\frac{n}{2}$ digits. I did not mean : Most of the numbers are "small". – Peter May 1 '16 at 18:32

The answer is yes, for sufficiently large $n$. This was recently proved in

Drmota, Mauduit and Rivat, "Primes with an average sum of digits". Compositio Mathematica, Volume 145:2 (March 2009), pp. 271–292.

Preprint available here: http://www.dmg.tuwien.ac.at/drmota/DMRcomp2.pdf

Theorem 1.1 is a type of Central Limit Theorem for the sum-of-digits function on primes, showing that when the number of digits is large, then the digit sum tends to be clustered normally around the average. Their result is strong enough to show that if you want to have a digit sum of exactly $n$ in base $10$ then you can achieve this with a $\lceil 2n/9 \rceil$-digit prime, provided $n$ is large enough.

I am not familiar enough with the paper to know how effective the convergence is and whether your question can be given a full affirmation after a practical amount of computation.