All primes greater than 5 end in either 1, 3, 7, or 9. If n is an integer, 2n + 3 will always be odd, but not necessarily prime. If we further require that n not be a multiple of 3, we eliminate all odd multiples of 3 since 2n + 3 will always be a multiple of 3 if n is a multiple of 3. We can also require that n be an integer whose last digit is not 1, because in those cases, 2n + 3 will always have 5 as the last digit. Likewise, if the last digit of n is a 6, the last digit of 2n + 3 will be 5.
If the conjecture is true, then it makes sense that 1 cannot be written form 2n + 3 since it is not prime. Also, it intuitively makes sense that all other primes would be some combination of the two smallest primes.
Let's make a table
n 2n + 3 prime?
0 3 yes
1 5 yes
2 7 yes
4 11 yes
5 13 yes
7 17 yes
8 19 yes
10 23 yes
13 29 yes
14 31 yes
17 37 yes
19 41 yes
20 43 yes
22 47 yes
23 49 no
25 53 yes
28 59 yes
29 61 yes
32 67 yes
34 71 yes
35 73 yes
37 77 no
38 79 yes
40 83 yes
43 89 yes
44 91 yes
For larger primes, we know that because of the possible last digits, the result of subtracting 3 will always be an even number, and so the result can always be written in the form of 2n.
I have a hunch I'm missing something but feel I'm on the right track. Could this be a new primality test? It may even be a way to find the next largest prime. It seems the conjecture occasionally returns a perfect square or a semiprime instead of a prime number.
The largest known prime number is 2^136279841 − 1. That's not really relevant for the conjecture, but I thought I'd put it here. The prime numbers used for RSA and other modern cryptography are in the range of about 2^300, which has roughly 100 digits.
Let's try n = 100,000.
2n + 3 = 200,003
200,003 is prime.
n = 1,000,000
2n + 3 = 2,000,003
2,000,003 is prime.
n = 5,000,000,000
2n + 3 = 10,000,000,003
10,000,000,003 = 13 × 769231
Well, looks like I have to think about this some more.