The Largest Prime Number

On 7 January 2016 a “new” large prime number was discovered, with more than 22 million digits. Time for a blog about these numbers, which have fascinated mathematicians from Greek antiquity until present times.

Prime numbers are numbers that can only be divided by 1 and itself. For example 7 is a prime number, but 6 is not because it can be divided by 2 and 3. . Here is a list of the 168 prime numbers smaller than 1000. The number 2 is the only even prime, all others are odd.

prime-numbers

How many prime numbers are there?

Euclides

Euclides, the famous Greek mathematician, living in present-day Egypt  around 300 BC, already proved that their number is infinite, and his proof is so elementary, that I often presented it to my students when I was a teacher, as an example of what is called Reductio ad Absurdum.

Euclides’ proof:  Assume that you have a complete list of all prime numbers.

  • Multiply them together and add 1. Call this number X.
  • Because of the added 1, this number X can not be divided by any prime number in your list (there will always be a reminder 1)!
  • So there are only two possibilities, either X is prime itself, or it can be divided by a prime number outside your list. In both cases it shows your list was incomplete.
  • Therefore our assumption was wrong and the list of prime numbers is infinite!

How to find out if a number X is prime?   Do we  have to check whether X is divisible by any number, smaller than X ? That would be a tedious job. Fortunately it is not as bad as that…:-). Because it is easy to see that we only have to check whether X is divisible by any prime number, smaller than the square root of X.

For example X=283, is it prime? The square root of 283 = 16.82…, so we have only to check division by 2,3,5,7,11 and 13.

  • 283 / 2 = 141 rest 1
  • 283 / 3 = 94 rest 1
  • 283 / 5 = 56 rest 3
  • 283 / 7 = 40 rest 3
  • 283 / 11 = 25 rest 8
  • 283 / 13 = 21 rest 10

So 283 is a prime number!

This procedure is called Trial Division. For large numbers it becomes time consuming. For example, we want to check if 1000.003 is prime.  There are 168 prime numbers smaller than 1000, so we have to do 168 divisions to finally conclude that, yes, 1000.003 is prime. Repeating this procedure for 999.997, you will find that this number is not prime, it can be divided by 757.

Imagine that you have to do these divisions with only pen and paper!

Back to the recently discovered large mega-prime. It is a so-called Mersenne prime, one less than a power of 2:  Mp = 2p − 1 with p itself a prime number.

  • M2 = 22 − 1 = 4 – 1 = 3 prime!
  • M3 = 23 − 1 = 8 – 1 = 7 prime!
  • M5 = 25 − 1 = 32 – 1 = 31 prime!
  • M7 = 27 − 1 = 128 – 1 = 127 prime!

Could this be a rule to create prime numbers? Unfortunately that is not the case.       M11 = 211 − 1 = 2048 – 1 = 2047 = 23 * 89 , not prime!
However the next one M13 = 213 − 1 = 8192 – 1 = 8191 is again prime.
As are M17 = 131.071 and M19 = 524.287. The last two are already quite large, in 1588 the Italian mathematician Cataldi had proven by trial division that they were prime.

Why are these numbers called Mersenne primes?

Marin_mersenne

Marin Mersenne was a French priest with an interest in mathematics, theology and philosophy.

He published in 1644 a list of these numbers 2p − 1, stating that they were prime for p  = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257, and not for any other p below 257.

His list was incomplete and incorrect, but still these prime numbers carry his name…:-)

Incorrect, because M67 and M257 are composite
Incomplete, because M61 , M89 and M107 are prime

Mersenne was correct that M31 = 2.147.483.647 is prime, but how could he know? This is a big number, the square root is ~ 46.340, so he should first determine all prime numbers smaller than 46.340  (there are 4792) and then perform trial division for all those 4792 numbers. It must have been a lucky guess. And certainly it was a guess for M127 = 170.141.183.460.469.231.731.687.303.715.884.105.727 🙂

18th century mathematician Leonhard Euler

It was only in 1772, more than a century later,  that the great mathematician Leonhard Euler proved the primality of M31.

By a clever analysis of the general structure of Mersenne numbers, he managed to reduce the number of trial divisions to 84 !

Still a big job (pen and paper), the story is that he had a team of helpers to do the actual calculations.

This was the last result using trial division. For more than a century no developments regarding Mersenne primes took place.

Elucas_1

