13 ms·

“A Handbook of Integer Sequences” Fifty Years Later

139 points by zeebeecee 4y ago

ufo 4y ago
> It was no mind-reading trick, the Catalan numbers are certainly the most common sequence that people don’t know about Guilty as charged! I learned about this sequence after looking it up in the OEIS, back when I was still a young student.
cscheid 4y ago
This makes me so happy to read. I had the privilege of working on the same lab as Neil (and Dave Applegate, another notable person in OEIS). No exaggeration at all to call them geniuses, you hang out with them for 5 minutes and know they're cut from different cloth. Nicest folk, too.
dahart 4y ago
> My fascination with these sequences began in 1964 when I was a graduate student at Cornell University in Ithaca, NY, studying neural networks. I had encountered a sequence of numbers, 1,8,78,944,13800,..., and I badly needed a formula for the n-th term, in order to determine the rate of growth of the terms (this would indicate how long the activity in this very simple neural network would persist). I will say more about this sequence in Section 2.1. It’s really fascinating to bump into mentions of NNs from the 60s & 70s. They seems to be quite hot at the time. The paper on the Medial Axis Transform mentions neural networks too, in a way that makes it seem like it was the cool thing to do. By the time I was in college, NNs were very out of fashion. Here’s the NN problem Neil was working on, and the first sequence in the database: https://oeis.org/A000435 https://oeis.org/A000435
- zitterbewegung 4y ago
  Yea neural networks were actually invented in the 40s by Warren McCulloch and Walter Pitts at University of Illinois at Chicago. They had a few isolated results until GPUs and distributed computation really kicked them into high gear and that made the change in terms to “deep learning” and now GPT-3 and other networks are hyperparamaterized neural networks with millions to billions of parameters .
  - visarga 4y ago
    True, but scaling has its own problems. It was necessary to find better optimisers, activation functions, regularisers, weight sharing schemes, architectures and many other ingredients to make it work. And to prepare the large datasets, and invent the whole stack of frameworks, from CUDA to HuggingFace. We have had 250,000 ML papers written since 2012. That's a lower bound on the number of distinct experiments necessary to find the winning tickets of today. Inventing the step-activated neuron formula was less than 1% of the way here.
  - ISL 4y ago
    I was part of a research group that extensively trained small neural networks for image-processing in 2001, the high-energy physics community had been using them for many years by that time. Furthermore, I believe that the PalmPilot's handwriting-recognition engine also had a neural-network component. Agreed that the usage has increased radically in the last twenty years, but even before the GPU-based revolution, it felt like neural networks were already broadly known and in use across the sciences and engineering. They were just slower :).
