Prime Conjectures¶
Each conjecture on this page is about prime numbers and holds for its first several cases, but has a counterexample at a larger input.
SymPy for Number Theory¶
SymPy provides fast functions for working with prime numbers and factorizations.
Function |
Returns |
|---|---|
The prime factorization of \(n\), as a |
|
The \(k\)th prime number ( |
|
The smallest prime greater than \(n\). |
import sympy as sy
print(sy.isprime(97)) # 97 is prime.
print(sy.isprime(91)) # 91 = 7 * 13 is composite.
print(sy.factorint(84)) # 84 = 2^2 * 3 * 7.
print(sy.prime(10)) # The 10th prime.
print(sy.nextprime(100)) # The first prime after 100.
True
False
{2: 2, 3: 1, 7: 1}
29
101
The function sy.isprime() uses much faster tests than brute-force trial-division, so it can handle very large numbers.
print(sy.isprime(2425967623052370772757633156976982469681))
True
Euler’s Polynomial¶
Problem 2
In 1772, Euler discovered a polynomial that seems to produce prime numbers for each natural number input.
Disprove: For every nonnegative integer \(k\), the number \(k^2 + k + 41\) is prime.
Write a function named eulerpoly() that accepts a nonnegative integer \(k\).
Return True if \(k^2 + k + 41\) is prime and False otherwise.
Use eulerpoly() to find the smallest counterexample, that is, \(k_0\) such that \(k_0^2 + k_0 + 41\) is composite.
Store the value of \(k_0\) as the variable problem2_counterexample.
No Formula for Primes
No nonconstant polynomial with integer coefficients produces a prime for every nonnegative integer input, so every conjecture of this form has a counterexample.
Fermat Primes¶
Problem 3
Numbers of the form \(2^{2^k}+1\), for \(k = 0, 1, 2, \ldots\), are called Fermat numbers. The first few are \(3\), \(5\), and \(17\).
Disprove: For every nonnegative integer \(k\), the Fermat number \(2^{2^k}+1\) is prime.
Write a function named fermat() that accepts a nonnegative integer \(k\).
Return True if the Fermat number \(2^{2^k}+1\) is prime and False otherwise.
Use fermat() to find the smallest counterexample, that is, \(k_0\) such that \(2^{2^{k_0}}+1\) is composite.
Store the value of \(k_0\) as the variable problem3_counterexample.
Mersenne Primes¶
Problem 4
Numbers of the form \(2^p - 1\) where \(p\in\mathbb{N}\) are called Mersenne numbers, and a Mersenne number that is prime is called a Mersenne prime.
Disprove: For every prime number \(p\), the Mersenne number \(2^p-1\) is also prime.
Write a function named mersenne() that accepts a prime number \(p\).
Return True if \(2^p-1\) is prime and False otherwise.
Use mersenne() to find the smallest counterexample, that is, \(p_0\) such that \(2^{p_0}-1\) is composite and \(p_0\) is prime.
Store the value of \(p_0\) as the variable problem4_counterexample.
Record-Setting Primes
Most of the largest known primes are Mersenne primes. The Great Internet Mersenne Prime Search (GIMPS) finds new ones by testing \(2^p - 1\) for enormous primes \(p\) on volunteers’ computers.
Prime Number Races¶
Problem 5
Every prime number larger than \(2\) is odd, so it is congruent to either \(1\) or \(3\) modulo \(4\). Let \(\pi_1(x)\) denote the number of primes that are less than or equal to \(x\) and congruent to \(1\) modulo \(4\), and define \(\pi_3(x)\) likewise. That is, if
then \(\pi_1(x) = |A_1(x)|\) and \(\pi_3(x) = |A_3(x)|\). For example, \(A_1(15) = \{5,13\}\) and \(A_3(15) = \{3, 7, 11\}\), so \(\pi_1(15) = 2\) and \(\pi_3(15) = 3\).
Is \(\pi_1(x)\) or \(\pi_3(x)\) bigger? This problem is called a “prime number race.”
Disprove: \(\pi_3(x) \geq \pi_1(x)\) for all integers \(x \geq 3\).
Write a function named prime_race() that accepts an integer \(x \geq 3\).
Return \(\pi_1(x)\) and \(\pi_3(x)\).
Use prime_race() to find the smallest counterexample, that is, the smallest integer \(x\) such that \(\pi_3(x) < \pi_1(x)\).
Store the value of \(x\) as the variable problem5_counterexample.
Hint: Only prime values of \(x\) need to be checked (can you explain why?).
Test Cases
print(prime_race(15))
print(prime_race(100))
(2, 3)
(11, 13)
Who Wins the Race?
It has been proven that
so “at infinity” the prime number race ends in a tie. Even so, \(\pi_3(x)\) is ahead far more often than \(\pi_1(x)\), a phenomenon called Chebyshev’s bias.