# You're reading: Posts Tagged: John Conway

### John Conway and his fruitful fractions

Following on from the series of ‘Pascal’s Triangle and its Secrets‘ posts, guest author David Benjamin shares another delightful piece of mathematics – this time relating to prime numbers.

At the time of writing the largest known prime number has $24862048$ digits. The number of digits does not reflect the true size of this prime but if we were to type it out at Times New Roman font size 12, it would reach approximately $51.5$ km, or about $32$ miles. Astonishing!

Patrick Laroche from Ocala, Florida discovered this Mersenne prime on December 7, 2018. I was surprised to discover that it’s exponent $82589933$ is the length of the hypotenuse of a primitive Pythagorean triple where $82589933^{2} = 30120165^{2} + 76901708^{2}$ as indeed are 8 of the exponents of those currently ranked from 1 to 10.

The Greek mathematician Euclid of Alexandria ($\sim$325 BC-265 BC) was arguably the first to prove that there are an infinite number of primes – and since then, people have been searching for new ones. Some do it for kudos, for the prize money, to test the power of computers and the need to find more of the large primes used to help protect the massive amount of data which is being moved around the internet.

Mersenne primes, named after the French monk Marin Mersenne, are of the form $2^{p} -1$, where the exponent $p$ is also prime. Mersenne primes are easier to test for primality, which is one reason we find so many large ones (all but one of the top ten known primes are Mersenne). When Mersenne primes are converted to binary they become a string of $1$s, which makes them suitable for computer algorithms and an excellent starting point for any search.

Since generally testing numbers for primality is slow, some have tried to find methods to produce primes using a formula. Euler’s quadratic polynomial $n^2+n+41$ produces this set of $40$ primes for $n = 0$ to $39$. When $n=40$, the polynomial produces the square number $1681$. Other prime-generating polynomials are listed in this Wolfram Mathworld entry.

The French mathematician Lejeune Dirichlet proved that the linear polynomial $a+nb$ will produce an infinite set of primes if $a$ and $b$ are coprime for $n=0,1,2,3,4,…$. Then again, it also produces an infinite number of composite numbers! However, this gem: $224584605939537911 + 1813569659748930n$ produces 27 consecutive primes for $n=0$ to $n=26$ – and of course, all the primes are in arithmetic progression.

## 14 fruitful fractions

The primes are unpredictable, and become less common as they get larger. Consequently there is no formula that will generate all the prime numbers. However, there is a finite sequence of fractions, that – given an infinite amount of time – would generate all the primes, and in sequential order.

They are the fruitful fractions, created by the brilliant Liverpool-born mathematician, John Horton Conway (1937–2020) who, until his untimely death from complications related to COVID-19, was the John von Neumann Emeritus Professor in Applied and Computational Mathematics at Princeton University, New Jersey, USA.

The fruitful fractions are

The first time I encountered this set of fractions was in the wonderful book, The Book of Numbers, by Conway and Guy. I was so intrigued as to how Conway came up with his idea, I emailed him to ask. I was delighted to receive an outline of an explanation and even a second set of fractions, neither of which I can now find – it was 1996 and pre-cloud storage! But no worries… Conway explains everything in this lecture, which also demonstrates his passion for mathematics and his ability to express his ideas in a relaxed and humorous way, even when he searches for an error in his proof on 26 minutes. The lecture also includes an introduction to Conway’s computer language, FRACTRAN, which includes the statement:

It should now be obvious to you that you can write a one line fraction program that does almost anything, or one and a half lines if you want to be precise‘.

## Using the fractions to find prime numbers

Here’s how the fractions are used to generate primes.

• Start with the number $2$
• Multiply by each of the fourteen fractions until you find one for which the product is an integer
• Starting with this new integer, continue multiplying through the fractions until another integer is produced. (If this process reaches fraction $N=\frac{55}{1}$, the integer’s product with N is guaranteed to be another integer as N has a denominator of $1$; the process continues with this new integer being multiplied by fraction A)
• Continue multiplying through the set to create more integers
• When the integer is a power of $2$, its exponent will be a prime number.

The 19 steps needed to produce the first prime number are:

$2 \overset{ \times M}{\rightarrow} 15 \overset{ \times N}\rightarrow 825\overset{ \times E} \rightarrow 725 \overset{ \times F}\rightarrow 1925\overset{ \times K} \rightarrow 2275 \overset{ \times A}\rightarrow 425 \overset{ \times B}\rightarrow 390 \overset{ \times J}\rightarrow 330 \overset{ \times E}\rightarrow 290 \overset{ \times F}\rightarrow 770 \overset{ \times K}\rightarrow 910\overset{ \times A} \rightarrow 170\overset{ \times B} \rightarrow 156\overset{ \times J} \rightarrow 132\overset{ \times E} \rightarrow 116 \overset{ \times F}\rightarrow 308\overset{ \times K} \rightarrow 364\overset{ \times A} \rightarrow 68 \overset{ \times I}\rightarrow 4 \equiv2^{2}$

The number of steps needed to produce the first 7 primes are shown in the table below:

And here is the start and end of the sequence of fractions used to produce the next prime number from $2^{2}$:

$4 \overset{ \times M}{\rightarrow} 30 \overset{ \times M}\rightarrow 225\overset{ \times N} \rightarrow 12375 \overset{ \times E}\rightarrow 10875 \rightarrow \cdots \rightarrow 232 \overset{ \times F}{\rightarrow} 616 \overset{ \times K}\rightarrow 728\overset{ \times A} \rightarrow 136 \overset{ \times I}\rightarrow 8\equiv2^{3}$

