A puzzle for November
Katie Steckles
Earlier this month I was reminded of a lovely maths puzzle – one which I often see shared by recreational mathematicians and maths teachers, to test people’s logical thinking. The puzzle is as follows:
What’s the next number in this sequence?
1 11 21 1211 111221 …
If you’d like some time to go away and think about it, take time now.
Before I go into the answer, I’d like to share the historical origins of this sequence. First introduced and analysed by mathematician John Conway, the sequence connects to important applications in computer encoding, and has teased the brains of countless mathematicians around the world since he first wrote about it in the Archimedeans’ Eureka Magazine back in 1986.
Have you figured it out yet? If not, it may help you to know that this sequence is known as the ‘Look and Say’ sequence – if you read out each number, as a series of digits rather than a word, it might jump out at you.
The Answer
The terms in the sequence each describe the previous term in the sequence – if you say them out loud. The first term, 1, initialises the sequence; then the next term, ‘one one’ (11), describes that, since it consists of one ‘one’. The next term is ‘two ones’ (21), then ‘one two, one one’ (1211), and so on.
The answer to my puzzle was therefore 312211 (‘three ones, two twos, one one’) and the sequence can be continued similarly. You may have been struggling to find a more mathematical sequence, connected to the values of the numbers – and it could be argued this is less of a mathematical puzzle and more of a linguistic one.
If you’d like a more mathematical challenge, you could content yourself with trying to prove the fact that this sequence can never contain a number larger than a 3, and separately that no entry can never contain the sequence ‘333’.
So it’s a fun mathematical curiosity. But is it mathematically important? As with so much of recreational maths, the answer is ‘maybe’! This sequence is related to a commonly used method in data compression and storage, called run-length encoding.
Efficient Use of Space
It’s often desirable to reduce the amount of computer memory needed to store a piece of information, and for certain data files, reducing their size can be achieved by simply describing what you see, just like in the sequence. For example, if my file consisted of 400 instances of the word ‘hello’, it would take significantly less storage to just store the words “400 instances of the word ‘hello’”; or even, “hello×400”. With pre-agreed conventions, data that contains any amount of repetition – sequences of the same digit, or chunks of data that occur more than once – can be compacted down, rather than writing out the whole thing in full.
Some version of this method has been used since as far back as the 1960s in transmission of TV signals and by fax machines, and has plenty of applications. Similar approaches can be applied to, for example, image files – rather than encoding the colour of every pixel of an image separately, it’s less information to just store the colours and location of regions of similar colour, and this is exploited well by the GIF and PNG image encoding formats.
The amount of space you can save depends heavily on the complexity of the image – so, a GIF file of a simple black-and-white checkerboard would take up much less disk space than a full-colour photo with lots of detail, even if they both have the same size in pixels. This also illustrates that you have to be careful what you apply it to – some data sets actually get larger when run-length encoded!
This is also a very desirable way to compress information – since the original message can be restored in full, without any data loss, it’s called ‘lossless compression’. This is one of the main ‘holy grails’ of data compression – to be able to reduce file size without losing any information.
Conway’s Constant
Conway studied the ‘Look and Say’ sequence, considering the rate of growth of the length of a string and determining a constant \(\lambda = 1.303577269034\ldots\), known as Conway’s constant, which describes the average rate at which the length increases. The exact value of this constant is given by a polynomial of degree 71.
He also has a bit of fun in his column (p.5 onwards) applying ideas behind this simple sequence to a metaphorical set of ‘chemical elements’ by analogy with the atoms that make up the universe. He presents a ‘periodic table’ with a string of 1s, 2s and 3s assigned to each element, playing with how the elements combine and eventually reaching a ‘Cosmological Theorem’ about how such sequences are structured, with a plea for someone to help by finding a shorter proof of his result. From a simple idea to a metaphorical theory about the universe!
You might be wondering what it was that inspired me to tell you about this – actually, it was the exciting (for me) realisation that earlier this month we celebrated 1/11/21 – surely the perfect date to study a sequence that starts 1, 11, 21 (and the last time in a while we’ll be able to!) Thanks to maths teacher Chris Smith for sharing this lovely video and bringing this auspicious date to my attention.
The post A puzzle for November originally appeared on the HLFF SciLogs blog.