## “A Handbook of Integer Sequences” Fifty Years Later

New paper by N. J. A. Sloane.

Abstract: Until 1973 there was no database of integer sequences. Someone coming across the sequence 1, 2, 4, 9, 21, 51, 127, . . . would have had no way of discovering that it had been studied since 1870 (today these are called the Motzkin numbers, and form entry A001006 in the database). Everything changed in 1973 with the publication of A Handbook of Integer Sequences, which listed 2372 entries. This report describes the fifty-year evolution of the database from the Handbook to its present form as The On-Line Encyclopedia of Integer Sequences (or OEIS), which contains 360,000 entries, receives a million visits a day, and has been cited 10,000 times, often with a comment saying “discovered thanks to the OEIS”.

I’m proud to have a couple of sequences in OEIS:

• A140961 (2008, with thanks to Vladeta Jovovic, whom I found via A051588, for the interpretation in terms of binary matrices). This arose when I was counting finite models of categorical syllogisms, thinking this might be useful for the psychology of reasoning. It wasn’t.
• A358693 (1 Jan 2023) – whilst looking for properties of the number 2023. Trivial extension of A001102.

## 2023

Random fact about 2023: if you divide 2023 by the sum of its digits (in base 10), you get a square number:

$$\displaystyle \frac{2023}{2+0+2+3} = \frac{2023}{7} = 289 = 17^2$$.

This is sequence A001102 in the On-Line Encyclopedia of Integer Sequences (OEIS). The last year that satisfied this property was 1815; however, OEIS doesn’t say when it next applies. Let’s find out.

First we need to spell out the property so that it’s easier to automate a search.

Let $$d_x(i)$$ denote the $$i$$th digit of $$x$$ in base 10,

$$\displaystyle d_x(i) = \frac{n \bmod 10^{i+1}-n \bmod 10^i}{10^i}$$,

where $$i$$ ranges from $$0$$ to $$\lfloor \log_{10}{x} \rfloor$$, i.e., to one less than the number of digits of $$x$$.

Let $$\displaystyle j(k) = \frac{k}{\sum_{i = 0}^{ \lfloor \log_{10}{k} \rfloor} d_k(i)}$$.

The property holds of $$k \in \mathbb{N}$$ iff there is an $$m \in \mathbb{N}$$ such that $$j(k) = m^2$$, or, equivalently, if $$\lfloor \sqrt{j(k)} \rfloor^2=j(k)$$.

This is enough to code up the search in R. Here are the next few years when the property applies: 2023, 2025, 2028, 2178, 2304, 2312, 2352, 2400.

Please note, I’m not a numerologist, so I don’t know if this is a good thing; however, Happy New Year nonetheless 😉

## Listing numbers

By the end of this post you will understand how to list all (yes, all!) integers and rational numbers and why you can’t list the reals. You will also learn why this weird sequence of numbers is useful:

$$1, 2, 1, 1, 2, 3, 4, 3, 2, 1, 1, 2, 3, 4, 5, 6, 5, \ldots$$

### The integers

There’s an easy way to list all the natural numbers without leaving any gaps. Start with 0, then add 1 to the previous number:

$$0, 1, 2, 3, 4, 5, \ldots$$

You will never reach the end, but wherever you stop, you can be confident that you have all the naturals up to that point.

For integers, list the naturals, then for each natural, $$n$$, add $$-n$$ as follows:

$$0, 1, -1, 2, -2, 3, -3, 4, -4, 5, -5, \ldots$$

This, by the way, is sequence A001057 in the On-line Encyclopedia of Integer Sequences.

### The reals

We can’t list the real numbers, as Cantor showed in 1891.

To see why, let’s explore the reals from 0 to strictly less than 1, or $$[0,1)$$ for short.

Suppose, for the sake of argument, that we could list them all. This means there will be a first number, a second, a third, and so on. So let’s number them and write some arbitrarily chosen examples to get a sense of how the list might look. I’ve put the ith digit in bold for reasons that will soon be apparent.

i Decimal expansion
1 0.00013
2 0.01202
3 0.00310
4 0.12772

Here’s Cantor’s trick. Work down the infinite list of numbers to create a new number in the following way.

• From the the 1st number take the 1st digit after the decimal point and subtract it from 9: $$9 – 0 = 9$$.
• From the the 2nd number take the 2nd digit after the decimal point and subtract it from 9: $$9 – 1 = 8$$.
• From the the 3rd number take the 3rd digit after the decimal point and subtract it from 9: $$9 – 3 = 6$$.
• From the the 4th number take the 4th digit after the decimal point and subtract it from 9: $$9 – 7 = 2$$.
• More generally, from the ith number take the ith digit after the decimal point and subtract it from 9.

Now use these subtractions to generate a new number. So for the example above, we just subtract 9 from the numbers in bold to make:

0.9862…

Our assumption was that we had listed all the real numbers in $$[0,1)$$. But here we have created a new number that differs from each one in that list by at least one digit. Our assumption that we could list all the numbers in $$[0,1)$$ has led to the conclusion that we can’t: a contradiction. If we can’t do it for $$[0,1)$$ then surely we can’t list all the reals.

Although there are infinitely many integers, we can list them. The number of real numbers is too big an infinity to list!

