Distinctive property of the primes 17 and 19?

Consider the question whether it is true that a prime number $p$ divides $1^1+2^2+3^3+....+(p-1)^{p-1}$ if and only if $p \in \{17,19\}$.

For the obvious heuristic reasons, for large $n$ one would expect there to be roughly $\ln(\ln(n))$ such primes $p < n$, however it seems that presently no examples other than 17 and 19 are known.

Is there a more efficient way of looking for examples than the brute force method of testing the primes one-by-one?

• See the FAQ's section on open problems. Also, what evidence is there that this is true? If you pick a random number mod each prime, this should be $0$ infinitely often, but the number of times you pick $0$ among the first $n$ primes will grow as $\log \log n$. So, if you see two examples among the first $1000$ or $10^6$, this is still not much evidence that there is anything special about those two examples, and that there aren't infinitely many examples. – Douglas Zare May 27 '13 at 8:09
• Another interesting paper is about the residues of $n^n$ mod $p$ for $n=1,2,\ldots ,p-1$, here: www.fq.math.ca/Scanned/19-2/somer.pdf‎ – Dietrich Burde May 27 '13 at 8:44
• Is there ANY property of primes where for the obvious heuristic reasons one would expect there to be roughly ln(ln(n)) such primes p<n, and for which there is a proof that there are infinitely many such primes? – André Henriques May 28 '13 at 13:40
• This (very early!) paper of Soundararajan ams.org/mathscinet-getitem?mr=1207502 shows that there are $O( \log x / (\log \log x)^2)$ primes of the form $1^1 + \ldots + n^n$ less than $x$. This doesn't directly help with the problem though... – Terry Tao May 28 '13 at 16:43
• I was interested in the determinant (mod $p$) and the trace (mod $p$) of a matrix defined as follows :- For each prime $p$, define a $(p-1)*(p-1)$ integer matrix $M^{p}$ as $M^{p}_{ij} \equiv i^{j}$ (mod $p$), $0<i<p, 0<j<p$. I was surprised to see that the trace was 0 (mod $p$) only for 17 and 19 in the first 3000 primes and thus I thought of posting this question. (I know that 3000 is very small number and one should not make any blind conjecture based on only 3000 evidences). – Mihir Sheth May 29 '13 at 5:53

exp(exp(3)) is about 5e8 and testing the primes up to that is probably feasible with a few days of computer abuse. I tested up to 1e5 in 6 minutes with a trivial, single-threaded Haskell script (no more p's found). I don't see any particular reason to think there are no more p's though. It would surprise me if searching didn't turn up another p.

• Testing up to $N$ takes time proportional to $N^2$ (the sum mod $p$ is a sum of $p$ terms, each of which takes about $\log p$ operations mod $p$, and there are $N/\log N$ terms to try. So going from $10^5$ to $5 \cdot 10^8$ would multiply the computing time not by $500$ but by about a quarter-million, unless there's some clever speedup I'm not seeing to a smaller power than $N^2$. – Noam D. Elkies May 28 '13 at 3:15
• One passably clever speedup would memoize mod p the results of $m^m$ and $n^n$ to aid in calculating $mn^{mn}$, but I don't see it reducing the exponent on the runtime. Gerhard "Has Not Thought It Through" Paseman, 2013.05.27 – Gerhard Paseman May 28 '13 at 6:27

This should be a comment, but I can't post them, sorry. To follow up the above: Prof. Elkies is of course right about the $O(n^2)\,$ complexity of the basic algorithm, but it should be possible to get large constant-factor speedups with better implementation:

• First of all there's probably 10x-50x available just by rewriting the program in C using the naive algorithm, and running on a multi-core processor, depending on available hardware. Let's say 25x on an 8-core AMD processor.

• There might be another 2x(?) using Montgomery's representation (from cryptography) to get rid of most of the integer division operations in the modular exponentials. Actually maybe a lot more than 2x.

• Finally, combining the above (I'm less sure of this) it might be possible to run on a graphics accelerator giving 100x or more.

Assuming 50x (perhaps using two or three computers) that would give 250000*6 minutes / 1440 minutes/day = about 3 weeks, which is above my guess of a "few days" but I think still feasible if someone was really interested. I'm surprised by how many upvotes this thread got.