Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
2  
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
1  
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

2 Answers 2

up vote 7 down vote accepted

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

share|improve this answer
    
Thanks Robert! Well, I guess that more or less puts an end to this discussion. –  Bruno Joyal Nov 29 '11 at 1:30
4  
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
1  
I swear that was simultaneous! –  Bruno Joyal Nov 29 '11 at 1:41
1  
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.

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?

share|improve this answer
1  
That's awesome! –  Bruno Joyal Nov 29 '11 at 22:25
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?) –  Michael Lugo Nov 29 '11 at 22:45
2  
Yes, I do. math.ubc.ca/~israel/problems/smodp3.jpg –  Robert Israel Nov 29 '11 at 23:10
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, ... –  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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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