# The Game of Life

Last month the English mathematician John Conway passed away at the age of 80. His name may not be familiar to many of you, but he was the inventor of the Game of Life, in 1970. For several years I have been interested in this game. A suitable time to write a blog about it.

When Conway was still an undergraduate at Cambridge University in the sixties, he became interested in “recreational” mathematics and got in contact with Martin Gardner, who had a popular column “Mathematical Games” in the Scientific American. In October 1970 Gardner published in this column The fantastic combinations of John Conway’s new solitaire game “life” Read here and here interviews with Conway about how he invented the game and that for a long time he actually hated it.

The game is played on a grid of adjoining cells, which can be either alive (black) or dead (white). Each cell is surrounded by eight neighbouring cells and what happens to a cell depends on how many neighbours are alive. These are the rules:

1. When a living cell has 0 or 1 living neighbours, it will die.
2. A living cell with 2 or 3 living neighbours will stay alive.
3. A living cell with 4 or more living neighbours will die.
4. A dead cell with exactly 3 living neighbours will become alive.

With zero or one neighbours you will die from loneliness, with four or more neighbours you die from overcrowding. With two or three neighbours you survive and when there are three parents around, a new baby is born. It looks a bit like life 😉

Of course other rules are also possible and it took Conway considerable time to find rules that gave interesting results. As there were hardly any computers in those days, they used a go board to follow the development of (simple) patterns!

Here are a few simple examples to show how the rules work. I have indicated the number of living neighbours in each cell. Living cells that will survive have a yellow number, those that will die have a red one. An empty cells with three neighbours gets a blue number. After the start pattern I have only marked the cells with get a colored number.

Two patterns have died, two became stable (one of them oscillating).

Here is a pattern of 5 cells. Again I count the number of neighbours, using the same colours, blue, yellow and red for birth, life and death. After 4 generations the original pattern appears again, but diagonally shifted one cell! This pattern has got a name, it is called a glider, it will continue moving diagonally

This pattern of 5 cells is very similar, with only the leftmost cell shifted to the right, but the behaviour is very different! It “explodes” rather chaotically, grows to a maximum of more than 200 cells and finally becomes stable after 1103 generations with 116 living cells, including 6 gliders (notice that three of them are escaping at t = 150). This configuration is called the R-pentonimo .

Of course you can not follow the development of such a pattern with pen and paper or a go-board. You need a computer. In those days they were huge and expensive machines. Here is a PDP-7 computer similar to the one used by Conway. The right picture shows the display screen running a life pattern. Click here for a video. The computers were still so slow that Conway was only able to follow the development of the R-pentomino until t = 460, when the article was published.

Here are a few more interesting patterns. This one is called a Heavyweight spaceship. It moves, like the glider, but orthogonally, two cells in 4 steps.

And here are three oscillators. From left to right Figure Eight (period 8), Pulsar (period 3) and Fumarole (period 5)

The publication in the Scientific American aroused a frenzy of interest among professional mathematicians and amateurs alike. Conway thought himself that no pattern could grow indefinitely and offered a prize of 50 dollar to the first person who could prove or disprove this conjecture before the end of 1970.

It took only a couple of weeks before an MIT group constructed a pattern that generates a glider every 30 moves. therewith proving that patterns can grow indefinitely. It is called the Gosper Glider Gun. and one of the many guns that have been found since then. Keep in mind that all this is the result of 4 simple rules 😉 .

Fifty years have passed since Conway’s invention of the Game of Life, and there is still considerable interest, leading to new interesting patterns every year. There exists a comprehensive Life Wiki, similar to Wikipedia, containing at the moment more than 2100 articles. Here is the main page of the wiki.

Notice at the right a list of pattern categories. The Wiki contains at the moment more than 1350 pattern pages. Each page gives a description of the pattern and an option to watch the development of the pattern, by launching the so-called Lifeviewer at the right side of each page. I have linked the patterns described above to the corresponding Wiki page.

There is a yearly competition for the Pattern of the Year . Here are a few winners :

• David Hilbert (2019) , 122 cells an oscillator with period 23
• Sir Robin (2018) , 282 cells, a spaceship moving in an oblique direction
• Lobster (2011), 83 cells, another spaceship, diagonally moving

Not always use the creators fancy names. Here is the p416 60P5H2V0 gun (left image) It has 26342 cells and fires gliders from four directions which collide in such a way that every 416 generations a 60P5H2V0 spaceship (right image) is produced. The center image shows a just completed spaceship, while gliders are already approaching to form a new one. Fascinating. When you click on the image, you can watch a YouTube video of the process.

You can play with the Lifeviewer , by clicking the image below. You start with a blank grid, where you can draw any pattern you like. The Lifeviewer is versatile and powerful, it may take some time to get to know all the options, just give it a try!

Let me finish this post with a few general remarks.

• The Game of Life is deterministic but unpredictable. Simple rules lead to complex behavior. All my life that has been a topic of great interest to me.
• When I got my first desktop computer, in the eighties, I wrote my own Game of Life program, in Pascal and partly in Assembler. I took part in a competition. No prize but a honourable mention that my program was very fast. Nowadays a lot of software exists, powerful and of course much faster. Golly is the most popular one, you can download it here.
• The Game of Life is much more than a collection of beautiful patterns. It has been shown by Conway himself that the Game of Life is a Universal Turing Machine, it can perform any calculation that a computer can do. The Pi-calculator calculates the decimal digits of π , the Primer uses the Sieve of Eratosthenes to determine the prime numbers. AND and OR gates can be constructed, etc.
• The Game of life is an example of what is called a Cellular Automaton.
• Martin Gardner has written three columns about the Game of Life. Here is the pdf-file with all three articles.

# 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. How many prime numbers are there? 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 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 🙂 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. 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. 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 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..:-) 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.

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. 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? 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.

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? 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..:-) 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. 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 ! 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) 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) 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. 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 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..:-) Next step, in each square we draw a quarter-circle. This is the result, we get a beautiful spiral, the 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. Finally: the Golden Spiral is a special case of a logarithmic spiral, with a growth factor of φ for every 90 degrees of rotation.