Mathematics for the liberal arts (2013)
Part II. TWO PILLARS OF MATHEMATICS
Chapter 5. NUMBER THEORY
5.17 Unfinished Business
Number theory has been one of the most studied of mathematical topics, but one must not get the impression that all the important problems have been solved. This area is famous for problems that are easy to state and to understand, but devilishly difficult to solve. (The Devil himself is recruited in the search for a proof of Fermat’s Last Theorem in the short story “The Devil and Simon Flagg,” by Arthur Porges.) Here are a few unsolved problems for your enjoyment.
The Twin Prime Conjecture. If n and n + 1 are consecutive integers, one of them must be even, i.e., divisible by 2. This means that, if both n and n + 1 are primes, the numbers must be 2 and 3. Hence every pair of primes other than 2 and 3 is at least two apart. Twin primes are primes that are exactly two apart, for example 3 and 5, or 11 and 13, or 41 and 43. Primes get sparser as the numbers get larger, but does the supply of twin primes run out? A famous conjecture, the twin prime conjecture, is that there are infinitely many twin primes.
There is currently no proof, or disproof, of the twin prime conjecture. As of this writing, the largest pair of twin primes known is 65516468355 × 2333333 – 1 and 65516468355 × 2333333 + 1, each of which has 100,355 digits. These were found by a distributed computing project for twin primes.
Goldbach’s Conjecture. Goldbach’s conjecture is that every even number is the sum of two primes. So, for example, 8 = 3 + 5, and 110 = 31 + 79. This conjecture dates from correspondence in 1742 between Leonhard Euler and the Prussian mathematician Christian Goldbach (1690–1764). As with the twin prime conjecture, many people have worked on this one, and quite a few assertions of proofs have been made, but no actual proof has been discovered. As of this writing, the conjecture has been verified up to at least 1017.
The Collatz Problem. This one is of more recent vintage, and has a different flavor. It was proposed in 1937 by Lothar Collatz (1910–1990).
Let n be an integer greater than 1. If n is even, divide it by 2. If n is odd, multiply by 3 then add 1. Repeat until you get 1. Here are a couple of examples, starting with
Of course, there is no guarantee that this ends. Maybe you never get to 1. Maybe you get into an infinite loop, or keep getting larger and larger numbers. The conjecture is that, whatever your starting number, you always end up at 1.
The number of steps required to get to 1 may be fairly large; If you start with 2,362,741,986,945,773,554,503, it takes 2,589 steps to reach 1. There is a distributed computing project for this problem as well, at
http://boinc.thesonntags.com/collatz/+.
The Collatz conjecture has been verified by computer for many numbers. But no one has been able to prove it. The great number theorist Paul Erdos (1913-1996) said of this conjecture, “Mathematics is not yet ready for such problems.”
EXERCISES
5.91 Find ten pairs of twin primes.
5.92 Verify Goldbach’s conjecture for numbers up to 50.
5.93 Verify the conjecture of the Collatz problem for n = 13 and n = 104.
5.94 What happens in the Collatz problem if n is a power of 2?
5.95 Prove any of the conjectures in this section.