Online Encyclopedia of Integer Sequences | Hacker News Reader

Online Encyclopedia of Integer Sequences

oeis.org

232 pointshyperific50 comments

OEIS solves real-world problems! One time I needed to optimize accesses to a data structure in my code. By trying out a few examples, I found the optimal order of iterations followed a particular number sequence, but I had no idea on how it could be deduced or calculated analytically. I entered the few examples I had into OEIS and found the solution. The solution involves graduate-level combinatorics and there was no way that I could solve it.

Thanks Neil Sloane and OEIS.

This sounds fascinating! What was the structure, and what was the sequence?

I can't give any detail, but the solution to my problem involves k-variate k-nomial multinomial coefficients [1]. It's a generalization of the binomial coefficients to high-order scenarios such as trinomial coefficients, quadrinomial coefficients, etc. In other words, from a Pascal triangle to a Pascal pyramid, to a Pascal hyperpyramid.

[1] https://oeis.org/wiki/Multinomial_coefficients

Multinomial coefficients are also used to define the multinomial distribution in probability which models e.g. the problem of "if I throw a fair die n times, how likely is it that I get exactly x1 ones, x2 twos, ..., x6 sixes?" - which is a generalisation of the binomial distribution in which there are only two cases.

This is not "graduate-level", it's a straightforward generalization of something that all school age kids learn. (Which is not too say that it's trivial to obtain an expression. I'm just saying it's not conceptually advanced)

Per a nitty exploitable quote, do you have the slightest idea how little that narrows it down?

You can generalize addition to semigroups but that's not a point, eh?

That's like arguing all math is addition (it's just a bunch of sum signs), therefore all math is not actually graduate level. It's a straightforward generalization of something that all school kids learn.

Also, math achievement in America is horrible. 40% of students leave 12th grade at "Less than Basic". Only 2-3% leave 12th grade at "Advanced." Must not be very straightforward. (21% "Proficient", 35% "Basic" in 2019)

https://nces.ed.gov/programs/coe/indicator/cnc

Also, "The Distribution User Skills, Worse than You Think" https://news.ycombinator.com/item?id=36620608

It's not even just math. Over half of the US adult population reads below a sixth-grade level. Their science literacy is worse.

No details but it's related to Pascal triangles? So it involves pricing financial instruments, seems like a safe guess...

I had a very similar experience—discovering Stirling numbers of the second kind by solving a computer science problem through brute force, then plugging the results into OEIS, then reverse-engineering an elegant solution to the problem. Fantastic resource.

I suspect this happens more often than anyone realizes.

I really want to read or write the sci-fi story where aliens ping our intelligence with some obscure sequence and they think we're geniuses because thanks to the OEIS we're all like "Oh, yeah, that's just A260151, numerators of coefficients c(n) in asymptotic expansion of Sum_{m=1..k} sqrt(m) ~ zeta(-1/2) + (2/3)*k^(3/2) + (-1/2)*k^(1/2) + Sum_{n=0..inf} c(n)/k^(2*n+1/2)., here's the next 50 terms" https://oeis.org/A260151 in about two minutes.

Fun fact: The sequences of ceiling( 2 / (2^(1/n)-1) ) and floor( 2n / log(2) ) have identical elements for a very long time. The first time they differ is n = 777451915729368.

https://oeis.org/A129935

Numberphile videos featuring Neil Sloane, the founder of the feast.

https://www.youtube.com/watch?v=RGQe8waGJ4w&list=PLt5AfwLFPx...

Related. Others? These are just the obvious matches:

The On-Line Encyclopedia of Integer Sequences - https://news.ycombinator.com/item?id=37041585 - Aug 2023 (3 comments)

What number comes next? The On-line Encyclopedia of Integer Sequences knows - https://news.ycombinator.com/item?id=36038302 - May 2023 (37 comments)

The On-Line Encyclopedia of Integer Sequences - https://news.ycombinator.com/item?id=26848517 - April 2021 (31 comments)

