Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
11  
Do it yourself. –  Fernando Muro May 27 '13 at 7:17
6  
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
15  
I can't do it myself. Please note that after being used to reading problems phrased in this manner in most books, it is perfectly understandable for students (especially foreign) to state questions as starting with "prove that". –  Gjergji Zaimi May 27 '13 at 8:14
8  
Gjerji, if it's an open problem then asking us to prove is seems a bit too much. If it's not an open problem, I'd like to see some more motivation behind this question. –  Asaf Karagila May 27 '13 at 8:17
6  
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

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.

share|improve this answer
3  
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.

share|improve this answer
2  
See also arxiv.org/abs/1209.3436 for ideas about possible mathematical speedups. –  François Brunault May 30 '13 at 8:31

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.