Someone 4y ago
For real numbers, there’s the dictionary of real numbers (https://www.amazon.com/Dictionary-Real-Numbers-Jonathan-Borwein/dp/1461585120 https://www.amazon.com/Dictionary-Real-Numbers-Jonathan-Borw...), “a list of just over 100,000 eight-digit real numbers in the interval [0,1) that arise as the first eight digits of special values of familiar functions” Its online equivalent is the inverse symbolic calculator (https://en.wikipedia.org/wiki/Inverse_Symbolic_Calculator https://en.wikipedia.org/wiki/Inverse_Symbolic_Calculator)
- lifthrasiir 4y ago
  Or use ries: https://mrob.com/pub/ries/index.html https://mrob.com/pub/ries/index.html
peter_d_sherman 4y ago
>"My fascination with these sequences began in 1964 when I was a graduate student at Cornell University in Ithaca, NY, studying neural networks. I had encountered a sequence of numbers, 1, 8, 78, 944, 13800, . . ., and I badly needed a formula for the n-th term, in order to determine the rate of growth of the terms..." Related Mathologer video: Mathologer - "Why don't they teach Newton's calculus of 'What comes next?'" https://www.youtube.com/watch?v=4AuV93LOPcE https://www.youtube.com/watch?v=4AuV93LOPcE
- anderskaseorg 4y ago
  The finite difference method of that video is only useful for finding polynomial sequences. Of course, any finite sequence can be extended to some polynomial, but in many cases (such as this one) that’s not the result you’re looking for.
  - peter_d_sherman 4y ago
    Specifically, in this case, why isn't it?
    - eesmith 4y ago
      Because this sequences isn't polynomial. It's https://oeis.org/A000435 https://oeis.org/A000435 , with the explicit formula a(n) = (n-1)! * Sum_{k=0..n-2} n^k/k! and the approximate form shows it's grows roughly as n^n: a(n) ~ sqrt(Pi/2)*n^(n-1/2) Here's my Python implementation: from math import factorial from fractions import Fraction as F def A000435(n): return int(factorial(n-1) * sum(F(n**k, factorial(k)) for k in range(0, n-1))) The video you linked to is on OEIS at https://oeis.org/A000127 https://oeis.org/A000127 and is a quartic: def A000127(n): return (n**4 - 6*n**3 + 23*n**2 - 18*n + 24)//24
      - peter_d_sherman 4y ago
        OK, I think I understand what you and anderskaseorg mean by polynomial/non-polynomial sequences... If we think about a polynomial, say 3x^2 + 2x + 1 -- then that's basically an algorithm that says "take x, raise it to the second power, muliply it by 3, take the result of that, add it to x multiplied by 2, and then take the result of that, and add one to it". In other words, in that algorithmic definition, a) There is no recursion (note that factorials imply recursion in an algorithm -- even though they could be computed by using a simple look-up table) and, b) There is no division (which could result in non-integer values) So, in the formulas you give, you are using both recursion and division to form your sequences. OK, so number tables / triangles / fans (call them what you will) -- don't work for things like that. I am willing to buy into that, prima facie, but "with the proverbial grain of salt"... You see, there's something deeper about math -- that we're not understanding here... To understand what it is or may be (I don't know what it is, all that follows is mathematically speculative reasoning, and might be wrong, might be quite wrong indeed!), then I would suggest the following: First, consider the Fibonnaci Sequence: https://oeis.org/A000045 https://oeis.org/A000045 Why? Because this is the simplest (AFAIK) recurrence relationship (AKA recursive, "defined using recursion") integer sequence -- that can be produced. To recap, its definition is: F(n) = F(n-1) + F(n-2) (with F(0) = 0 and F(1) = 1) Now let's create that integer sequence -- and a corresponding number table / difference table / triangle / fan (again, call it what you will) -- and let's see if that works... Now, I don't have Python all set up to do this -- all I have is pen and paper. But I tried it -- and lo and behold, it works! What's very interesting about the Fibonnaci Sequence -- is that if you create a number table for it -- you'll see that it repeats (although each row is shifted to the right!) in descending rows! In other words, that number table -- if we can spot that pattern -- is in fact showing us the recurrence/recursive relationship! In other words, it's still working(!) -- for this simple recurrence/recursive formula! But we know that it fails -- somewhere between this simple recurrence algorithm -- and the one you have presented! My challenge to you then, as a fellow Mathematician (I haven't done this by the way, I'm lazy! <g>) -- is to figure out when/where/why the number table / difference table / triangle / fan -- fails -- between the simplest of all recurrence relationship formula, the Fibonnaci sequence -- and this one! Because you see, I'll bet there's some interesting mathematical knowledge there!. I'd do it myself -- but no time! Besides, you have Python already set up and running and everything... I don't! Anyway, I think it would be interesting to know this! Also -- once the exact failure criteria are understood -- next question is, is it possible to construct an n-dimensional table (like maybe 2 or more interlinked/interrelated number/difference tables) -- where one maps to others, and you can get the correct answer for deeply recursive algorithms -- which include division?
DonHopkins 4y ago
My favorite hard core nerd insult used to be "Your idea of a hot date is looking up dirty words in the unabridged dictionary," but now I'm going to use "Your idea of a hot date is looking up 69 in the Handbook of Integer Sequences."
anthk 4y ago
The series of dividing an integer over 7 are nice.
NeilSloane 4y ago
There's a version with fewer errors and typos here: http://neilsloane.com/doc/HIS50.pdf http://neilsloane.com/doc/HIS50.pdf
optimalsolver 4y ago
I'll take this opportunity to point out my favorite integer sequence, Recaman's Sequence: https://www.youtube.com/watch?v=FGC5TdIiT9U https://www.youtube.com/watch?v=FGC5TdIiT9U
dleather 4y ago
Is there something similar for real sequences?
andreareina 4y ago
Neil Sloane (author of the paper and curator of the OEIS) has been featured on Numberphile several times and it’s always a pleasure to watch. https://m.youtube.com/playlist?list=PLt5AfwLFPxWJXQqPe_llzWmTHMPb9QvV2 https://m.youtube.com/playlist?list=PLt5AfwLFPxWJXQqPe_llzWm...
- jl6 4y ago
  Seconded. He has an otherworldly curiosity.
jacquesm 4y ago
The OEIS lives here: https://oeis.org/ https://oeis.org/ Super useful resource.
- typical182 4y ago
  As I understand it, written in Go. There's a mildly humorous "How do you know" exchange where someone on HN quizzes the very person most likely to know: https://news.ycombinator.com/item?id=9920020 https://news.ycombinator.com/item?id=9920020
  - jacquesm 4y ago
    HN has had a couple of those.
    - recov 4y ago
      Mandatory HN lore https://news.ycombinator.com/item?id=35079 https://news.ycombinator.com/item?id=35079
      - jacquesm 4y ago
        That was one of the ones I had in mind. What's really neat is that everybody from that thread is still visiting HN and participating.
- totetsu 4y ago
  Any website that lets me see "The numbers of Mozart's piano concerti" as a graph must be doing something correctly. http://oeis.org/A064172/graph http://oeis.org/A064172/graph
- yreg 4y ago
  I always have a need to use this on puzzle hunts, but I don't think it ever helped.
  - jacquesm 4y ago
Isamu 4y ago
A classic resource. I have my own favorite sequences. Thanks Neil for this unexpected way of connecting to previous research!

139 points by zeebeecee 4y ago

ufo 4y ago

> It was no mind-reading trick, the Catalan numbers are certainly the most common sequence that people don’t know about Guilty as charged! I learned about this sequence after looking it up in the OEIS, back when I was still a young student.

cscheid 4y ago

This makes me so happy to read. I had the privilege of working on the same lab as Neil (and Dave Applegate, another notable person in OEIS). No exaggeration at all to call them geniuses, you hang out with them for 5 minutes and know they're cut from different cloth. Nicest folk, too.

dahart 4y ago

> My fascination with these sequences began in 1964 when I was a graduate student at Cornell University in Ithaca, NY, studying neural networks. I had encountered a sequence of numbers, 1,8,78,944,13800,..., and I badly needed a formula for the n-th term, in order to determine the rate of growth of the terms (this would indicate how long the activity in this very simple neural network would persist). I will say more about this sequence in Section 2.1. It’s really fascinating to bump into mentions of NNs from the 60s & 70s. They seems to be quite hot at the time. The paper on the Medial Axis Transform mentions neural networks too, in a way that makes it seem like it was the cool thing to do. By the time I was in college, NNs were very out of fashion. Here’s the NN problem Neil was working on, and the first sequence in the database: https://oeis.org/A000435 https://oeis.org/A000435

zitterbewegung 4y ago
Yea neural networks were actually invented in the 40s by Warren McCulloch and Walter Pitts at University of Illinois at Chicago. They had a few isolated results until GPUs and distributed computation really kicked them into high gear and that made the change in terms to “deep learning” and now GPT-3 and other networks are hyperparamaterized neural networks with millions to billions of parameters .
- visarga 4y ago
  True, but scaling has its own problems. It was necessary to find better optimisers, activation functions, regularisers, weight sharing schemes, architectures and many other ingredients to make it work. And to prepare the large datasets, and invent the whole stack of frameworks, from CUDA to HuggingFace. We have had 250,000 ML papers written since 2012. That's a lower bound on the number of distinct experiments necessary to find the winning tickets of today. Inventing the step-activated neuron formula was less than 1% of the way here.
- ISL 4y ago
  I was part of a research group that extensively trained small neural networks for image-processing in 2001, the high-energy physics community had been using them for many years by that time. Furthermore, I believe that the PalmPilot's handwriting-recognition engine also had a neural-network component. Agreed that the usage has increased radically in the last twenty years, but even before the GPU-based revolution, it felt like neural networks were already broadly known and in use across the sciences and engineering. They were just slower :).

Someone 4y ago

For real numbers, there’s the dictionary of real numbers (https://www.amazon.com/Dictionary-Real-Numbers-Jonathan-Borwein/dp/1461585120 https://www.amazon.com/Dictionary-Real-Numbers-Jonathan-Borw...), “a list of just over 100,000 eight-digit real numbers in the interval [0,1) that arise as the first eight digits of special values of familiar functions” Its online equivalent is the inverse symbolic calculator (https://en.wikipedia.org/wiki/Inverse_Symbolic_Calculator https://en.wikipedia.org/wiki/Inverse_Symbolic_Calculator)

lifthrasiir 4y ago
Or use ries: https://mrob.com/pub/ries/index.html https://mrob.com/pub/ries/index.html

peter_d_sherman 4y ago

>"My fascination with these sequences began in 1964 when I was a graduate student at Cornell University in Ithaca, NY, studying neural networks. I had encountered a sequence of numbers, 1, 8, 78, 944, 13800, . . ., and I badly needed a formula for the n-th term, in order to determine the rate of growth of the terms..." Related Mathologer video: Mathologer - "Why don't they teach Newton's calculus of 'What comes next?'" https://www.youtube.com/watch?v=4AuV93LOPcE https://www.youtube.com/watch?v=4AuV93LOPcE

anderskaseorg 4y ago
The finite difference method of that video is only useful for finding polynomial sequences. Of course, any finite sequence can be extended to some polynomial, but in many cases (such as this one) that’s not the result you’re looking for.
- peter_d_sherman 4y ago
  Specifically, in this case, why isn't it?
  - eesmith 4y ago
    Because this sequences isn't polynomial. It's https://oeis.org/A000435 https://oeis.org/A000435 , with the explicit formula a(n) = (n-1)! * Sum_{k=0..n-2} n^k/k! and the approximate form shows it's grows roughly as n^n: a(n) ~ sqrt(Pi/2)*n^(n-1/2) Here's my Python implementation: from math import factorial from fractions import Fraction as F def A000435(n): return int(factorial(n-1) * sum(F(n**k, factorial(k)) for k in range(0, n-1))) The video you linked to is on OEIS at https://oeis.org/A000127 https://oeis.org/A000127 and is a quartic: def A000127(n): return (n**4 - 6*n**3 + 23*n**2 - 18*n + 24)//24
    - peter_d_sherman 4y ago
      OK, I think I understand what you and anderskaseorg mean by polynomial/non-polynomial sequences... If we think about a polynomial, say 3x^2 + 2x + 1 -- then that's basically an algorithm that says "take x, raise it to the second power, muliply it by 3, take the result of that, add it to x multiplied by 2, and then take the result of that, and add one to it". In other words, in that algorithmic definition, a) There is no recursion (note that factorials imply recursion in an algorithm -- even though they could be computed by using a simple look-up table) and, b) There is no division (which could result in non-integer values) So, in the formulas you give, you are using both recursion and division to form your sequences. OK, so number tables / triangles / fans (call them what you will) -- don't work for things like that. I am willing to buy into that, prima facie, but "with the proverbial grain of salt"... You see, there's something deeper about math -- that we're not understanding here... To understand what it is or may be (I don't know what it is, all that follows is mathematically speculative reasoning, and might be wrong, might be quite wrong indeed!), then I would suggest the following: First, consider the Fibonnaci Sequence: https://oeis.org/A000045 https://oeis.org/A000045 Why? Because this is the simplest (AFAIK) recurrence relationship (AKA recursive, "defined using recursion") integer sequence -- that can be produced. To recap, its definition is: F(n) = F(n-1) + F(n-2) (with F(0) = 0 and F(1) = 1) Now let's create that integer sequence -- and a corresponding number table / difference table / triangle / fan (again, call it what you will) -- and let's see if that works... Now, I don't have Python all set up to do this -- all I have is pen and paper. But I tried it -- and lo and behold, it works! What's very interesting about the Fibonnaci Sequence -- is that if you create a number table for it -- you'll see that it repeats (although each row is shifted to the right!) in descending rows! In other words, that number table -- if we can spot that pattern -- is in fact showing us the recurrence/recursive relationship! In other words, it's still working(!) -- for this simple recurrence/recursive formula! But we know that it fails -- somewhere between this simple recurrence algorithm -- and the one you have presented! My challenge to you then, as a fellow Mathematician (I haven't done this by the way, I'm lazy! <g>) -- is to figure out when/where/why the number table / difference table / triangle / fan -- fails -- between the simplest of all recurrence relationship formula, the Fibonnaci sequence -- and this one! Because you see, I'll bet there's some interesting mathematical knowledge there!. I'd do it myself -- but no time! Besides, you have Python already set up and running and everything... I don't! Anyway, I think it would be interesting to know this! Also -- once the exact failure criteria are understood -- next question is, is it possible to construct an n-dimensional table (like maybe 2 or more interlinked/interrelated number/difference tables) -- where one maps to others, and you can get the correct answer for deeply recursive algorithms -- which include division?

DonHopkins 4y ago

My favorite hard core nerd insult used to be "Your idea of a hot date is looking up dirty words in the unabridged dictionary," but now I'm going to use "Your idea of a hot date is looking up 69 in the Handbook of Integer Sequences."

anthk 4y ago

The series of dividing an integer over 7 are nice.

NeilSloane 4y ago

There's a version with fewer errors and typos here: http://neilsloane.com/doc/HIS50.pdf http://neilsloane.com/doc/HIS50.pdf

optimalsolver 4y ago

I'll take this opportunity to point out my favorite integer sequence, Recaman's Sequence: https://www.youtube.com/watch?v=FGC5TdIiT9U https://www.youtube.com/watch?v=FGC5TdIiT9U

dleather 4y ago

Is there something similar for real sequences?

andreareina 4y ago

Neil Sloane (author of the paper and curator of the OEIS) has been featured on Numberphile several times and it’s always a pleasure to watch. https://m.youtube.com/playlist?list=PLt5AfwLFPxWJXQqPe_llzWmTHMPb9QvV2 https://m.youtube.com/playlist?list=PLt5AfwLFPxWJXQqPe_llzWm...

jl6 4y ago
Seconded. He has an otherworldly curiosity.

jacquesm 4y ago

The OEIS lives here: https://oeis.org/ https://oeis.org/ Super useful resource.

typical182 4y ago
As I understand it, written in Go. There's a mildly humorous "How do you know" exchange where someone on HN quizzes the very person most likely to know: https://news.ycombinator.com/item?id=9920020 https://news.ycombinator.com/item?id=9920020
- jacquesm 4y ago
  HN has had a couple of those.
  - recov 4y ago
    Mandatory HN lore https://news.ycombinator.com/item?id=35079 https://news.ycombinator.com/item?id=35079
    - jacquesm 4y ago
      That was one of the ones I had in mind. What's really neat is that everybody from that thread is still visiting HN and participating.
totetsu 4y ago
Any website that lets me see "The numbers of Mozart's piano concerti" as a graph must be doing something correctly. http://oeis.org/A064172/graph http://oeis.org/A064172/graph
yreg 4y ago
I always have a need to use this on puzzle hunts, but I don't think it ever helped.
- jacquesm 4y ago

Isamu 4y ago

A classic resource. I have my own favorite sequences. Thanks Neil for this unexpected way of connecting to previous research!