Saturday 1 April 2017

How to use number theory to help bus travellers

Living in London, I use buses a lot.  Each day I catch a 180 or 199, ignoring the 188, 286 and others whcih don't take me home.  I have a good memory for all the different buses in the parts of central London that I frequent, but wouldn't it be easier if the bus number told me where it was going?  If, rather than 180 arbitrarily designating a route between Lewisham and Belvedere, the number itself indicated where the bus goes?

So today I am going to unveil my scheme for taking advantage of the properties of numbers to do exactly that.  I will start off with my first idea, and then show enhancements.

The Fundamental Theorem of Arithmetic tells us that any number can be expresssed as the product of prime numbers in an essentially unique way.  So my first scheme allocates to every destination a different prime number.  For example, we might assign 2 to Waterloo, 3 to Euston and 5 to London Bridge.  Then the bus route serving these three places would be number 30.  All you need to do, as a passenger, is know the number assigned to your destination.  If you want to go to Waterloo, you know that any even-numbered bus will take you there: if you are heading for London Bridge then any bus whose number ends with 0 or 5 will do,

You might object that it is easy to tell when a number is divisible by 2 or 5, but less easy if your destination's number is, say, 17.  But there are tricks: to test whether a number is divisible by 17, one simply tests the number obtained by subtracting five times the last digit from the rest (so for 374, we subtract 20 from 37, getting 17: that tells us 17 divides 374).

But this method has a glaring weakness.  It doesn't tell us the order of the stops.  I want to be able to distinguish the route Euston - Waterloo - London Bridge from Euston - London Bridge - Waterloo since I want to travel direct from Euston to Waterloo, and going via London Bridge would take much longer.  So my improved proposal uses Godel numbering.  If a bus visits destinations a, b, c, ... in that order, its number is 2^a times 3^b times 5^c times ...  And this can be dynamically adjusted during the journey: when the bus has left Euston, the number changes to reflect that the next stop is Londo Bridge.  Now, I can find out not only whether the bus takes me to Waterloo, but how many stops there are first.  In my example, if I am at Euston, bus number 288 (2^5x3^2) will take me to London Bridge and then Waterloo, while 1944 (2^3*3^5) will go to London Bridge via Waterloo.

But my final scheme is even better.  In this one, The bus number is the product of the primes representing the places it visits, each raised to the power of the number of minutes it is expected to take to get there.  If a bus doesn't call at destination p, then the number is not a product of p.  So if I want to get to Waterloo, and bus number n arrives, I check to see what is the largest power of 2 which divides n: that is how many minutes it will take to get there.  Of course, this is adjusted dynamically, in the same way as London's bus stops now tell us how long it will be before the next bus arrives.

You might object that this system assumes bus passengers can carry out mental arithmetic.  But of course, there will be apps to do this for those who are not confident.  I will just point my smartphone at the front of a bus, and the app will read the number (say 7200) and tell me that it will be at Waterloo (destination 2) in 5 minutes (since the highest power of 2 dividing 7200 is 2^5 = 32).

Yet another way in which mathematics can make our lives easier!