WOO logo

Wizard Recommends

Proof there is no Largest Prime

This week we continue our journey into mathematical proofs. Today we will do a common one, proving there is no largest prime number. As usual, it is my goal to explain them using as simple English as possible and avoid difficult mathematical notation. However, before we get to that, I present the usual weekly logic puzzle.

Logic Puzzle

You are at a 106-story building. Floors are numbered 0 to 105 (as most of the world numbers floors outside the US). You want to test for the highest floor you can safely drop an egg from into a large box of feathers on the ground. You know an egg dropped from the roof will break and one dropped from floor 0 will survive. You have two eggs to experiment with. What is the fewest drops you will need in a worst-case scenario?

The answer and solution appear at the end of the column.

Proof there is no Largest Prime

I will prove there is no largest prime by contradiction. In other words, I’ll disprove the opposite – that there is a largest prime.

Let’s call the largest prime pn, meaning it is the nth prime number, let’s label all the primes in order as follows:

p1 = 2, p2 = 3, p3 = 5, p4 = 7, … pn=?

Consider a number N as follows:

N = p1×p2× p3× p4× … ×pn+1.

If N is prime then no smaller prime should divide into it evenly. However, if we divide any prime up to pn into it, we will get a remainder of 1. That can only be explained two possible ways:

  1. N itself is prime, which must be larger than pn.
  2. There is some prime larger than pn that divides evenly into N.
 

Either way, we have shown there is some larger prime than pn.

Let’s look at a small prime for example. I’ll go see what happens if we assume 31 is the largest prime. In this case:

N = 2×3×5×7×11×13×17×19×23×29×31 + 1 = 1,805,044,411,171

Using a prime factors calculator we find 1,805,044,411,171 = 1,061,729 x 1,700,099. So, we have found two larger primes than 31: 1,061,729and 1,700,099

To site another example, assume7 is the largest prime. Then N = 2×3×5×7 + 1 = 211. Doing a prime factorization test on 211, we find that 211 is prime. Thus, we found a larger prime than 7.

No matter what prime we assume is the largest, this method will find a larger one.

Answer to Logic Puzzle

14

Here is how to achieve discovering the highest safe floor with no more than 14 drops.

  1. Drop first egg from 14th floor. If it breakes, test floors 1 to 13 one at a time. Maximum drops needed if it breaks = 14 (1 with first egg and 13 with second). Otherwise, go to step 2.
  2. Go up 13 floors, dropping first egg from 27th floor. If it breakes, test floors 15 to 26 one at a time. Maximum drops needed if it breaks = 14 (2 with first egg and up to 12 with second). Otherwise, go to step 3.
  3. Go up 12 floors, dropping first egg from 39th floor. If it breakes, test floors 28 to 38 one at a time. Maximum drops needed if it breaks = 14 (3 with first egg and up to 11 with second). Otherwise, go to step 4.
  4. Go up 11 floors, dropping first egg from 50th floor. If it breakes, test floors 40 to 49 one at a time. Maximum drops needed if it breaks = 14 (4 with first egg and up to 10 with second). Otherwise, go to step 5.
  5. Go up 10 floors, dropping first egg from 60th floor. If it breakes, test floors 51 to 59 one at a time. Maximum drops needed if it breaks = 14 (5 with first egg and up to 9 with second). Otherwise, go to step 6.
  6. Go up 9 floors, dropping first egg from 69th floor. If it breakes, test floors 61 to 68 one at a time. Maximum drops needed if it breaks = 14 (6 with first egg and up to 8 with second). Otherwise, go to step 7.
  7. Go up 8 floors, dropping first egg from 77th floor. If it breakes, test floors 70 to 76 one at a time. Maximum drops needed if it breaks = 14 (7 with first egg and up to 7 with second). Otherwise, go to step 8.
  8. Go up 7 floors, dropping first egg from 84th floor. If it breakes, test floors 78 to 83 one at a time. Maximum drops needed if it breaks = 14 (8 with first egg and up to 6 with second). Otherwise, go to step 9.
  9. Go up 6 floors, dropping first egg from 90th floor. If it breakes, test floors 85 to 89 one at a time. Maximum drops needed if it breaks = 14 (9 with first egg and up to 5 with second). Otherwise, go to step 10.
  10. Go up 5 floors, dropping first egg from 95th floor. If it breakes, test floors 91 to 94 one at a time. Maximum drops needed if it breaks = 14 (10 with first egg and up to 4 with second). Otherwise, go to step 11.
  11. Go up 4 floors, dropping first egg from 99th floor. If it breakes, test floors 96 to 98 one at a time. Maximum drops needed if it breaks = 14 (11 with first egg and up to 3 with second). Otherwise, go to step 12.
  12. Go up 3 floors, dropping first egg from 102nd floor. If it breakes, test floors 100 and 101 one at a time. Maximum drops needed if it breaks = 14 (12 with first egg and up to 2 with second). Otherwise, go to step 13.
  13. Go up 2 floors, dropping first egg from 104th floor. If it breakes, test floor 103. Maximum drops needed if it breaks = 14 (13 with first egg and 1 with second). Otherwise, go to step 14.
  14. Go up 1 floor, dropping first egg from 105th floor. If it breaks, the highest safe floor is 104. If it survives, the highest safe floor is 105.
 

The general strategy for an n-story building is finding the optimal floor to do the first drop. If the first test passes, you go up from there the same number of floors minus 1. If that second test passes, then you go up again one less than the last you went up the last time. Keep repeating this, going up one less floor than the previous increase between tests. If a test with the first egg fails, then use the second egg to systematically test every floor between the last two tests, starting with the lowest floor in that range.

Notice the increase in floors goes n, n-1, n-2, ... 1. The sum of all these jumps is n(n+1)/2. The key is finding the lowest possible integer value of n where the sum of the series is equal or greater than the number of floors in the building.

For example, let's look at a 500-story building (not counting the safe ground floor), solve for:

n(n+1)/2 = 500

n(n+1) = 1000

n2 + n -1000 = 0

Using the Pythagorean formula:

n = (-1 +/-√4001)/2 =~ 31.13

However, floors have integer values. So, we round up to n=32. Thus, in the case of a 500-story (or 501 if counting the safe ground floor), we do the first test from floor 32.