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

sy.isprime(n)

True if \(n\) is prime, False otherwise.

sy.factorint(n)

The prime factorization of \(n\), as a dict mapping each prime to its exponent.

sy.prime(k)

The \(k\)th prime number (sy.prime(1) is \(2\)).

sy.nextprime(n)

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

\[\begin{split} \begin{aligned} A_1(x) &= \{p\in\mathbb{N}:p~\text{is prime},~p\leq x,~\text{and}~p \equiv 1 \bmod 4\}, \\ A_3(x) &= \{p\in\mathbb{N}:p~\text{is prime},~p\leq x,~\text{and}~p \equiv 3 \bmod 4\}, \end{aligned} \end{split}\]

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

\[ \lim_{x\to \infty} \frac{\pi_1(x)}{\pi_3(x)} = 1, \]

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.