Until 1857, when Édouard Lucas, a young French boy (15 years old), gets interested to prove that M127 is prime.

As trial division is not feasible for these large numbers, he studies the structure of the Mersenne numbers and develops a method to check the primality without trial divisions.

After 19 (!) years of testing his methods, he is convinced and announces in 1876 that M127 is prime. The 9th Mersenne prime!

His approach, later refined by others, is still used in the search for new Mersenne primes. Characteristic for this Lucas–Lehmer primality test is that it can decide that a Mersenne number is NOT prime, without finding the factors of this number. For example, using this test, we find that M257 = 231.584.178.474.632.390.847.141.970.017.375.815.706.539.969.331.281.128.078.915.168.015.826.259.279.871 is composite, but we don’t know its factors…:-)

With Lucas’ method, in the following years/decades the primality of M61 , M89 and M107 is proven. Still using pen and paper!

New activity starts only in the 20th century when the first computers are built.

SWAC_001

One of them is the famous SWAC computer, built in 1950. Nowadays a PC or even a tablet would be more powerful.

In 1952 it was used to check new Mersenne primes. Within one year 5 new ones were found, for p = 521, 607, 1279, 2203  and 2281. Still using the methods developed by Lucas

Very large numbers! Here is prime number M2281 with 687 digits. To make it more readable, spaces have been inserted after three digits.

446 087 557 183 758 429 571 151 706 402 101 809 886 208 632 412 859 901 111 991 219 963 404 685 792 820 473 369 112 545 269 003 989 026 153 245 931 124 316 702 395 758 705 693 679 364 790 903 497 461 147 071 065 254 193 353 938 124 978 226 307 947 312 410 798 874 869 040 070 279 328 428 810 311 754 844 108 094 878 252 494 866 760 969 586 998 128 982 645 877 596 028 979 171 536 962 503 068 429 617 331 702 184 750 324 583 009 171 832 104 916 050 157 628 886 606 372 145 501 702 225 925 125 224 076 829 605 427 173 573 964 812 995 250 569 412 480 720 738 476 855 293 681 666 712 844 831 190 877 620 606 786 663 862 190 240 118 570 736 831 901 886 479 225 810 414 714 078 935 386 562 497 968 178 729 127 629 594 924 411 960 961 386 713 946 279 899 275 006 954 917 139 758 796 061 223 803 393 537 381 034 666 494 402 951 052 059 047 968 693 255 388 647 930 440 925 104 186 817 009 640 171 764 133 172 418 132 836 351

IBM_7090_computer

Computers became more powerful, and new Mersenne primes were discovered. In 1961 the first Mersenne prime with more than 1000 digits was found, M4253, using an IBM 7090 mainframe computer (pic left)

And in 1979 the first Mersenne prime with more than 10.000 digits was found, M44.497, using a Cray supercomputer.

You might expect that the recently discovered Mersenne prime M74.207.281 with more than 22 million digits has been found using a super-super computer…:-)  But that is not the case! Actually PC’s were used, not one but many, working together!

In 1996 the Great Internet Mersenne Prime Search ( GIMPS) project was started. It is an example of what is called  distributed computing.  A PC will often be idle, so why not  let it work during that time for a project such as GIMPS. Just download some software and your PC will try to find a new Mersenne Prime. Many thousands of volunteers are doing this. And with success

Since 1996, 15 new Mersenne primes have been found, all of them using GIMPS!

Of course finding a new Mersenne prime has no scientific value, it is just an intellectual challenge. But you might win a prize!

When in 1999 the first Mersenne prime was found with more than 1 million digits,M6.972.593 , the Electronic Frontier Foundation awarded this result with a prize of 50.000 US$. In 2008 M37.156.667 was found, with more than 10 million digits. The award was 100.000 US$

Two more prizes have not yet been awarded

  • 150.000 US$ to the first individual or group who discovers a prime number with at least 100 million digits
  • 250.000 US$ to the first individual or group who discovers a prime number with at least  1 billion digits

The latest Mersenne prime M74.207.281 has 22.338.618 digits, not yet enough for the next reward

So, why not join GIMPS!  I did….:-)

For this blog I have made extensive use of The Prime Pages

Large numbers have been calculated using the Online Big Number Calculator

Fibonacci (part 2)

