A positive integer $n$ is called prime if the only positive integers that divide $n$ are $1$ and itself. For example, $7$ is prime since it is only divisible by $1$ and $7$, while $8$ is not prime since it is divisble by $2$ and $4$. Prime numbers play a key role in the study of integers, and thus are of great interest to mathematicians. For example, mathematicians have long studied the density and distribution of prime numbers. Note that, aside from the pair of primes ($2, 3$), no other prime numbers are adjacent (since $2$ is the only even prime number). That is, no other pair of prime numbers differ by $1$. In this report, we are interested in studying pairs of prime numbers that differ by $2$, which we will call twin primes.
In order to find twin primes, it will first be useful to be able to find prime numbers. To that end, we will introduce a function is_prime that takes in an integer n and returns True if n is prime, and False otherwise.
... more explanation on how is_prime works, including an explanation about the sqrt(n) optimization that was discussed in class...
# Import the square root function
from math import sqrt
def is_prime(n):
# Check for divisors between 2 and sqrt(n)
for d in range(2,int(sqrt(n))+1):
# Check if d divides n
if n % d == 0:
return False
return True
We now test the use of is_prime on some known examples of prime and non-prime numbers:
is_prime(7)
True
is_prime(8)
False
We see that the function correctly identifies 7 as prime and 8 as not prime.
We can use the is_prime function to easily generate lists of prime numbers. To do so, we will define a function get_primes that takes in an integer N and returns a list containing all primes n such that n < N.
def get_primes(N):
# Initialize an empty list of twin primes
primes = []
# Check if n is prime for n = 2, 3, ..., N-1
for n in range(2,N):
if is_prime(n):
# If n is prime, add it to the list
primes.append(n)
return primes
We can now use this function to find prime numbers.
N = 30
primes = get_primes(N)
print('Prime numbers less than {}:'.format(N))
print(primes)
Prime numbers less than 30: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Now that we can use Python to identify prime numbers, we are ready to search for false primes. We will first define a function is_twin_prime that takes in an integer n and returns True if the pair (n,n+2) are twin primes, and False otherwise. This function will make use of the earlier defined is_prime function.
def is_twin_prime(n):
# Check whether both n and n+2 are prime
if is_prime(n) and is_prime(n+2):
return True
else:
return False
Once again, we will test our is_twin_prime function on some simple cases. For example, the pair $(5,7)$ are twin primes since both $5$ and $7$ are prime. This we can confirm by calling is_twin_prime(5).
is_twin_prime(5)
True
On the other hand, the pair $(7,9)$ are not twin primes since $9$ is not a prime number.
is_twin_prime(7)
False
From these examples, our is_twin_prime function appears to be working correctly. We are now ready to search for twin primes. To do so, we will define a function get_twin_primes that takes in an integer N and returns a list containing all twin primes (n,n+2) such that n < N.
def get_twin_primes(N):
# Initialize an empty list of twin primes
twin_primes = []
# Check if (n,n+2) are twin primes for n = 2, 3, ..., N-1
for n in range(2,N):
if is_twin_prime(n):
# If (n,n+2) are twin primes, add them to the list
twin_primes.append((n,n+2))
return twin_primes
We can now use this function to find twin primes.
twin_primes = get_twin_primes(10000)
We now check a portion of the twin_primes list to see the first 10 twin primes:
num_to_show = 10
print('The first {} twin primes:'.format(num_to_show))
print()
print(' n | n+2')
print('---------')
for (n,m) in twin_primes[:num_to_show]:
print('{0:>3} | {1:>3}'.format(n,m))
The first 10 twin primes: n | n+2 --------- 3 | 5 5 | 7 11 | 13 17 | 19 29 | 31 41 | 43 59 | 61 71 | 73 101 | 103 107 | 109
Now that we are able to generate lists of twin primes, we can start to study their properties. For example, what is the density of twin prime numbers? We can explore this by counting the number of twin primes less than a maximum N for several different choices of N, which we do below.
We first will define a list Nlist of N values. For each value N, we will generate a list of all twin primes less than N, and store this list of twin primes inside another list called twin_primes_lists. For later convenience, we will simultaneously generate and store lists of all primes (whether prime or not) less than N for each N.
# Define list of N values, which will give an upper bound
# on the twin primes that will be sought
Nlist = [10**i for i in range(2,7)]
# Initialize an empty list that will store lists of twin primes
twin_primes_lists = []
# Initialize an empty list that will store lists of primes
primes_lists = []
for N in Nlist:
# for each N in Nlist, find all twin primes less than N
twin_primes = get_twin_primes(N)
# store the list of twin primes inside twin_primes_lists
twin_primes_lists.append(twin_primes)
# for each N in Nlist, find all primes less than N
primes = get_primes(N)
# store the list of primes inside primes_lists
primes_lists.append(primes)
Now that we have generated this data, let us look at the density of twin primes over each subset. That is, we will count how many integers less than N are twin primes. We can easily do this by dividing the length of each list of twin primes by the corresponding maximum N.
for N, twin_primes in zip(Nlist, twin_primes_lists):
# For each maximum N and corresponding list of twin primes less than N,
# divide the length of the list by N to calculate the density of twin primes
ratio = len(twin_primes) / N
print('{0:5.2f}% of integers less than {1:>7} are twin primes.'.format(100*ratio,N))
8.00% of integers less than 100 are twin primes. 3.50% of integers less than 1000 are twin primes. 2.05% of integers less than 10000 are twin primes. 1.22% of integers less than 100000 are twin primes. 0.82% of integers less than 1000000 are twin primes.
It appears that the density of twin primes decreases as N increases. This might suggest that there are only finitely many twin primes, although that need not be the case. For comparison, we can also check the density of prime numbers (whether twin prime or not).
for N, primes in zip(Nlist, primes_lists):
# For each maximum N and corresponding list of primes less than N,
# divide the length of the list by N to calculate the density of primes
ratio = len(primes) / N
print('{0:5.2f}% of integers less than {1:>7} are primes.'.format(100*ratio,N))
25.00% of integers less than 100 are primes. 16.80% of integers less than 1000 are primes. 12.29% of integers less than 10000 are primes. 9.59% of integers less than 100000 are primes. 7.85% of integers less than 1000000 are primes.
It appears that the density of the prime numbers also decreases. On the other hand, it is a well-known fact that there are infinitely many prime numbers. With this in mind, we should not assume that there are only finitely many twin primes. Answering this question is beyond the scope of this report.
Finally, for completeness, we compare look at the density of twin primes within the set of prime numbers less than N for each N in our list Nlist.
for N, primes, twin_primes in zip(Nlist, primes_lists, twin_primes_lists):
# For each maximum N and corresponding list of twin primes less than N,
# divide the length of the list by N to calculate the density of twin primes
ratio = len(twin_primes) / len(primes)
print('{0:5.2f}% of primes less than {1:>7} are twin primes.'.format(100*ratio,N))
32.00% of primes less than 100 are twin primes. 20.83% of primes less than 1000 are twin primes. 16.68% of primes less than 10000 are twin primes. 12.76% of primes less than 100000 are twin primes. 10.41% of primes less than 1000000 are twin primes.
From this, we see that the density of twin primes diminishes even within the diminishingly dense subset of prime numbers.
We have found many examples of twin primes. Are there are any triplet primes? That is, can we find triples of integers $(n, n+2, n+4)$ such that $n$, $n+2$, and $n+4$ are all prime? The integers $(3,5,7)$ (with $n=3$) form triplet primes as an immediate example. Are there any others?
It is straight-forward to modify our existing functions to search for such triplets. We start by defining a function is_triplet_prime which takes in an integer n and returns True if (n, n+2, n+4) is a triplet prime, and False otherwise.
def is_triplet_prime(n):
# Check whether n, n+2, and n+4 are all prime
if is_prime(n) and is_prime(n+2) and is_prime(n+4):
return True
else:
return False
We can now search for triplet primes. We will start by searching through all positive integers n less than 10000 to see if (n,n+2,n+4) are triplet primes.
for n in range(2,10000):
if is_triplet_prime(n):
print('({},{},{}) is a triplet prime.'.format(n,n+2,n+4))
(3,5,7) is a triplet prime.
From this seach, we find only the one example, $(3,5,7)$. This suggests that there may not be any others, although it is not concrete proof. On the other hand, we can argue mathematically that these are the only possible triplet primes.
Suppose $(n,n+2,n+4)$ are triplet primes. Then $n$, $n+2$, and $n+4$ must all be odd numbers (since $2$ is the only even prime). On the other hand, at least one of $n$, $n+2$, and $n+4$ must be divisible by $3$. To see why, note that $n$, $n+2$, and $n+4$ all have different remainders after division by $3$. But the only possible remainders are $0$, $1$, and $2$. Thus one of them has remainder $0$ and is divisible by $3$. Since all are prime, this number must be exactly $3$. Finally, since $n=1$ is not a prime number, it must be the case that $n=3$, so that the triplet primes are $(3,5,7)$.
Instead of generalizing twin primes to triplet primes (which did not yield interesting results), we can instead look for other prime neighbors. For example, can we find primes that differ by $4$, $6$, $8$, etc? Note that we do not need to bother searching for primes that differ by an odd number, since all primes (aside from $n=2$) are odd.
We now write a function is_neighboring_prime that takes in integers n and k and returns True if both the pair (n,n+k) are prime and False otherwise.
def is_neighboring_prime(n,k=2):
# Check whether both n and n+k are prime
if is_prime(n) and is_prime(n+k):
return True
else:
return False
As an example, $n=7$ and $n=11$ are neighboring primes with a difference of $k=4$. We will use this as a test scase for our is_neighboring_prime function.
is_neighboring_prime(7,4)
True
We now define a function get_neighboring_primes that takes in integers N and k, and returns a list of all neighboring primes (n,n+k) with n < N.
def get_neighboring_primes(N,k=2):
# Initialize an empty list of neighboring primes
neighboring_primes = []
# Check if (n,n+k) are neighboring primes for n = 2, 3, ..., N-1
for n in range(2,N):
if is_neighboring_prime(n,k):
# If (n,n+k) are neighboring primes, add them to the list
neighboring_primes.append((n,n+k))
return neighboring_primes
We will test this function by generating a list of neighboring primes $(n,n+k)$ with $n < 100$ and $k=6$.
N = 100
k = 6
neighboring_primes = get_neighboring_primes(N,k)
To check the output, we will now print out the first 10 neighboring primes with $k=6$.
num_to_show = 10
print('The first {0} neighboring primes with k={1}:'.format(num_to_show,k))
print()
print(' n | n+2')
print('---------')
for (n,m) in neighboring_primes[:num_to_show]:
print('{0:>3} | {1:>3}'.format(n,m))
The first 10 neighboring primes with k=6: n | n+2 --------- 5 | 11 7 | 13 11 | 17 13 | 19 17 | 23 23 | 29 31 | 37 37 | 43 41 | 47 47 | 53
Now that we have some tools in place, we can explore neighboring primes further. In particular, we may ask how many neighboring primes there are for various distance values $k$. To measure this, we will count the number of neighboring primes $(n,n+k)$ with $n < 100,000$ for varying distance values $k$.
# Set a maximum integer for the neighboring primes
# that will be sought
N = 100000
# Define a list of distance values k that will be used.
# Only even values of k will yield neighboring primes
klist = [2*i for i in range(1,10)]
# Initialize an empty list that will store lists of neighboring primes
neighboring_primes_lists = []
for k in klist:
# for each k, find all neighboring primes (n,n+k) with n<N
neighboring_primes = get_neighboring_primes(N,k)
# store the list of neighboring primes in neighboring_primes_list
neighboring_primes_lists.append(neighboring_primes)
Let us now count the number of neighboring primes for each value of $k$:
print('Count of neighboring primes (n,n+k) for varying k:')
print()
print(' k | count')
print('----------')
for k,neighboring_primes in zip(klist, neighboring_primes_lists):
num_neighboring_primes = len(neighboring_primes)
print('{0:>2} | {1:>5}'.format(k,num_neighboring_primes))
Count of neighboring primes (n,n+k) for varying k: k | count ---------- 2 | 1224 4 | 1216 6 | 2447 8 | 1260 10 | 1624 12 | 2421 14 | 1488 16 | 1233 18 | 2477
From this data, we see that there are many neighboring primes for each value of $k$. Moreover, there are far more neighboring primes with a distance of $k=6$, $k=12$, and $k=18$ than the other distance values tested. This raises an interesting question: In general, are there more neighboring primes when $k$ a multiple of $6$ than when $k$ is not? While we could compile more data using Python, a more robust mathematical analysis may be required to truly answer this question. Such analysis is beyond the scope of this report.
We previously discovered that there is a unique triplet prime, $(3,5,7)$. Following our study of more general neighboring primes, we could revisit the idea of triplet primes and ask if there are triplet primes with different distance values $k$, that is prime triples $(n,n+k,n+2k)$. For example, $(5,11,17)$ and $(7,13,19)$ are triplet primes with distance $k=6$. For brevity, we leave such exploration out of this report, but encourage the reader to use the tools developed here to cary out their own exploration of this idea.
In this report, we have explored the idea of twin primes. We looked at the density of twin primes and found that they appear less and less dense as we search through more and more integers. Moreover, they become less dense even compared to subset of prime numbers as we search through larger and larger integers. It is not clear from our study whether or not there are infinitely many twin primes, which is an interesting question for future study. We have also looked into the idea of prime triplets, and found that there is a unique prime triplet $(3,5,7)$.
Finally, we looked at neighboring primes and found that many exist for many even distance values $k$. In particular, it seems that there are for more neighboring primes when $k$ is a multiple of $6$. Proving this statement is beyond the scope of this report, but is an interesting question for further study. In addition, we briefly considered the idea of triplet primes $(n,n+k,n+2k)$ with now varying distance values $k$, and leave further study to the reader.