### The rationals: Cantor’s zigzag

We can, however, list the rational numbers in a way that’s guaranteed not to leave any out. Here are two ways to do it. I’ll focus on the non-negative rationals from which it is easy to get the negatives.

The first is due to Cantor, let’s call it the zigzag, and is easiest to show in a picture than to explain. The diagram below puts denominators on the columns and numerators on the rows. Start with $$1/1$$ and follow the arrows:

Beautiful, isn’t it? This zigzag solves the problem that if we go down the first column, say,

$$1/1, 1/2, 1/3, 1/4, \ldots$$,

we head off to infinity without ever moving to the second column, so, for example, we would miss out $$2/5$$ and $$3/4$$.

I think about this in terms of compass directions. Begin by adding $$1/1$$ to your list of rationals and heading east. Let’s call the numerator $$p$$ and denominator $$q$$, so we are enumerating $$p/q$$. Here’s what happens at each step:

• If we are heading east then set $$p \leftarrow p + 1$$ and add $$p/q$$ to our list of rationals. Head southwest on the next step.
• If we are heading southwest, then set
$$p \leftarrow p – 1$$
$$q \leftarrow q + 1$$
Add $$p/q$$ to our list of rationals.
If $$p = 1$$, i.e., we have hit the leftmost column, then head south on the next step.
• If we are heading south then set $$q \leftarrow q + 1$$ and add $$p/q$$ to our list of rationals. Head northeast on the next step.
• If we are heading northeast, then set
$$p \leftarrow p + 1$$
$$q \leftarrow q – 1$$
Add $$p/q$$ to our list of rationals.
If $$q = 1$$, i.e., we have hit the top row, then head east on the next step.

All I have done above is spell out the zigzag pattern. You will see that if we are heading east or south, then we just take one step then change direction. Whereas if we are heading southwest or northeast then we keep going until we hit the edge.

The sequences of numerators and denominators are A092543 and A092542, respectively. It’s interesting looking at the numbers and trying to forget that you know how they were generated. Like, what on earth is going on with

$$1, 2, 1, 1, 2, 3, 4, 3, 2, 1, 1, 2, 3, 4, 5, 6, 5, \ldots$$

It makes sense when you look at the numerators in the zigzag diagram. (I bet this sequence is used in an IQ test or job selection exam somewhere, so basically it just asks if you’re aware how to enumerate the rationals.)

The zigzag is great because it’s easy to see that it works. However, it has two problems: (1) we get the same numbers multiple times, e.g., $$1/2$$ and $$2/4$$ are there and (2) related to this, the fractions aren’t always in their simplest forms, i.e., the numerators and denominators will often have common factors over 1 (again $$2/4$$ is an example – top and bottom can be divided by 2).

### The rationals: Stern-Brocot’s sandwich

Enter the Stern-Brocot tree. Stern, a mathematician, discovered the approach in 1858 and Brocot, a clockmaker, discovered it independently in 1861 in the process of devising systems of gears. Hayes (2000) delves into the history.

I’m doing to ignore the tree aspect of Stern-Brocot’s approach because I don’t think it helps understand how it works. Instead, let’s consider a multilayer Stern-Brocot sandwich (not on Google when I searched, incidentally) as follows.

Begin with the two fractions $$0/1$$ and $$1/0$$. The first is zero, the second is weird – we usually aren’t allowed to divide by zero. But you could think of it as an infinitely large number. (Hayes quotes an anonymous source who says that it is “infinity reduced to lowest terms”.)

Now we fill the sandwich by taking the mediant of these two fractions. This is defined:

$$\displaystyle \mathit{mediant}\left( \frac{p_L}{q_L}, \frac{p_R}{q_R} \right) = \frac{p_L + p_R}{q_L + q_R}$$.

In other words, simply sum the numerators and sum the denominators of the left and right fractions to get, respectively, the numerator and denominator of the mediant.

$$\displaystyle \frac{0}{1} \qquad \frac{1}{0}$$

Fill it with the mediant:

$$\displaystyle \frac{0}{1} \qquad \mathbf{\frac{1}{1}} \qquad \frac{1}{0}$$

Now we have created the number 1. Let’s go again, filling the gaps between numbers we have using the mediant:

$$\displaystyle \frac{0}{1} \qquad \mathbf{\frac{1}{2}} \qquad \frac{1}{1} \qquad \mathbf{\frac{2}{1}} \qquad \frac{1}{0}$$

One more go:

$$\displaystyle \frac{0}{1} \mathbf{\quad \frac{1}{3}} \quad \frac{1}{2} \mathbf{\quad \frac{2}{3}} \quad \frac{1}{1} \mathbf{\quad \frac{3}{2}} \quad \frac{2}{1} \mathbf{\quad \frac{3}{1}} \quad \frac{1}{0}$$

Lovely! You get $$2^s + 1$$ rationals on each step, $$s$$, e.g., the last step above is step three and has $$2^3 + 1 = 9$$ numbers. Follow the steps 10 times and you get 1,205 rationals.

It can be proved this works: all non-negative rationals are enumerated in the correct order and in simplest forms. I shall delegate the proofs to a Google search…

By the way, one reason we can list the rationals at all is because there’s the same number of them as natural numbers.