In part 1 we have seen that the Fibonacci series can be generated by a simple rule: start with 1, 1 then adding the last two numbers of the series gives the next one

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765 ...

When you take the ratio of two consecutive Fibonacci numbers, this ratio approaches the Golden Ratio φ (phi) = 1.61803.. as you proceed in the series. And we have seen the close relation between the Fibonacci numbers and the Golden Spiral. Take note in the picture below of the rectangle containing the spiral. The ratio between width and height is φ. You will not be surprised that it is called the Golden Rectangle..:-)

Golden spiral

Has all or any of this a relation with the world around us? It is said that the Golden Rectangle is pleasing to the eye and that therefore many paintings have that format. It is said that the Parthenon temple in Athens was designed with φ in mind. There are people who believe that φ ( like π ) can be found in the dimensions of the  Pyramid of Cheops. And that the spiral arms of galaxies are Golden Spirals.

parthenonMona Lisagalaxy

 

The above statements are unfounded (the Parthenon) , false (painters had no preference for the Golden Rectangle) or only partly true (spiral arms of galaxies are logarithmic, but in general not golden). People who know me, will not be surprised that I am a skeptic..:-). When you are a believer, you will be pleased with the Golden Number website, maintained by “Phi Guy:” who introduces himself with “The inspiration for the site came as a result of coming to faith in God through Jesus Christ.” The guy must have taken the alternative name for φ (Divine Proportion) very literally.

This site is more to my liking: The Myth That Will Not Go Away

Often in a discussion about the Golden Spiral, the Nautilus shell is mentioned. Here it is,  a beautiful example of a logarithmic spiral in nature. But is a Golden Spiral, does it grow with a factor 1.618 each quarter turn? The answer is negative. The golden spiral is the blue line. It is clear that it grows faster than the Nautilus! The average growth factor for a Nautilus is ~ 1.33.

Nautilus with golden spiral

Many references to Fibonacci and the Golden Ratio in  the world around us, are incorrect.

Here is one more, funny example. Recently I found on FB a picture of Fibonacci Pigeons. The location of the pigeons has been indicated with yellow arrows. Nice how the distance between the pigeons increases from left to right. But is it Fibonacci?

pigeons1

The answer is again negative. In the upper part of the picture I have indicated the Fibonacci positions. Compare the regular increase in spacing with the very irregular spacing of the yellow arrows!

Ok, time to become more positive…:-) Several painters (Dali, Seurat) were intrigued by Fibonacci numbers and the Golden Ratio. One 20th century artist, Mario Merz, was fascinated by it and you can find references in many of his works. Here are a few.

TablesMario MerzSpiral

 

 

But the most beautiful examples come from nature, from the Kingdom of Plants.

Here is a sunflower. What we call the flower is actually a combination of hundreds of small flowers (florets) surrounded by petals. As you see the florets are arranged in two series of spirals, starting from the center. One series is curving clockwise (red), the other one anticlockwise (blue). Can you count the number of blue spirals and red spirals?

Sunflower

The answer is : 55 red spirals and 34 blue ones. Two Fibonacci numbers!

Here is a pine cone, that I found in the forest a couple of years ago. Also here the scales form  two series of spirals. I counted how many and found 13 green ones and 8 yellow ones. Again two Fibonacci numbers! Isn’t it amazing? Try it yourself with a pineapple..:-)

pine cone

Is this Intelligent design? The Divine Proportion in action? The explanation is very interesting: by arranging the florets/scales this way, the available space is used the most efficiently. The idea is that new flowers/seeds are not formed in line with the old one, but rotated. If we express this rotation as part of a full turn (360 degrees), then a rotation of 0.5 would mean that each new cell is rotated 180 degrees. A rotation of 0.25 gives a rotation of 90 degrees, etc. Here are a few examples for various rotations. As you see, the result depends strongly on the chosen rotation value. For a value of 1.610, the space is used already quite efficiently.

rotations

So, let us try 1.6180, the golden ratio. We see an almost perfect filling of the space. Notice the two series of spirals and count the number in each series and you will find 13 and 21 !

rotphi

The pictures above have been created with a beautiful app, which can be found on the website Math Is Fun . Have a look, and try out other values of the rotation. You will also find there an explanation why φ is so special.

Much more can be said about the Fibonacci numbers and the Golden Ratio. A Google search gives numerous hits. Also a book has been published: The Golden Ratio: The Story of PHI, the World’s Most Astonishing Number

