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
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 :).
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.
Super useful resource.
There's a mildly humorous "How do you know" exchange where someone on HN quizzes the very person most likely to know:
It's nice to see they have a solid plans on how to keep the website running indefinitely.
“In 2009, in order to ensure the long-term future of the database, I set up a non-profit foundation, The OEIS Foundation Inc., a 501(c)(3) Public Charity, whose purpose is to own, maintain and raise funds to support The On-Line Encyclopedia of Integer Se- quences or OEIS.
On October 26, 2009, I transferred the intellectual property of The On-Line Ency- clopedia of Integer Sequences to the Foundation. A new OEIS with multiple editors was launched on November 11, 2010.
Since then it has been 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, and then submissions are reviewed by the editors before they become a permanent part of the OEIS. Technically the OEIS is now a “moderated wiki”.
I started writing this article on November 11, 2022, noting that this marked twelve years of successful operation of the online OEIS, and also that the database is in its 59th year of existence.”
Related Mathologer video:
Mathologer - "Why don't they teach Newton's calculus of 'What comes next?'"
> Robert Jackson suggests that if you've completed a difference table and still don't understand the sequence, you should turn the paper through an angle of 60 degrees, say, and start again and perhaps repeat this several times to make a fan of difference tables.
Its online equivalent is the inverse symbolic calculator (https://en.wikipedia.org/wiki/Inverse_Symbolic_Calculator)
Guilty as charged! I learned about this sequence after looking it up in the OEIS, back when I was still a young student.
a(n) = (n-1)! * Sum_{k=0..n-2} n^k/k!
a(n) ~ sqrt(Pi/2)*n^(n-1/2)
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)))
def A000127(n):
return (n**4 - 6*n**3 + 23*n**2 - 18*n + 24)//24If 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! <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?
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
> 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)
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))
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)| < |F(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.
Which were you thinking of?
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]
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]
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]
Well -- that looks like the problem then!
And the solution -- use a division table -- as you said.
Point is, is that the method shown in the Mathologer video -- does in fact work for every integer sequence defined by polynomials, including some of those that are non-polynomial and involve recursion -- as long as that recursion involves only addition and not multiplication...
In other words, sequence algorithms which are recursive and involve multiplication -- fail.
But then the next question must be -- is there a generalized algorithm for the construction of Mathologer's tables, which creates a subtraction table on the one hand and a divison table on the other?
Which points to the following problem/question:
Given an arbitrary integer sequence -- how can we know that the algorithm that generates it -- uses recursion and multiplication? (without knowing anything else about it -- other than the given sequence of numbers?)
?
>"I don't think you're thinking about these concepts in a useful way."
Define "useful". <g> :-)
I went ahead and watched the video.
Your summary is incomplete. It works for anything which can be represented as a power series. A polynomial has a largest power. A power series can be seen as the extension of polynomials to have an infinite number of exponents, like how
exp(x) = 1 + x + x^2/2! + x^3/3! + ...
This is why it can fit an exponential function.
And why it cannot fit a factorial/gamma function. (As only one of many classes of sequences it cannot fit.)
Multiplication is recursive addition. The phrase "recursive and involve multiplication" is equivalent to "recursive and involve addition".
> Define "useful". <g> :-)
Just because I can recognize that your misunderstanding of what "recursive" means is not a useful way to understand these topics doesn't mean I can describe what is useful.
I can know that the Eiffel Tower is not a fish even if I can't define what a fish is.
We agree on half of this point -- that it cannot fit a factorial function.
I am (not sure/not convinced) currently (without a proof, one way or the other) on the other half of this point -- that (it would not/could not) fit a gamma function -- or some other function or functions which would allow us to differentiate the values at each point where an integer value would have existed .
If we think about the integer values in Mathologer's table -- they are created by simple subtraction, simple difference (of integers).
Now, the concept of "difference" -- not only exists for Integers -- but it also exists for functions...
In other words, f(a) = f(b) + f(c).
If you know that, and you know f(a) and f(b) -- you can solve for f(c).
Conversely, if you know f(a) and f(c) -- you can solve for f(b).
And if you know f(b) and f(c) -- you can solve for f(a).
In other words, it's just another 3-part trinity in Mathematics -- where something added to something else gives you a third thing -- well, if you know that that's what happens, and you have any two of the parts -- then you can solve for the third part.
A simple concept... yet mind-blowing in its ramifications...
Point is -- Mathologer's tables -- could be constructed with functions instead of integers -- and they could work and could work well if those functions are selected correctly to mirror the underlying geometric reality.
We can convert factorial functions into other types of functions (most notably gamma, but probably others as well) -- and if the Math is right -- then it should work...
Now, perhaps you don't get an integer sequence at the top row -- perhaps you get a series of other functions... and then you need to perform some other mathematical operations on them to get the integer sequence...
Also -- the starting point of all of this, should we desire to explore this in some depth -- would be the integer factorial sequence (as the initial integer sequence) -- without any additional polynomials or division.
Does that sequence work in Mathologer's table -- why or why not?
From there we could seek to define sequence values at specific points and in the table as functions -- and see if we could get that going correctly.
Point is -- while you might be very right, and I might be very wrong(!) -- I can't accept what you're telling me without an appropriate mathematical proof.
This is because we know without proof that Mathologer's tables are based on difference -- and that difference exists between functions as another function, and some functions are differentiable and some are not -- but those that are not differentiable can be converted into those that are, i.e. gamma function).
>"(As only one of many classes of sequences it cannot fit.)"
You moved the goalpost!
Originally, anderskaseorg said "The finite difference method of that video is only useful for finding polynomial sequences."
To recap, I tested that with the Fibonnaci Sequence (recursion with addition), and found that that viewpoint -- was not as large as it could be...
In other words, I showed that the set of possibilities was greater than what was expressed by anderskaseorg's viewpoint -- if only by a little bit.
What we're aiming for -- ultimately -- is to be able to rigorously define sequences mathematically -- which would give us clues as to how they are contructed, and answers to such questions as "what comes next".
I suggested that they might be defined in terms of functions instead of integers, and if these functions could not be mathematically manipulated one way in one form -- then it might be possible to do so if they were changed into another form.
You have shown me, over and over again, in your comments, that you wish to deal in limitations...
I have shown you, over and over again, in my comments, that I wish to deal with possibilities...
>Just because I can recognize that your misunderstanding of what "recursive" means is not a useful way to understand these topics doesn't mean I can describe what is useful.
If two wrongs don't make a right -- why do three left turns do?
Upon deeper thought as to why a factorial might fail -- aren't these tables sort of like derivatives?
If so -- then we might want to consider thinking about the derivative of a factorial:
https://math.stackexchange.com/questions/300526/derivative-o...
Hey, the smart people StackExchange tell me that you can't take the derivative of a factorial (well, not in usual Calculus -- at least not without using the Gamma function, as you previously aluded to!)
>"I am not a mathematician. Neither are you."
Well then, one fellow, ahem, "Non-Mathematician" to another(!) -- let me lay out a mathematical speculation/conjecture for you...
I'll bet that somehow Mathologer's tables -- which are based on subtraction -- and fail to work with recursive functions that use multiplication -- could indeed work with even those functions(!) -- if they could somehow be constructed instead -- out of Gamma functions!
Why?
Well simply because you can take the derivative of a Gamma function -- whereas you can't for a factorial!
Now, if such a table as alluded to above could in fact be constructed -- that might be an interesting area of mathematical research!
I don't currently have the time or resources to prove or disprove that it could or couldn't...
But that it could is my bet, my speculation, my conjecture!
One "non-Mathematician" -- to another! <g> :-)
And we'll see if time proves it to be correct or incorrect!
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, 2As logarithmic functions -- difference could be computed between two of them more easily.
Maybe it wouldn't work -- but it would certainly be interesting to try...