14
$\begingroup$

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!

  • 2
    Till $10^8$, the primes are $5,71,369119$ i.e. till the $5761455^{th}$ prime.2011-11-29
  • 0
    The very naive heuristic is indeed very naive, since we could make such an heuristic for mostly any non-trivial property about prime numbers...2011-11-29
  • 1
    Well that was pretty quick! Awesome! I think my computer would have taken the age of the universe to check that.2011-11-29
  • 0
    Jon Schoenfield checked to 10^12 without finding further terms, see the OEIS link.2011-11-29

2 Answers 2

7

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

  • 0
    Thanks Robert! Well, I guess that more or less puts an end to this discussion.2011-11-29
  • 4
    Always a good idea to check OEIS first whenever you encounter an integer sequence...2011-11-29
  • 1
    Moral of the story: always check OEIS, especially when the third element in the list is 369119.2011-11-29
  • 1
    I swear that was simultaneous!2011-11-29
  • 1
    https://oeis.org/A009560 also worth looking at.2011-11-29
15

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.

enter image description here

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:

enter image description here

Can anybody explain this effect?

  • 1
    That's awesome!2011-11-29
  • 4
    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?)2011-11-29
  • 2
    Yes, I do. http://www.math.ubc.ca/~israel/problems/smodp3.jpg2011-11-29
  • 1
    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, ...2011-12-02
  • 0
    ... 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.2011-12-02