Fibonacci (part 1)

Let me start with a rabbit tale..:-)

Rabbits

Once upon a time a pair of rabbits was born. One month later they were mature and mated. After a pregnancy of 1 month, a new pair of rabbits was born (and being rabbits, the parents mated again immediately). In this tale rabbits have eternal life and keep mating. The question is, how does the number of rabbit pairs grow with time?

Let us do some simple arithmetic (if you are afraid of numbers, skip this paragraph)

  1. At the start there is 1 pair, just born. We call it pair A
  2. After 1 month this pair A is mature and mates, so still 1 pair
  3. After two months, pair A delivers a new pair B, so we have now 2 pairs
  4. After three months pair A delivers again a new pair C, pair B has matured and mated, so 3 pairs
  5. After four months pair A delivers pair D, pair C has matured and mates, but now also pair B produces pair E, so totally 5 pairs
  6. After five months pair A delivers pair F, pair C delivers pair G, pair B delivers pair H, totally 8 pairs of rabbits.

Complicated..:-)?  Maybe the graph below will help. Red vertical lines show mating (M), yellow diagonal ones indicate gestation and delivery  (N), black vertical ones are stable (each month producing a new pair)

rabbits

So the sequence gives (in rabbit pairs) 1,1,2,3,5,8… can you guess how it continues?

Here is the answer, each number is the sum of the two preceding ones! 2+3=5, 3+5=8, so the next term should be 5+8=13, then 8+13=21, 13+21=34. A very simple rule..:-)

Still you may wonder, who came with such a funny story. Well, that was Fibonacci, an Italian mathematician, living from c. 1170 – c. 1250.

Fibonacci

The numbers are now called Fibonacci numbers:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765 ...

This Fibonacci series has several remarkable properties. To explain one of them, I first have to introduce the Golden Ratio, also known as the Divine Proportion!

Hm, a little bit more mathematics (skip it if you are afraid of formulas). We have to go back to the old Greek philosophers. They were fascinated with numbers and ratios between numbers. You you may remember the Pythagorean triangles from your school days! Here is one of the problems they were interested in. Suppose you have a stick you like to divide in two parts a and b in such a way that the the ratio (a + b) / a is the same as the ratio a/b

220px-Golden_ratio_line

Hm, let’s try. We have a stick of 100 cm long and we divide it in a =50 cm and b = 50 cm. Then (50+50)/50 = 2 and 50/50 = 1. Not at all the same. Next we try a = 60 and b = 40. This results in (60+40)/60 = 1.6666.. and 60/40 = 1.500. Not yet equal. Next a =62 and b =38. Result: (62+38)/62 = 1.6129.. and 62/38 = 1.6315.. Getting closer! Refining this, we finally find a division of a = 61.8034.. and=38.1966.. with a common ratio of 1.6180..  The Greek mathematicians named this ratio the Golden Ratio with  φ (phi) as its symbol.

Back to our Fibonacci numbers. Let us take the ratio of two consecutive numbers. We start with 1/1 = 1, then 2/1 = 2, 3/2 = 1.5, 5/3 = 1.666, 8/5 = 1.6, 13/8 = 1.625, 21/13 = 1.615, 34/21 = 1.6190, 55/34 = 1.6176, 89/55 = 1.6182, 144/89 = 1.6180 etc

Surprise! The Fibonacci numbers and the Golden Ratio are related!

The ratio of two consecutive Fibonacci numbers approaches the Golden Ratio !

For the second remarkable property we will visualise the Fibonacci numbers in two dimensions, as squares. We add each square so that the result will be a rectangle. The last rectangle in the picture below measures 13 by 8, ratio 13/8 = 1.625, already close to the Golden Ratio..:-)

Fibonacci.squares

Next step, in each square we draw a quarter-circle. This is the result, we get a beautiful spiral, the Golden Spiral!

golden spiral

Not surprisingly, artists throughout the ages have been fascinated by Fibonacci numbers and the Golden Ratio. And in nature we come across many examples of Golden Spirals.

But that will be the topic of a separate post.

Note for readers with a mathematical background. The spiral above is an approximation of the Golden Spiral. And the Golden Ratio can be easily calculated.

golden ratio

Finally: the Golden Spiral is a special case of a logarithmic spiral, with a growth factor of φ for every 90 degrees of rotation.