.png)
3 hours ago
1
I’ve written before about favourite numbers. Today I want to write about favourite sequences.
Before we get to some, here’s what a sequence is. It is just an ordered list of numbers whose terms can be described. For example, the prime numbers – the numbers that can only be divided by themselves and 1 – form a sequence:
2, 3, 5, 7, 11, 13, 17, 19, 23, …
And there is the Fibonacci sequence, for which each term is the sum of the previous two terms:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …
Ok, so far, so predictable. Prime numbers and Fibonacci numbers are well known throughout general culture.
But have you ever heard of the Kolakoski sequence?
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, …
Mathematicians drool over this sequence, because of the pleasingly self-referential way it is defined.
The sequence only contains 1s and 2s. They appear either in a run of one, or in a run of two.
If we start at the beginning of the sequence, then, as illustrated below, the length of the runs recreates the original sequence.
In other words, the Kolakoski sequence describes the length of runs in the sequence itself. It is the only sequence that does this except for the same sequence with the initial 1 deleted.
Nice!
The Kolakoski sequence is prestigious for another reason: it is the second entry in the Online Encyclopedia of Integer Sequences (OEIS).
(The first entry is about groups and too complicated for discussion here).
The OEIS is one of the best-known mathematical databases on the web and this week it is the subject of a conference at Rutgers University, timed to coincide with its 50th birthday and the 75th birthday of its founder Neil Sloane.
Sequences superstar
Some people collect stamps, some collect fossils but Neil has always collected sequences. In the 1960s he started to write his favourite ones on file cards.
He was only interested in integer sequences, which are those made up of whole numbers and negative numbers and zero.
By 1973 he had 2,400 sequences, which were published as a book: A Handbook of Integer Sequences. In 1996 Sloane put his collection, by then 10,000-strong, on the web, renaming it the OEIS.
Today the OEIS approaches an incredible 250,000 sequences!
Every day mathematicians around the world send Neil new sequences, which are then approved or rejected for inclusion by him and his team of 20 editors-in-chief and 100 associate editors.
The OEIS still grows by about 40 sequences a day. It is a marvellous resource, which gets about nine million hits a month, and it has turned Neil – who was born in Wales, brought up in Australia and has spent his adult life in the USA – into the sequences superstar.
Professor Doron Zeilberger of Rutgers University believes that Sloane’s collection of sequences has made him the world’s most influential mathematician. “Neil did not prove Fermat’s Last Theorem, nor did he prove the Poincaré Conjecture, nevertheless, the impact of [the OEIS] on today’s (and tomorrow’s!) mathematical research far surpasses that of any living mathematician.”
I caught up with Neil via Skype and asked him whether he had any new favourite sequences from the last few years. He mentioned a sequence submitted by Jan Ritsema Van Eck in 2010.
0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5, 0, 2, 6, 5, 4, 0, 5, 3, 0, 3, …
The rule here is that you start with 0, and whenever you get to a number you have not seen before, the following term is a 0. But if the number k has appeared previously in the sequence, then you count the number of terms since the last appearance of k, and that number is the following term. In more detail:
- Term 1: The first term is 0 by definition.
- Term 2: Since we haven’t seen 0 before, the second term is 0.
- Term 3: Since we have seen a 0 before, one step back, the third term is 1
- Term 4: Since we haven’t seen a 1 before, the fourth term is 0
- Term 5: Since we have seen a 0 before, two steps back, the fifth term is 2.
- And so on.
“This is one of my top favourites of all time,” said Neil. “ The question is, how fast does it grow? And does every number eventually appear?” These are open questions.
Neil has lost none of his excitement about sequences. Rarely does a day go past when he doesn’t submit a sequence or two. This year he has already submitted more than 700 sequences, bringing his total tally to more than 42,000.
“The kind of things I do tend to produce sequences! And when I come across a sequence I put it in the database.”
If you have never been to the OEIS before I urge you to go and look around. You can search for sequences by inputting numbers. So if you put in 0, 1, 1, 2, 3, 5 you will get the Fibonacci sequence, as well as more than 200 others that also include these numbers. Each sequence is known by its OEIS catalogue number, which begins with an A. The Kolaloski sequence is A000002, and van Eck’s is A171862.
Each sequence has its own page, which lists the early terms, and includes comments and references as well as other information. It also gives you the option to plot a graph of the sequence, or listen to it as a piece of music where each number is a note in a scale of eight octaves.
Mathematicians and scientists use the OEIS all the time. Sometimes people go there because certain sequences crop up in their work, and it is the best place to see if other people have studied them.
It is also a badge of honour to get a sequence accepted – although Neil and the administrators tend to be very generous in their selection criteria. Still, you need to think up something that hasn’t been thought up before!
The OEIS is also a source of interesting problems, quite often that arise from the recreational mathematics community. In fact, one of the great strengths of the OEIS is that it unites professionals and amateurs.
Jan Ritsema van Eck, of the above sequence, is not a mathematician but a geographer who works for the Dutch environmental assessment agency.
One prolific amateur is the Belgian journalist Eric Angelini, who is the author of the following sequence (A244471) submitted in July that Neil particularly likes:
1, 11, 3, 7, 71, 31, 111, 113, 33, 117, 77, 13, 37, 711, …
The rule here is that if a vertical line is drawn in between any two digits, the number made up of the digits to the left is divisible by the single digit to the right. With the added constraint that numbers are not repeated and you always take the lowest number possible.
If we start at the beginning:
- 1 is divisible by 1
- 11 is divisible by 1
- 111 is divisible by 3
- 1113 is divisible by 7
- 11137 is divisible by 7
- And so on.
“The OEIS changed my life. It may sound ridiculous, but it’s true,” said Eric. “Ask my wife. I don’t disturb her anymore around midnight. She has the bed and ear-plugs for herself. I’m in the living room, digging numbers and waiting for time-zoned replies from the SeqFans list.”
Yes, there is a SeqFans list.
Eric is a fan of the French literary movement Oulipo, a group of mathematically inclined, predominantly French-speaking writers who use constrained writing techniques, such as writing a book without using the letter e.
He sees the OEIS as an Oulipian project – and Oulipian ideas inspired him to create his personal favourite, the “commas sequence” (A121805):
1, 12, 35, 94, 135, 186, 248, 331, 344,…
The rule here is that the difference between each term is the number made by joining the digits either side of the comma between those respective terms.
- The difference between 1 and 12 is 11.
- The difference between 12 and 35 is 23.
- The difference between 35 and 94 is 59.
- And so on. (I’ve highlighted the digits to make it clearer what is going on.)
“A comma usually separates two integers A and B, but plays here the role of a special magnet - a magnet that ‘glues’ the last digit of A to the first digit of B. This visually produces a new integer C that is - guess what? - the difference between A and B!” said Eric.
An interesting fact about the commas sequence is that it carries on for an awfully long time. It contains exactly 2,137,453 terms.
Neil adds the following sequence is “very cute”. It is called the “prime sieve of pi” (A245770), and was submitted this August by Gil Broussard, a computer programmer who lives on a farm in Mississippi.
1, 9, 6, 5, 93, 84626, 3, 2, 502884, …
Here’s how we get it. You extract (sieve out) all the appearances of the prime numbers in the decimal expansion of pi. Let’s do it for the first 25 digits of pi:
- 3141592653589793238462643…
- the first prime is 2, so lets extract the first occurrence and replace it with a space:
- 314159 653589793238462643…
- Repeat the process with the second prime, 3:
- 14159 653589793238462643…
- Then 5:
- 141 9 653589793238462643…
- Then 7:
- 141 9 653589 93238462643…
- Then 11, 13, 17, etc., until the first occurrence of every prime is eliminated.
- We are left with
- 1 9 6 5 93 84626 ...
- We consolidate the gaps between the remaining digits into a single comma. And there we have it.
- 1, 9, 6, 5, 93, 84626, ….
Gil has the romantic notion that some kind of message is embedded in numbers like pi, and he says that his sequence is “a simplistic yet elegant transformation” in search of the message.
“A sequence per-se is inherently and literally primordial, and for me, this is a very alluring creative outlet. In other words, to be inventive in this medium, one must have mastery of only two things, numbers and ideas.
“I derive pleasure from daydreaming about numbers and order and occasionally sharing my creations with others. Is that folly? Perhaps it is, but the OEIS sees to it that even the drivel of fools is harnessed industriously.”
Amen!
If you have your own favourite sequences from the OEIS, please list them in the comments section with the reasons why.
Thanks to Emma Ringelding for her illustration. More of her art and cartoons here.
For latest updates on this blog and other mathematical miscellany follow me on twitter and Facebook.