The On-Line Encyclopedia of Integer Sequences - https://news.ycombinator.com/item?id=21366618 - Oct 2019 (28 comments)

The On-Line Encyclopedia of Integer Sequences [pdf] - https://news.ycombinator.com/item?id=18015493 - Sept 2018 (4 comments)

The On-Line Encyclopedia of Integer Sequences - https://news.ycombinator.com/item?id=15900294 - Dec 2017 (1 comment - but it says "I recently had a sequence accepted")

Pictures from the On-Line Encyclopedia of Integer Sequences - https://news.ycombinator.com/item?id=11711212 - May 2016 (5 comments)

The On-Line Encyclopedia of Integer Sequences - https://news.ycombinator.com/item?id=9919535 - July 2015 (19 comments)

The On-Line Encyclopedia of Integer Sequences - https://news.ycombinator.com/item?id=6650490 - Oct 2013 (20 comments)

The On-Line Encyclopedia of Integer Sequences - https://news.ycombinator.com/item?id=2496629 - April 2011 (7 comments)

The On-Line Encyclopedia of Integer Sequences - https://news.ycombinator.com/item?id=888577 - Oct 2009 (2 comments)

Oh man. I love this encylopedia. Once, I found a little website that had a series of increasingly difficult, Project Euler style coding problems. After a while, it turned out to be a google recruiting tool. But while I was playing the games, I had to use the OEIS more than once. It’s such an obscure, nerdy tool. I realky like it.

The website you mention was, I believe, Google Foobar. Here's a nice article about it https://www.turing.com/kb/foobar-google-secret-hiring-techni... It was internally called Rabbit Hole. In true killed-by-Google fashion, they killed this recruiting tool too. It was formerly available at https://foobar.withgoogle.com/

They also used to have on-site versions of such programming contests. I've been to the one at their Los Angeles office twice. Very nice memories.

It still exists. I saw it pop up when I searched about LSTMs a few weeks ago.

It was turned down three days ago.

I did the same thing. I solved all the levels. I got random emails from Google trying to recruit me for a while.

I had no interest in working for them. I just wanted to solve programming puzzles in a time before it got dysfunctionally commodified industry-wide.

Those interested in databases of mathematical objects may want to check out https://mathbases.org

I recently learned this was originally a book! https://www.amazon.com/Encyclopedia-Integer-Sequences-N-Sloa...

also, the author, Neal Sloane is a regular on the youtube channel Numberphile, which always has fun patterns to discuss

OEIS is fun but the bare homepage probably isn't too helpful. I highly recommend Sloane's memoir about the history of OEIS: http://neilsloane.com/doc/HIS50.pdf "_A Handbook of Integer Sequences_ 50 Years Later", Sloane 2023

Data can also be downloaded to use it offline https://github.com/oeis/oeisdata

Is there any list that's growing slower over time than the Dedekind numbers? https://oeis.org/A000372

New entries in the years 1897, 1940, 1946, 1965, 1991, 2023.

