11
$\begingroup$

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?

Improve this question
$\endgroup$
14
  • 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$
    – Douglas Zare
    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$
    – Dietrich Burde
    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$
    – André Henriques
    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$
    – Mihir Sheth
    Commented May 29, 2013 at 5:53

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 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$
    – Noam D. Elkies
    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$
    – Gerhard Paseman
    Commented May 28, 2013 at 6:27
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .