Nonplussed! Mathematical Proof of Implausible Ideas by Julian Havil

This book covers a number of interesting mathematical puzzles, giving comprehensive solutions and great discussions. The puzzles include Conway’s Chequerboard Army, the UpHill Roller and several pursuit puzzles. A very interesting read with great explanations.

My favourite though had to be the coverage of Conway’s Fractran. Fractran is a programming language that runs on a very simple virtual machine. This machine takes an input number and a finite sequence of fractions. The machine takes the first number from the sequence and multiplies it against the input number. If the value isn’t an integer then the next fraction is taken from the sequence and is multiplied against the input number, and this continues until the result is an integer. If no integer result can be found, the machine terminates with the final result being the input number. If an integer result is found, then the process is repeated, using the result as the input and restarting at the first element of the integer sequence.

The chapter starts out by giving a sequence of integers and then describes how this implements an algorithm to generate the nth prime number.

To see how this works, let’s take a small register machine for adding two numbers and show how to translate it into the FRACTRAN language.

Let’s take the initial inputs in the registers r2 and r3. Using the states s5,s7,s11,… we can encode a machine which produces the sum of the numbers in r2 by starting in state s5 and doing.

s5: if r3 > 0 then r3 = r3 – 1; goto s7

s7: r2 = r2 + 1; goto s5

The trick is to label the registers by using prime numbers and record the state of the machine as the product of state * 2 ^ r2 * 3 ^ r3.

The integer representing the state 5 is 7 / (5 * 3) – we divide by 5 to check we are in state 5, and multiply by 7 to transition to state 7. We divide by 3 to subtract one from the r3 register.

The integer representing the state 7 is 5 * 2 / 7 – we divide by 7 to check we are in state 7, multiply by 5 to move to state 5, and multiply by 2 to add to r2.

If neither of these rules matches, then we must have finished in state 5. We therefore need the final rule 1/5 to get rid of the state marker leaving just the register contents.

Hence our program is { 7/15, 10/7, 1/5 }

Let’s run this on initial state r2=3 r3=4, which gives a start value of 5 * 2 ^ 3 * 3 ^ 4 = 3240.

We multiply 3240 by the various integers giving (1512 32400/7 648) and take the first one which is integer, 1512.

We get the following transitions: 2160, 1008, 1440, 672, 960, 448, 640, 128.

The final result is 128 = 2 ^ 7, so the machine has added 3 and 4 to get the result 7.