(see also "Ninth Dedekind number discovered: long-known problem in mathematics solved" https://news.ycombinator.com/item?id=36491677)

I find Jenny’s constant useful whenever a store wants a phone number for their loyalty program.

Did they ever find the area code for that, or is that still unsolved?

I think Lenny's constant might be better suited https://old.reddit.com/r/itslenny/

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!

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.

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

Russ Cox (who recently did a deep dive into the xz attack shell script[0][1]) of Bell Labs Plan9 and Google golang fame re-wrote the OEIS in golang in the summer of 2009[2][3] and now serves as the foundation's president[4]

> "Here, however, we ran into a very serious problem. In the summer of 2009, when we tried to get the OEIS working as a wiki, we discovered that the Mediawiki software was not capable of handling the kind of queries that arise in looking up sequences. This was a disaster."

> "It took us over a year to resolve this problem. In the end, Russ Cox completely rewrote all the programs needed to maintain the database and answer queries - a huge task! NJAS's colleague David Applegate has also been of enormous help in getting the new system working. As a result of their work, the new OEIS was finally launched on November 11, 2010. It is now possible for anyone in the world to propose a new sequence or an update to an existing sequence. To do this, users must first register. A group of about 130 editors has been formed, whose job it is to review submissions before they become a permanent part of the OEIS."

> "So, after nearly two years of struggle, the OEIS was finally able to operate without NJAS having to approve every change. After 46 years of running the database, this came as a great relief to him."[2]

> "It's true. The original software was an email auto-reply implemented in shell. The first web version of the software was CGI invoking roughly the same shell script. I didn't have anything to do with those. The next web version (which I wrote in ~2006) was CGI invoking C with an mmap'ed index file. The third web version (which I wrote in ~2010 and is the one running today) is a Go HTTP server, fronted by Apache."

> "Note that I'm only talking about the software for the "interactive" UI, not the database itself. The database itself goes back to punched cards and the original interactive UI was a pair of published books (first A Handbook of Integer Sequences, and then the Encyclopedia of Integer Sequences)."[5]

[0]: https://news.ycombinator.com/item?id=39902241

[1]: https://news.ycombinator.com/item?id=39903685

[2]: https://oeis.org/wiki/Welcome#OEIS:_Brief_History

[3]: https://news.ycombinator.com/item?id=9920020

[4]: https://oeisf.org/board/

[5]: https://news.ycombinator.com/item?id=9927038

https://news.ycombinator.com/user?id=rsc

This just came up in a Stand-up Maths video on a curious Minecraft boat drop bug…

https://youtu.be/ei58gGM9Z8k

All sorts of fun ones here. I like this one of a NYC subway line’s stops: https://oeis.org/A000054

I was delighted to find The Numbers from LOST:

https://oeis.org/A104101

> It is easy to fit formulas to the first six terms, in a million different ways, but none of them are of any interest (the seventh term can be chosen to be any number you wish). - N. J. A. Sloane, Oct 22 2017

A microcosm for the "plot" of that show, where the writers just pulled some new twist out of their backsides every episode!

There seems to be a few python libraries out there that will spit out a subset of these sequences. I know that's pretty much the exact opposite of how you're supposed to use this data, but I still think it's neat.

Usefully, there's a "PROG" entry for many sequences on this site showing one or more ways of generating the sequence.

I love this site. I have used it many times to help me solve- or shine a light on some problems I have worked on. I visit "my" sequences from time to time

https://oeis.org/search?q=jostein+trondal&language=english&g...

Out of all the professionals, Neil and company are the only community willing to publish my discoveries despite the fact I'm amateur. Looking up A297189 and learning it wasn't known to approximate 7^(1/2) was a thrill.

Is there a version of this for real value sequences?

Also, an interesting video on Recamán's Sequence:

https://www.youtube.com/watch?v=FGC5TdIiT9U

Using the OEIS, you can usually find a reason why every single answer to those IQ questions about what number comes next in the series is correct.

in theory anyone can map any sequence to an interpolating polynomial, but I think those would get rejected.

Also: meta-sequences: a sequence of integers that has no notable properties about them or that dosn't comprise a sequence

I like the phrasing used by https://houseofgraphs.org/ — while there are an infinite number of mathematical objects in any category, there are only "a few thousand that can be considered really interesting."

The same with chess and go. There are way too many move order combinations, but only a few thousand interesting ones.

Happy to have authored A094777, Number of legal positions in Go played on an n X n grid (each group must have at least one liberty), [1] and A269417, Number of Go games on n X n board with no repeating position and suicide allowed. [2].

[1] https://oeis.org/A094777

[2] https://oeis.org/A269417

Relevant XKCD: https://xkcd.com/2016/

I can't find any sequences that list Randall Munroe as the author, but there are several sequences that referenced xkcd:

https://oeis.org/search?q=xkcd&go=Search

https://oeis.org/search?q=randall+munroe&go=Search

Those were great.

I like how he doesn't hold back on the labels, but still accepts some 'dumb' sequences: https://oeis.org/search?q=dumb like this one: https://oeis.org/A104175

Reply on news.ycombinator.com