For $a>0$ prime $p=a+b$ and $p\cdot a+b$ and $p\cdot b+a$ gives all primes

Question

How many primes will not be found from prime $p=a+b$ and prime producing formulae $a\cdot p+b$ and $b\cdot p+a$? An example for $11=2+9$ gives $2\cdot 11+9=31$ and $9\cdot 11+2=101$. Is there a maximum prime that will not be found? The larger the prime, the more numbers produced, $p-1$ of them; so it seems inevitable that all but a few primes will not be found. Do you agree?

Answer 1

If I understand what you're asking correctly, then the answer to your main question is almost definitely no, there is no maximum prime that will not be found. First, let me state a few things I am assuming here. First, the $a$ and $b$ are meant to be non-negative integers. Second, note that you don't need to check both $ap + b$ and $bp + a$ since if $p = a + b$, then $p = b + a$ also, so each check would be duplicated. As such, I will just only consider all possible $ap + b$. Replacing $b$ with $p - a$ gives

$$ap + \left(p - a\right) = \left(a + 1\right)p - \left(a + 1\right) + 1 \tag{1}\label{eq1}$$

Now, you are asking to check for $a$ going from $1$ to $p - 1$, inclusive. I will replace $a + 1$ with $c$, with it going from $2$ to $p$, inclusive, to get

$$cp - c + 1 = c\left(p - 1\right) + 1 \tag{2}\label{eq2}$$

Among the primes to check, consider the Sophie Germain primes, i.e., which are primes $q$ where $2q + 1$ is also a prime. Assume there is a $c \ge 2$ and $p$ which allows \eqref{eq2} to be equal to $2q + 1$. This then gives

$$2q + 1 = c\left(p - 1\right) + 1 \tag{3}\label{eq3}$$

which simplifies to

$$2q = c\left(p - 1\right) \tag{4}\label{eq4}$$

Now, if $p = 2$, then $2q = c$, but $2 \le c \le p$, so $c = 2$ is the only value, resulting in $q = 1$, which is not prime. For $p \gt 2$, $p$ is odd and so must be of the form $2n + 1$ for some positive integer $n$. Thus, $p - 1 = 2n$, with \eqref{eq4} now becoming

$$q = cn \tag{5}\label{eq5}$$

However, with $q$ being a prime, then $q = c$ and $n = 1$, or $q = n$ and $c = 1$. Since $c \ge 2$, as stated earlier, this requires that $c = q$ and $n = 1$. This means that just $p = 3$ can possibly work, giving the only Sophie Germain primes your algorithm creates being $2$, with $5 = 3 \times 1 + 2$, plus $3$, with $7 = 3 \times 2 + 1$. All other primes coming from Sophie Germain primes, starting with $5$ where $11 = 2 \times 5 + 1$ as you have noticed yourself, will not work!

It's an unproven conjecture that there are an infinite # of Sophie Germain primes. However, I believe it's likely true as it would be an very unusual property of primes, IMHO, for the set of these primes to be finite.

There also other types of primes which generally will not work. Consider, for example, where both $q$ and $4q + 1$ are primes. I'm not aware of any general name for these types of primes. Anyway, \eqref{eq5} then becomes

$$2q = cn \tag{6}\label{eq6}$$

As before, $q$ must divide $c$ or $n$. If it divides $c$, then $c = q$ and $n = 2$, which means $p = 5$, with the only $q$ which works being $3$, giving the prime to create being $13 = 4 \times 3 + 1$ and, from your algorithm, $13 = 2 \times 5 + 3$. If $q$ doesn't divide $c$, then it must divide $n$, so $q = n$ and $c = 2$. However, this means that $p = 2n + 1 = 2q + 1$. But this can't be true in general as it means that $q$, $2q + 1$ and $4q + 1$ must all be prime simultaneously. To see this, if $q$ is not $3$, then $q \equiv 1 \pmod 3$ (with $2q + 1 \equiv 0 \pmod 3$ in this case) or $q \equiv 2 \pmod 3$ (with $4q + 1 \equiv 0 \pmod 3$ in this other case). As such, only $q = 3$ works. There are also undoubtedly an infinite number of cases where both $q$ and $4q + 1$ are prime, starting with $7$ and $29$, so this is another set of values which won't work for you.

Consider more generally where $q$ and $2dq + 1$ are prime, for some fixed integer $d \gt 2$. Using analysis similar to what I've done above will result in at least relatively stringent requirements (especially for smaller $d$) which may allow many values to work, but I suspect there will also be quite a few cases that don't, especially for larger $q$. As such, unfortunately, it seems there are a quite few other types of primes, other than just those associated with Sophie Germain ones, that won't work with your algorithm.