Unsolved: Perfect Numbers and Mersenne Primes

In an earlier post I talked about perfect numbers, and how it was still unknown whether there are any odd perfect numbers. There's another unsolved problem surrounding the perfect numbers, and this one intersects with a special set of numbers that you may have heard of, the Mersenne primes.

Mersenne numbers and Mersenne primes

Mersenne numbers take their name from the French monk and mathematician Father Marin Mersenne, even though they were studied as long ago as the times of Euclid. You construct Mersenne numbers by subtracting 1 from a power of 2.

M_n = 2ⁿ - 1

The following table details the construction of the first sixteen Mersenne numbers.

n	2n	2n - 1
1	2	1
2	4	3
3	8	7
4	16	15
5	32	31
6	64	63
7	128	127
8	256	255
9	512	511
10	1024	1023
11	2048	2047
12	4096	4095
13	8192	8191
14	16384	16383
15	32768	32767
16	65536	65535

If you look closely at the highlighted fields you may notice what mathematicians have known for centuries. A Mersenne number (2ⁿ - 1) cannot be prime unless the exponent n is prime. This is often expressed with a slightly different notation.

M_p = 2^p - 1

What wasn't known in the time of the ancient Greeks was whether or not the exponent being prime meant that M_p would always be prime. It wasn't until the 16th century, when it was discovered that 2¹¹ - 1 = 2047 is not prime, that this question was finally settled (2047 = 23 * 89). In order for M_p to be prime, it is necessary but not sufficient for the exponent p to also be prime.

Constructing Perfect Numbers

Perfect numbers have also been studied since the times of the early Greek mathematicians. It was Euclid who first discovered that the first four perfect numbers are given by the formula

P = 2^p-1 * (2^p - 1)

6 = 2¹ * (2² - 1)
28 = 2² * (2³ - 1)
496 = 2⁴ * (2⁵ - 1)
8128 = 2⁶ * (2⁷ - 1)

It wasn't until 1849 that it was shown by Euler (in a paper published after his death) that all even perfect numbers are of the form 2^p-1 * (2^p - 1), where (2^p - 1) is a Mersenne prime.

Since every even perfect number corresponds to a Mersenne prime (and vice versa), searching for perfect numbers is the same as searching for Mersenne primes. This leads us to two unsolved problems.

It isn't known if there are infinitely many even perfect numbers.

It isn't known if there are infinitely many Mersenne primes.

