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?

  • 6
    $\begingroup$ 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. $\endgroup$ Commented May 27, 2013 at 8:09
  • 2
    $\begingroup$ 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‎ $\endgroup$ Commented May 27, 2013 at 8:44
  • 1
    $\begingroup$ 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? $\endgroup$ Commented May 28, 2013 at 13:40
  • 4
    $\begingroup$ 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... $\endgroup$
    – Terry Tao
    Commented May 28, 2013 at 16:43
  • 6
    $\begingroup$ 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). $\endgroup$ Commented May 29, 2013 at 5:53

2 Answers 2


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.

  • 3
    $\begingroup$ 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$. $\endgroup$ Commented May 28, 2013 at 3:15
  • $\begingroup$ 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 $\endgroup$ Commented May 28, 2013 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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