Hacker News Reader

Comment by nickdrozd | Hacker News Reader

The OEIS is a curated selection of integer sequences. It only includes those sequences deemed interesting (usually mathematically, but also recreationally, and occasionally for some other reason). It's easy to generate a new sequence from an old one, say B(n) = A(n) + 11 for some sequence A. But if you submit that it will be rejected because it isn't interesting. (Trying to come up with an OEIS-worthy sequence is difficult and edifying, and a great rainy-day activity.)

But even if the OEIS had no standards and included every imaginable sequence, it still wouldn't include more than a vanishingly small fraction of the total set of all integer sequences. This is because almost all integer sequences are infinitely long and cannot be specified. There just aren't enough words!

View on HN

At one point a project in a research group I'm part of did automatic parsing of the entire OEIS to find relations between different existing sequences. Using a very simple approach, they found ~300 000 000 relations (e.g. meaning one sequence can be expressed as some combination of other sequences); see section 4 of [1].

However they submitted only three (!) of those back to OEIS. Even with 130 reviewers on the OEIS side, submitting all of those relations would have basically been a Denial-of-service attack on the review process.

[1] https://kwarc.info/people/mkohlhase/papers/icms16-oeis.pdf

Is the set of integer sequences uncountably infinite? It seems like Cantor's diagonal argument would work here.

1. Number all sets from 0.

2. Construct a new set by picking the i^th number from each set.

Yes, one useful application of Cantor's theorem is to show that anything claiming to enumerate all integer sequences must fail to do so. That's assuming that the sequences can be infinite; if it were the Online Encyclopedia of Finite Integer Sequences, then it could succeed at enumerating all of them.

(As for the diagonal argument, make sure that the ith value of the counter-sequence DIFFERS from the ith value of the ith sequence. A sequence whose ith value matches the ith value of the ith sequence doesn't produce a contradiction, and could in fact be part of the encyclopedia.)

You don't even have to repeat the diagonal argument. There's a one-to-one correspondence between subsets of the natural numbers and sequences of elements from {0,1}. The i-th element is 1 if i is in the set, otherwise it's zero.

Reply on news.ycombinator.com