The steps needed for the first 34 primes are given as OEIS A007547 and the first 8102 products in the B-list for A007542.

The successive primes are produced almost like magic – but the number of multiplications needed to produce each new prime becomes larger and larger, and so the method, though wonderfully inventive, is not at all efficient.

### Conway’s Circle Theorem: a proof, this time with words

Back in the olden days, Colin entered a proof without words in the Big Mathoff. It was mentioned, in passing, in a New York Times obituary of John Horton Conway.

### John Conway has died

Mathematician John Horton Conway, a professor at both the University of Cambridge and Princeton University, and the originator of hundreds of lovely and clever maths things, has died at the age of 82.

### 13532385396179 doesn’t climb to a prime

Someone called James Davis has found a counterexample to John H. Conway’s “Climb to a Prime” conjecture, for which Conway was offering \$1,000 for a solution. The conjecture goes like this, as stated in Conway’s list of \$1,000 problems:

Let $n$ be a positive integer. Write the prime factorization in the usual way, e.g. $60 = 2^2 \cdot 3 \cdot 5$, in which the primes are written in increasing order, and exponents of $1$ are omitted. Then bring exponents down to the line and omit all multiplication signs, obtaining a number $f(n)$. Now repeat.

So, for example, $f(60) = f(2^2 \cdot 3 \cdot 5) = 2235$. Next, because $2235 = 3 \cdot 5 \cdot 149$, it maps, under $f$, to $35149$, and since $35149$ is prime, we stop there forever.

The conjecture, in which I seem to be the only believer, is that every number eventually climbs to a prime. The number 20 has not been verified to do so. Observe that $20 \to 225 \to 3252 \to 223271 \to \ldots$, eventually getting to more than one hundred digits without reaching a prime!

Well, James, who says he is “not a mathematician by any stretch”, had a hunch that a counterexample would be of the form $n = x \cdot p = f(x) \cdot 10^y+p$, where $p$ is the largest prime factor of $n$, which in turn motivates looking for $x$ of the form $x=m \cdot 10^y + 1$, and $m=1407$, $y=5$, $p=96179$ “fell out immediately”. It’s not at all obvious to me where that hunch came from, or why it worked.

The number James found was $13\,532\,385\,396\,179 = 13 \cdot 53^2 \cdot 3853 \cdot 96179$, which maps onto itself under Conway’s function $f$ – it’s a fixed point of the function. So, $f$ will never map this composite number onto a prime, disproving the conjecture. Finding such a simple counterexample against such stratospherically poor odds is like deciding to look for Lord Lucan and bumping into him on your doorstep as you leave the house.

A lovely bit of speculative maths spelunking!

via Hans Havermann, whom James originally contacted with his discovery.

### Right answer for the wrong reason: cellular automaton on the new Cambridge North station

Cambridge North is a brand new train station, and the building’s got a fab bit of cladding with a design ‘derived from John Horton Conway’s “Game of Life” theories which he established while at Gonville and Caius College, Cambridge in 1970.’

One problem: that’s Wolfram’s Rule 135, not the Game of Life. You can tell because of the pixels.

Rule 135 is a 1-dimensional automaton: you start with a row of black or white pixels, and the rule tells you how the colour of each pixel changes based on the colours of the neighbouring pixels. The Cambridge North design shows the evolution of a rule 135 pattern as a distinct row of pixels for each time step. Conway’s Game of Life follows the same idea but in two dimensions – a pixel’s colour changes depending on the nearby pixels  in every compass direction.

Either way, it’s a lovely pattern. I suspect the designers went with Rule 135 instead of the Game of Life so that they’d get a roughly even mix of white and black pixels, which is hard to achieve under Conway’s rules.

Just in case gawping at train stations is your cup of tea, here’s a promotional video with lots of lovely panning shots of the design:

EDIT: James Grime has now also done a video, which can be seen here:

Cambridge North Station information from Atkins Group, the design consultancy responsible for the station building.

The Game of Life: a beginner’s guide by Alex Bellos in the Guardian.

Brought to our attention by @Quendus on Twitter.

### Just how big is a big proof?

With news that a recent proof of the Boolean Pythagorean Triples Theorem is the ‘largest proof ever’, we collect and run-down some of the biggest, baddest, proofiest chunks of monster maths.

### Improbable John Conway/Pizza Hut collaboration for π day

John Conway, here pictured browsing the character table of $Fi_{23}$

Restaurant chain Pizza Hut in the US have announced a promotion for “Pi Day” on March 14, involving an unlikely partnership with renowned group-theorist, Life-wrangler and apparent pizza-lover John Conway. (Apparently, pizza and pie are somehow linked in America. It is probably best not to worry about this.)

Featuring on their blog as the inaugural post under the optimistic tags ‘math‘ and ‘John Conway‘, they explain that three maths puzzles set by Conway will be posted on Pi Day, “varying in level of difficulty from high school to Ph.D. level”. Residents of the 48 contiguous US states can leave their answers in the comments when the puzzles are posted, and the winners receive a 3.14-year supply of pizza (or, as the rules clarify, a somewhat more prosaic \$1600 Pizza Hut gift card).

Obviously we will have to wait for the questions to be unveiled to be able to judge the appropriate level of excitement for this promotion, but with Conway involved, no maths-is-really-hard nonsense in the blog post, and not a formula for the perfect anything in sight, things are looking promising for a nice bit of harmless maths/poor childhood diet fun.