Exploring primes: A first taste of abc

Imagine that one day, as you go about your daily business, you are suddenly abducted by aliens, quite unexpectedly. You are told by the captain of the alien spaceship that you will be executed 24 hours from now, unless by that time you have provided them with a prime number larger than one million. An already stressful situation is made somewhat worse, as you realize you forgot to grab an electronic device in the moment of abduction, so you have nothing but a pen and a little notebook found in your pocket.

How would you go about solving this problem?

Perhaps you have already memorized the list of primes up to and beyond one million. That would have come in handy.

Perhaps you will try some of the numbers immediately following one million, and check by hand if they are divisible by any prime smaller than one thousand (and a tiny bit more). You could probably make a list of these primes by spending a precious hour or so with the sieve of Eratosthenes. The prime number theorem suggests there are roughly $1000 / \ln(1000) $ such primes, which would be $145$, and in fact there are $168$ of them. Working by hand, it is possible to check for example if the number $1000001$ is divisible by any of these primes, but you might want to deprioritize a good night's sleep and pray to some higher power that a prime number is conveniently placed somewhere quite early after one million. Of course, you take heart from the fact that the average prime gap in that region is around $ \ln(1000000)$, which is $14$.

After a brief and successful search, you find that $1000003$ is actually a prime. Phew! After double-checking your calculations throughout the night, you hand over the prime number to the captain, and upon your immediate release you can now go back to your ordinary life. You check with a digital device that had you made a mistake in checking $1000003$, the subsequent primes you could have found would have been $1000033$ and then the twin primes $1000037$ and $1000039$.

Mindful of the abduction experience, you may be reflecting in the following days (and nights) on whether there is a way to produce large primes, or at least produce some numbers that have very large prime factors. There is of course a host of both deterministic and probabilistic primality tests more effective than naive trial-division, but I want to show you a funny way to produce such numbers, as an introductory and motivating example for future discussions of the abc conjecture.

Consider numbers of the form

\[ 2^a + 3^b \]

for positive integers $a$ and $b$. The Sage code below will generate a table of these numbers in prime-factored form, for $a$ and $b$ in the range $1$ to $4$.

Perhaps a bit surprisingly, almost all of these numbers are prime! This seems highly relevant for future abduction events. In fact, they are all prime except when $a+b = 6$, in which case they happen to be divisible by $5$. (Why is this so?)

You can increase the number $N$ in the code to get a larger table. For which $a$ and $b$ do you get actual primes? Do you see some patterns in when for example $5$ or $7$ appears as a prime factor? Are there any values of $a$ and $b$ for which all of the prime factors are small?

You can in fact quite easily increase the table to the point where primes above one million begin to appear.

You can also change the base numbers $2$ and $3$ to, for example, $2$ and $5$. Are the resulting numbers also likely to have large prime factors?