(In fact, given the 1-to-1 correspondence between even perfect numbers and Mersenne primes, it really wouldn't be incorrect to say that either one of these problems is just a restatement of the other.)

The largest prime number yet discovered as of this writing is the Mersenne prime 2^43,112,609 - 1, which has a starggering 12,978,189 digits. The corresponding perfect number, 2^43,112,608 * (2^43,112,609 - 1), has 25,956,377 digits.


Additional reading

In this article I've barely scratched the surface of prime number research. There is a very large network of people and computers dedicated to the search for Mersenne primes. For more information (and to possibly join in the search) have a look at the Great Internet Mersenne Prime Search (GIMPS).

Unsolved: Odd Perfect Numbers

A perfect number is a number that is the sum of its proper divisors (i.e., including 1 but excluding itself).

For example, the smallest perfect number is 6.

1 + 2 + 3 = 6

The next two perfect numbers are

1 + 2 + 4 + 7 + 14 = 28
1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248 = 496

See sequence A000396 in OEIS for a list of the first ten perfect numbers.

On a related note, a number that is smaller than the sum of its proper divisors is an abundant number, while a number greater than the sum of its proper divisors is called deficient. The smallest abundant number is 12, whose proper divisors sum to 16.

All of the perfect numbers that have been discovered so far are even.

The problem is to find an odd perfect number, or prove that no odd perfect numbers exist.

If there is an odd perfect number, we already know a lot about it. It must be at least 300 digits long, with at least 75 prime factors, at least 9 of them distinct. Its largest prime factor must be greater than 100,000,000. Its second largest prime factor is greater than 10,000, and its third largest is greater than 100.

Unsolved: Twin Primes Conjecture

Prime numbers, as most school children can tell you, are those numbers that are evenly divisible by only themselves and 1. The first few primes are

2, 3, 5, 7, 11, 13, 17...

We've known that there are infinitely many primes since c. 300 BC when it was proven by Euclid of Alexandria. Euclid used a very simple and elegant proof by contradiction.

Euclid's proof of the infinitude of primes

First, assume that there are a finite number of primes, p1, p2, p3, ..., pn.

Now let

Q = (p1 * p2 * ... * pn) + 1

That is, Q is equal to all of the primes multiplied together plus one.

By the Fundamental Theorem of Arithmetic, Q is either prime or it can be written as the product of two or more primes. However, none of the primes in our list evenly divides Q. If any prime in our list did evenly divide Q, then that same prime would also evenly divide 1, since

Q - (p1 * p2 * ... * pn) = 1

This contradicts the assumption that we had listed all the primes. So no matter how many primes we start with in our list, there must always be more primes. (Note that this proof does not claim that Q itself is prime, just that there must be some prime not in the initial list.)


Twin primes

Twin primes are those pairs of numers that have a difference of two, and that are both prime.

3, 5
5, 7
11, 13
17, 19
...

The Twin prime conjecture, which dates back to the 18th century, simply states that there are infinitely many twin primes.

Given the simplicity of Euclid's proof of the infinitude of primes, it's tempting to hope for an equally simple proof to the Twin prime conjecture. Needless to say, such a proof has not been found.


Other facts about twin primes:

Other than (3, 5), all twin primes have the form (6n - 1, 6n + 1).

In 1919 Viggo Brun showed that the sum of the reciprocals of the twin primes converges to a definite number, now known as Brun's constant (approximately 1.902160578).

In 1994, while in the process of estimating Brun's constant by calculating the twin primes up to 10¹⁴, Thomas Nicely discovered the infamous Pentium bug.

The largest known twin primes (as of January 2010) are a pair of 100,355 digit primes with the values 65516468355 * 2³³³³³³ ± 1.

Unsolved: Goldbach conjecture

The Goldbach conjecture is one of the oldest and easiest-to-understand math problems that remains unsolved. The problem was originally posed to Leonhard Euler in a letter from amateur mathematician Christian Goldbach in 1742. The original form of the conjecture, now known as the weak Goldbach conjecture says:

Every whole number greater than five is the sum of three prime numbers.

Euler restated the problem in an equivalent form, the strong Goldbach conjecture (or just the Goldbach conjecture):

Every even number greater than two is the sum of two primes.

So,

4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 5 + 5
12 = 5 + 7
...
100 = 47 + 53
...

Progress

In 1966, Chinese mathematician Chén Jǐngrùn showed that every sufficiently large even integer is the sum of a prime and semiprime (a number that has at most two prime factors).

Brute force methods have been used to show that the Goldbach conjecture is true for even integers up to about 1.5 * 10¹⁸* (1,500,000,000,000,000,000 or 1.5 billion billion).


Notes:

* Brute force results are as of July 24, 2009. See Goldbach conjecture verification for up-to-date results.

Unsolved: Collatz conjecture

First proposed in 1937 by the German mathematician Lothar Collatz, the Collatz conjecture is also known as the 3n + 1 problem, Kakutani's problem, the Syracuse problem, Thwaites' conjecture, and Ulam's conjecture. The conjecture starts with the following simple procedure:

1. Let n be any natural number (n > 0).
2. If n is odd, triple it and add 1 (n = 3n + 1).
3. If n is even divide it in half (n = n/2).
4. Stop if n = 1, otherwise go back to step 2.

The Collatz conjecture asks:

Does the above process always terminate (end with n = 1) for any starting value of n?

For example, starting with a value of n = 42, we get the following sequence

{ 42, 21, 64, 32, 16, 8, 4, 2, 1 }

The sequences produced by the Collatz procedure are known as hailstone sequences.

The conjecture remains unanswered, although it has been proven that the process terminates for all values of n up to 5.764 × 10¹⁸. In 1972, John Conway proved that it is possible for problems of this type to be undecidable, so it is not known if a solution is even possible.

Unsolved: The Perfect Cuboid Problem

In Tomorrow's Math, C. Stanley Ogilvy asks

Does there exist a rectangular parallelepiped (box) all of whose edges and face diagonals are of integral length, and the length of whose main diagonal is also an integer?

Put another way, can you construct a rectangular solid where all three edge lengths, all three face diagonals, and the long space diagonal have integer values (or prove that such a box cannot be constructed)?



This deceptively simple-sounding problem is known as the Perfect Cuboid Problem (among other names). It is closely related to the problem of finding an Euler Brick, which has many solutions, the smallest of which is a box with edges 125, 244, and 267.

No perfect cuboids were found during an exhaustive search of the integers up to 100 billion (10¹⁰). This lends evidence (but is far from a proof) to the suspicion that no perfect cuboids exist. One near miss is the cuboid that has edges with lengths 44, 117, and 240, and diagonals with lengths 125, 244, and 267.