Primes and Strong Pseudoprimes of the form x^y + y^x

Many moons ago in a previous life, I was surprised to receive an email out of the blue which claimed that there are only a finite number of non-trivial values of x and y such that x^y + y^x  is prime. By "non-trivial" I mean, of course, that we discount (x,y) = (p-1,1) where p is prime and we assume for convenience that x>y.

It's straightforward to put a few conditions on x and y which must be met for x^y + y^x to be prime. For a start, they must be of opposite parity and be co-prime (i.e. have no factors in common). These conditions only remove a few candidates, and it was not obvious to me that all but a finite number of the remainder had to be composite. I wrote a little search program and found a few dozen pairs which were strong pseudoprimes. The smallest of these, those up to 400 decimal digits or so, were proved prime with a number of different programs, principally UBASIC's APRT-CL test and François Morain's ECPP.

A couple of years later, I completed the search for all x < 1030, and proved several more candidates prime, including (405,364) and (406,289) which have more than a thousand digits each. There the matter rested until early 2001. I still don't have a clue as to whether the number of primes of this form is finite or infinite, but if forced to guess I would go for infinite.

Interest was re-raised in February 2001 when a few people started searching again. A number of them, especially Greg Childers and Andrey Kulsha, have been particularly effective in finding new pseudoprimes and proving some of them to be prime. Andrey holds the record for the largest pseudoprime yet discovered of this form. It has 87201 digits. The results of all the searchers are summarized in the table below. The smaller values, especially those which have x < 1000, have doubtless been found many times by many other researchers. The last entry with x<1000 was completed on 28 March 2002.

Note added 16 November 2004: I thought that the tables were complete to x<1000 but Andrey Kulsha discovered two PRPs which had been omitted and has since proved them prime. This shows the importance of double checking the computations! Andrey has now completed the double checking as far as x=3500 and found no further errors. Please contact me if you have any other corrections or additions to make to either table on this page.

More recently still, it was realized that numbers of this form are ideal test cases for general purpose primality proving programs. They have a simple algebraic description but no obvious cyclotomic properties which special purpose algorithms can exploit. There seems to be a reasonably high density of primes of this form and so there is a reasonable number of test cases to use. Finally, there seems to be a good distribution of small, medium and large sized candidates in the tables below.

I volunteer to co-ordinate any further searches and to keep the following tables as up to date as I can. I strongly suggest that searches be performed in order of increasing x values, and that all values of y be tested for each x in the range. It keeps things neat and tidy, and makes my task easier 8-)

Mark Rodenkirch has written a program to sieve out candidates which are divisible by small primes, so reducing the number which need to be subjected to an expensive PRP test.

Raffi Chaglassian has already searched the range 7500 < x <8000 for 100 < y < 1001. Anatoly Selevich has completed searching the range 8000 < x < 20000 for y < 1001, Andrey Kulsha has completed the range 20000 < x < 100000 for y< 11 and Anatoly Selevich is searching the range 7500 < x <20001 for 1000 < y< 2001 so, to avoid duplicating their work, you should start searches with y = 2001 or y = 1001 or y = 11 as appropriate.

Andrey is also co-ordinating a project to find the factorization of "small" composite values of  x^y + y^x . He's produced a very professional looking site, and I recommend that you take a look.

The table below lists all the proven primes and strong pseudoprimes of the form x^y + y^x known to me at 6th October 2006. Greg Childers informs me that certificates for the ones he has proved prime are available at http://www.pa.uky.edu/~childers/certs/ and Christ van Willegen's certificates are at http://home.iae.nl/users/richtofe/certs.