Conjecture. (Stephen Redmond & Zhi-Wei Sun) Given positive integers $x$ and $y$ and exponents $a$ and $b$ (with all these numbers being greater than 1), if $x^a \neq y^b$ then between $x^a$ and $y^b$ there are always primes, with only the following ten exceptions:

1. There are no primes between $2^3$ and $3^2$
2. There are no primes between $5^2$ and $3^3$
3. There are no primes between $2^5$ and $6^2$
4. There are no primes between $11^2$ and $5^3$
5. There are no primes between $3^7$ and $13^3$
6. There are no primes between $5^5$ and $56^2$
7. There are no primes between $181^2$ and $2^{15}$
8. There are no primes between $43^3$ and $282^2$
9. There are no primes between $46^3$ and $312^2$
10. There are no primes between $22434^2$ and $55^5$

See A116086 in Sloane's OEIS for a listing of the perfect powers beginning primeless ranges before the next perfect power. As of 2007, no further counterexamples have been found past $55^5$