If you reformulate a problem just a little bit, it does not actually become combinatorially hard.
3^7 + 13 = 3 + 13^3 (= 2200)
3^7  3 = 13^3  13 (= 2184)
So you don't actually need to consider pairs of primes separately. Just calculate "p^n  p" for all primes p and powers n >= 2 such that the value is less than your limit, and see if you get the same number twice. To check this for all numbers up to some limit, you only need to consider primes up to about sqrt(limit) as otherwise prime^2 would already be too big. I checked that 2184 is the only such number up to about 10000000000000000 (a hundred million squared, considering primes up to hundred million). That took less than half a minute with a Python script.
