Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

“A Handbook of Integer Sequences” Fifty Years Later

arxiv.org

Post reply on HN
Print view View original

31–40 of 46 posts

Re: “A Handbook of Integer Sequences” Fifty Years Later

#31

Post by zitterbewegung »

dahart wrote: post #12

> 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…

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 .

Re: “A Handbook of Integer Sequences” Fifty Years Later

#32

Post by visarga »

zitterbewegung wrote: post #31
dahart wrote: post #12

> 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…

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 .

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.

Re: “A Handbook of Integer Sequences” Fifty Years Later

#34

Post by ISL »

zitterbewegung wrote: post #31
dahart wrote: post #12

> 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…

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 .

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 :).

Re: “A Handbook of Integer Sequences” Fifty Years Later

#36

Post by eesmith »

jacquesm wrote: post #27
eesmith wrote: post #25

Earlier quoted context omitted.

11 distinct answers on OEIS, assuming the 2 is either the first value, or you omitted an initial 0. Which were you thinking of?

The 2 is the first value. And no spoilers.

https://oeis.org/A001105 starts with 0 so I guess you don't mean that obvious quadratic.

Could be https://oeis.org/A209303 :

  def f(n):
    return n*n + sum(k*k for k in map(int, str(n)))

  >>> [f(i) for i in range(1, 5)]
  [2, 8, 18, 32]
but I don't know why that entry doesn't start with 0.

Could be https://oeis.org/A190787 :

  >>> import heapq, itertools
  >>> seq = heapq.merge((2**i for i in itertools.count(1, 2)),
              (9*2**i for i in itertools.count(1, 2)))
  >>> list(itertools.islice(seq, 0, 4))
  [2, 8, 18, 32]
Or https://oeis.org/A067051:

  import itertools

  def sigma(n):
    return sum(i for i in range(1, n//2+1) if n % i == 0)

  def seq():
    for n in itertools.count(1):
      if sigma(2*n) % 2 == 0: continue
      if sigma(3*n) % 3 == 0: yield n
      continue

  >>> list(itertools.islice(seq(), 0, 4))
  [2, 8, 18, 32]
The others are either degenerate for 4 points of the A001105 case, or are not so easy to implement in raw Python.

Re: “A Handbook of Integer Sequences” Fifty Years Later

#37

Post by jacquesm »

eesmith wrote: post #36
jacquesm wrote: post #27

Earlier quoted context omitted.

The 2 is the first value. And no spoilers.

https://oeis.org/A001105 starts with 0 so I guess you don't mean that obvious quadratic. Could be https://oeis.org/A209303 : def f(n): return n*n + sum(k*k for k in map(int, str(n))) >>> [f(i) for i in range(1, 5)] [2, 8, 18, 32] but I don't know why that entry doesn't start with 0. Could be https://oeis.org/A190787 : >>> import heapq, itertools >>> seq = heapq.merge((2**i for i in itertools.count(1, 2)), (9*2**i for…

Think chemistry...

Re: “A Handbook of Integer Sequences” Fifty Years Later

#38

Post by eesmith »

jacquesm wrote: post #37
eesmith wrote: post #36

Earlier quoted context omitted.

https://oeis.org/A001105 starts with 0 so I guess you don't mean that obvious quadratic. Could be https://oeis.org/A209303 : def f(n): return n*n + sum(k*k for k in map(int, str(n))) >>> [f(i) for i in range(1, 5)] [2, 8, 18, 32] but I don't know why that entry doesn't start with 0. Could be https://oeis.org/A190787 : >>> import heapq, itertools >>> seq = heapq.merge((2**i for i in itertools.count(1, 2)), (9*2**i for…

Think chemistry...

I believe you are referring to one of the many listed ways to define https://oeis.org/A001105 , which is even more succinctly expressed as a(n) = 2*n^2. This is the answer I thought you wanted, and which I was avoiding saying.

My underlying point is your sequence was under-specified, and with no clear reason to pick your preferred answer over other answers.

Even knowing it's chemistry, three finite sequences which match your specification are:

  2, 8, 18, 32, 18,  8, 2
  2, 8, 18, 32, 21,  9, 2
  2, 8, 18, 32, 32, 14, 2

Re: “A Handbook of Integer Sequences” Fifty Years Later

#39

Post by peter_d_sherman »

eesmith wrote: post #28
peter_d_sherman wrote: post #24

Earlier quoted context omitted.

Specifically, in this case, why isn't it?

Because this sequences isn't polynomial. It's 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 vi…

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

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! ) -- 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?

Re: “A Handbook of Integer Sequences” Fifty Years Later

#40

Post by eesmith »

peter_d_sherman wrote: post #39
eesmith wrote: post #28

Earlier quoted context omitted.

Because this sequences isn't polynomial. It's 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 vi…

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…

I don't think you're thinking about these concepts in a useful way.

Yes, factorials can be defined through recursion. But so can multiplication of non-negative integers:

  def mult(a, b):
    if a == 0 or b == 0: return 0
    if a == 1: return b
    return mult(a-1, b) + b

  >>> mult(5, 9)
  45
Furthermore, factorials can alternatively be defined through the Gamma function, which supports more than just the integers and isn't defined recursively. https://en.wikipedia.org/wiki/Gamma_function .

> the simplest (AFAIK) recurrence relationship ...that can be produced.

The positive integers is even easier. For n >= 0:

  F(0) = 0
  F(n) = 1 + F(n-1)
> What's very interesting about the Fibonnaci Sequence

Another interesting thing about the Fibonnaci Sequence is that it has a closed-form solution, given in your OEIS link as:

  F(n) = ((1+sqrt(5))^n - (1-sqrt(5))^n)/(2^n*sqrt(5))
or see https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_e... .

It is also non-polynomial. In the limit, it approaches a simple exponential.

Nor is it bounded by a polynomial, meaning that if you pick any positive integer p and any constant C, and define g(n) = C n^p then for a large enough n you will find that |g(n)| Furthermore, A000435 , with its n^n - like form, grow even faster than exponential. It's similar to factorial growth.

> as a fellow Mathematician

I am not a mathematician. Neither are you.

> s 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

Consider f(n) = f(n-1) + 1 where f(0) = 0. This is the sequence 0, 1, 2, 3, .... This addition of 1 can be seen trivially in the difference table.

Consider f(n) = f(n-1) + f(n-1) with f(1) = 1. This is the sequence 1, 2, 4, 8, 16, 32, or 2^n, which is an exponential function.

Consider the Fibonacci function f(n) = f(n-1) + f(n-2) with f(1) = f(2) = 1. This uses an addition of the two previous numbers. It approaches an exponential function as n gets larger.

Consider f(n) = n * f(n-1) with f(1) = 1 This is the factorial. It grows faster than the exponential function.

Because the last one uses a multiplication instead of addition, a difference table (which is based on subtraction) won't show the pattern. The inverse of multiplication is division, so use a division table.

> deeply recursive algorithms

These are not deeply recursive. For an example of those, see the Ackermann function. https://en.wikipedia.org/wiki/Ackermann_function , which is not primitive recursive like functions we've discussed so far.

Post reply on HN