Calculator Games: Ulam Sequences: Up, Up and Away!

 Up, Up and Away With Ulam Seqeunces

This article in the ongoing series of ‘mathematical puzzles you could investigate with a calculator’ (that’s why I just call it ‘Calculator Fun and Games’) is the Ulam Sequence.   It’s an interesting mathematical sequence named after the Polish-American mathematician Stanisław Ulam. It’s a sequence rather than a series, and it generates some strange and interesting results, which seem almost random.

How to Generate an Ulam Sequence

Take with two numbers (specifically, positive integers).  A good place to start is with a =1 and b=2.  To find the next number in the sequence, find the smallest integer that can be written as the sum of two distinct earlier numbers in just one way.  Continue with the next number, and the next.

For example, let’s start the Ulam Sequence with the numbers 1 and 2.  These are the first two terms in the sequence.

The next term is 3 (since 1+2=3).
After that comes 4 (since 1+3=4).

The next terms is not 5.  We can write 5 as 1+4 and as 2+3 using the terms that we’ve generated already.

The next term is 6 (since 2+4=6), and we can only write this in one way using our terms.

We can write 7 as 4+3 and as 6+1, so we skip 7.

The next term is 8 (since 2+6=8).

So, the beginning of the sequence is: 1,2,3,4,6,8,… (and it continues
1,2,3,4,6,8,11,13,16,18,26,28,36,38,47,48,53,57,62,69,72,77,82,87,97,99,102)

Note that 5, 7, 9, 10, 12, 14, 15, 17, 19, 20, 21 and 22 can be obtained in multiple ways using the terms before them.

However:  23 is not in the sequence because it cannot be obtained using the previous terms at all!    24 can be written as both 16+8 and 18+6, while 25 is not obtainable.

The sequence grows in an irregular, almost random pattern.  Let’s see what happens when we start with 1 and 3 instead of 1 and 2.

4 = 1 + 3 only
5 = 1 + 4 only
6 = 5 + 1 only
7 can be written as 4+3 and 6+1
8 = 5+3
9 is 4+5 and 6+3
10 = 6+4
11 is 6+5 and 8+3

The first 20 terms for the 1,3 Ulam Sequence are:

1,3,4,5,6,8,10, 12,17, 21, 23, 28, 32,34,39,43,48,52,59 and 63.

The Ulam Sequence is an interesting example of how simple rules can lead to complex and intriguing mathematical structures, which makes it ideal for calculator (or spreadsheet) exercises.  For example, here’s a comparison of the Ulam sequences for 1,2 compared with 1,3 (as I’ve calculated above) and then 1,4 and 1,5.  Interestingly, the 1,5 sequence does not race ahead of the 1,2 sequence as I had originally expected.

Term	Ulam (1,2)	Ulam (1,3)	Ulam (1,4)	Ulam (1,5)
1	1	1	1	1
2	2	3	4	5
3	3	4	5	6
4	4	5	6	7
5	6	6	7	8
6	8	8	8	9
7	11	10	10	10
8	13	12	16	12
9	16	17	18	20
10	18	21	19	22
11	26	23	21	23
12	28	28	31	24
13	36	32	32	26
14	38	34	33	38
15	47	39	42	38
16	48	43	46	40
17	53	48	56	41
18	57	52	57	52
19	62	59	66	57
20	69	63	70	69

There’s a balance between the ability to leap to larger numbers (1,5) initially – from 1 to 5 – and the need to fill in more numbers between 5 and 10 (because there are very smaller numbers that can be made in multiple ways).

A quick comparison of the Ulam Sequences for (2,b) is even more interesting.  We have to start with 2,3 since 2,1 is the same as 1,2 above, and 2,2 will only produce the even numbers (which is cute but dull).  In fact, any even number paired with 2 will produce uninteresting results!

Let’s compare 2,3 and 2,5:  These grow at a slower rate compared to the 1,b sequences.  Interestingly, they contain far fewer even numbers than the 1,b sequences; in fact 2,5 only contains the even numbers 2 and 12 in the first 20 terms (with no indication that there are any more even numbers further along the sequence).

Term	2,3	2,5
1	2	2
2	3	5
3	5	7
4	7	9
5	8	11
6	9	12
7	13	13
8	14	15
9	18	19
10	19	23
11	24	27
12	25	29
13	29	35
14	30	37
15	35	41
16	36	43
17	40	45
18	41	49
19	46	51
20	51	55

So there’s plenty of scope for investigation with a spreadsheet for the larger numbers.  For example, I haven’t found anybody else list the Ulam sequence for 10,11… so here it is:  the Ulam Sequence for (10,11)

10, 11, 21, 31, 32, 41, 43, 51, 54, 61, 62, 65…

After huge initial leaps of +10 or +11 between consecutive terms, the growth rate of the sequence starts to slow down.  There is only one term in the 20s, then two in the 30s, 40s and 50s, then three in the 60s.

Further reading:
Wolfram has lists and links for many of the 1,b and 2,b Ulam sequences