# How rare are the primes $p$ such that $p$ divides the sum of all primes less than $p$?

This is just for fun! The title pretty much says it all. It's probably a very difficult question.

Up to the $40,000^{th}$ prime $(479909)$, I have found only $5$, $71$ and $369119$ with this property. Somebody with better hardware than me might have better luck!

Edit: Sivaram Ambikasaran has checked that these are the only ones up to $10^8$, i.e. up to the $5761455^{th}$ prime (see the comments).

(Here is a very naive heuristic: if we suppose the sum $S_n$ of primes less than $p_n$ to be randomly distributed mod $p_n$, it will be divisible by $p_n$ with probability $1/p_n$. Hence the function $f$ given by

$$f(n) = \begin{cases} 1, & \text{ if } p_n \mid S_n, \\ 0, &\text{ otherwise.} \end{cases}$$

should have expected value $1/p_n$, and hence I'd expect the series $\displaystyle\sum_{n\geq 1}f(n)$ to diverge very slowly, like the sum of reciprocals of the primes, which is approximately $\log \log n$... but then again, such an argument is more or less worthless.)

Cheers!

-
Till $10^8$, the primes are $5,71,369119$ i.e. till the $5761455^{th}$ prime. – user17762 Nov 29 '11 at 1:12
The very naive heuristic is indeed very naive, since we could make such an heuristic for mostly any non-trivial property about prime numbers... – Patrick Da Silva Nov 29 '11 at 1:14
Well that was pretty quick! Awesome! I think my computer would have taken the age of the universe to check that. – Bruno Joyal Nov 29 '11 at 1:14
Jon Schoenfield checked to 10^12 without finding further terms, see the OEIS link. – Charles Nov 29 '11 at 15:30

The next one is 415074643. Apparently that's the largest one known. See https://oeis.org/A007506

-
Thanks Robert! Well, I guess that more or less puts an end to this discussion. – Bruno Joyal Nov 29 '11 at 1:30
Always a good idea to check OEIS first whenever you encounter an integer sequence... – J. M. Nov 29 '11 at 1:40
Moral of the story: always check OEIS, especially when the third element in the list is 369119. – Bruno Joyal Nov 29 '11 at 1:41
I swear that was simultaneous! – Bruno Joyal Nov 29 '11 at 1:41
oeis.org/A009560 also worth looking at. – Henry Nov 29 '11 at 22:31

The naive heuristic is not so naive, although maybe not quite true. Here is a graph of $S_n \mod p_n$ versus $p_n$ for the first 2000 primes.

It looks rather random except for the part from about 10000 to 15000 that shows an interesting pattern. A closer look in other places reveals similar patterns in other places too, e.g. here it is from 90000 to 104000:

Can anybody explain this effect?

-
That's awesome! – Bruno Joyal Nov 29 '11 at 22:25
These "windows" of order are centered at around 13,000 and 99,000; there's also one centered around 4,700 or so. Now 99,000/13,000 is approximately $e^2$ and $13,000/4,700$ is approximately $e$. I can't help but think that this isn't a coincidence. (Do you see something similar around 36,000 or so?) – Michael Lugo Nov 29 '11 at 22:45
Yes, I do. math.ubc.ca/~israel/problems/smodp3.jpg – Robert Israel Nov 29 '11 at 23:10
In fact, the "windows" seem to be near $p_n$ where $p_n^2/S_n$ is an even integer. And that, I think, is the key to the explanation. Suppose $S_n \approx p_n^2/(2 r)$ where $r$ is a small positive integer, i.e. $S_n = A_n p_n + B_n$ where $A_n$ is an integer and $A_n \approx p_n/(2 r)$. If $p_{n+i} - p_n \equiv 0 \mod 2 r$ where $i$ is a small integer, i.e. $p_{n+i} = p_n + 2 k r$ for some small integer $k$, then since $S_{n+i} \approx S_n + i p_n$ we get $S_{n+i} \approx (A_n + i-k)(p_{n+i}) + B_n$ because $A_n (2 k r) + (i-k) p_n$ is small, ... – Robert Israel Dec 2 '11 at 0:02
... and thus $S_{n+i} \mod p_{n+i}$ is close to $S_n \mod p_n$. The "curves" in the pictures correspond to the different congruence classes for $p_n$ mod $2 r$ (hmm, or maybe mod $r$). Thus for $p_n$ around 13000, $S_n \approx p_n^2/36$ (with $p_{1536} = 12907$ and $S_{1536} = 9254767$). There are 6 curves, corresponding to the different congruence classes mod 18 that are coprime to 18. – Robert Israel Dec 2 '11 at 0:19