the arc of software bends towards understanding

## Integer sequences every computer scientist should know?

The On-Line Encyclopedia of Integer Sequences is quite a nifty website. Suppose that you’re solving a problem, and you come up with the following sequence of integers: 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2... and you wonder to yourself: “huh, what’s that sequence?” Well, just type it in and the answer comes back: A007814, along with all sorts of tasty tidbits like constructions, closed forms, mathematical properties, and more. Even simple sequences like powers of two have a bazillion alternate interpretations and generators.

This got me wondering: what are integer sequences that every computer scientist should know? That is, the ones they should be able to see the first few terms of and think, “Oh, I know that sequence!” and then rack their brains for a little bit trying to remember the construction, closed form or some crucial property. For example, almost anyone with basic math background will recognize the sequences 1, 2, 3, 4, 5; 0, 1, 4, 9, 16; or 1, 1, 2, 3, 5. The very first sequence I cited in this article holds a special place in my heart because I accidentally derived it while working on my article Adventures in Three Monads for The Monad.Reader. Maybe a little less familiar might be 1, 1, 2, 5, 14, 42 or 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, but they are still quite important for computer scientists.

So, what integer sequences every computer scientist should know? (Alternatively, what’s your favorite integer sequence?)

### 12 Responses to “Integer sequences every computer scientist should know?”

1. Brent Yorgey says:

One of my favorite integer sequences is 1,1,2,1,3,2,3,1,4,3,5…, although I wouldn’t say it’s something every computer scientist ought to know.

2. WhoeverIAm says:

1) 2,3,5,7,11,13,17,19,23,29,… (A000040)
2) Binomial coefficients e.g. a) 1,2,1 b) 1,3,3,1 b) 1,5,10,10,5,1
4) 0, 1, 3, 2, 6, 7, 5, 4, … (A003188)

:P

3. Anonymous says:

That’s simple. 2 4 8 16 32 64… (and of course the resulting maximum boundaries). How many times did I look at an error message or log and think, “hmm, that number 65535 sure looks familiar”, and whoops, solved the problem. Now imagine that would just be a random number for me, I’d be debugging forever. :)

4. Anonymous says:

0, 1, 3, 2, 6, 7, 5, 4…

5. Of course! I don’t know how I forgot that one :-) Relatedly, 1, 3, 7, 15, 31, 63… (since we’re zero-indexed bastards.)

6. Derek Elkins says:

0 1 3 2 6 7 5 4

7. Yum Gray codes.

8. Ashley Yakeley says:

I’ve got my very own entry:

5, 6, 8, 16, 65536, ….

9. Apologies to users who got their comments trapped by the spam filter. I guess Akismet thinks that numbers are spammy. :o)

10. jeff putnam says:

1, 1, 2, 6, 24, 120…

11. Leon P Smith says:

I was slightly embarrassed that I had to look this one up the other day:

2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, …

I dunno how important it really is to computer scientists though.

12. alex says: