4 ms·

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

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.

JoshTriplett 3y ago
This sounds fascinating! What was the structure, and what was the sequence?
- segfaultbuserr 3y ago
  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 https://oeis.org/wiki/Multinomial_coefficients
  - Tainnor 3y ago
    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.
  - bdjsiqoocwk 3y ago
    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)
    - deruta 3y ago
      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?
    - araes 3y ago
      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 https://nces.ed.gov/programs/coe/indicator/cnc Also, "The Distribution User Skills, Worse than You Think" https://news.ycombinator.com/item?id=36620608 https://news.ycombinator.com/item?id=36620608
      - autoexec 3y ago
        It's not even just math. Over half of the US adult population reads below a sixth-grade level. Their science literacy is worse.
  - gwern 3y ago
    No details but it's related to Pascal triangles? So it involves pricing financial instruments, seems like a safe guess...
Cieplak 3y ago
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.
jerf 3y ago
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 https://oeis.org/A260151 in about two minutes.

JoshTriplett 3y ago

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

segfaultbuserr 3y ago
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 https://oeis.org/wiki/Multinomial_coefficients
- Tainnor 3y ago
  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.
- bdjsiqoocwk 3y ago
  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)
  - deruta 3y ago
    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?
  - araes 3y ago
    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 https://nces.ed.gov/programs/coe/indicator/cnc Also, "The Distribution User Skills, Worse than You Think" https://news.ycombinator.com/item?id=36620608 https://news.ycombinator.com/item?id=36620608
    - autoexec 3y ago
      It's not even just math. Over half of the US adult population reads below a sixth-grade level. Their science literacy is worse.
- gwern 3y ago
  No details but it's related to Pascal triangles? So it involves pricing financial instruments, seems like a safe guess...

Cieplak 3y ago

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.

jerf 3y ago

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 https://oeis.org/A260151 in about two minutes.