# The number sequence algorithm that solves them all!

Inspired by a student who was asked the typical question of

What is the missing number in the sequence

8, 15, 25, 38, ??, 73

I thought: Well, this type of question is silly; if the student knows about OEIS and it exists there, then there is no challenge and if it does not appear there, then there is a chance that the question is too hard or too broad for such low-level student!

What a silly teacher I thought, as I found the 54 that their teacher was probably looking for, using the generator $3/2\,{n}^{2}+5/2\,n+4$.

Now, as we all know, such sequence is bound to not be unique. An example, I like to use is to consider the function

$$\frac{(1-n)(2-n)(3-n)(4-n)(5-n)(6-n)(7-n)(8-n)(9-n)( y-n)}{(n-1)!} +n$$ This silly function returns

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} n&1&2&3&4 & 5& 6& 7& 8& 9& 10& 11& 12 \\\hline \text{out} &1& 2& 3& 4& 5& 6& 7& 8& 9& y& y& 6+ y/2 \end{array}

for $n = 1,\ldots, 12$ and any chosen $y$(!)

Now, in a similar fashion, can you create a function or algorithm that, for an input $n$ satisfies the below table for some $y$ so we can help our beloved student show off to their teacher?

\begin{array}{|c|c|c|c|} n& 1& 2 & 3 & 4 & 5 &6 \\\hline \text{out} & 8& 15 & 25& 38& y & 73 \end{array}

• The examples you showed are called rational interpolating polynomials; although there are lots of alternatives. Do you require the answer to be a rational polynomial? or even continuous (can they only have values at integer n?)
– smci
Mar 23, 2017 at 15:38
• @smci I did not know that, actually. That is nice to know! I do not require either, however I feel like a combination of step functions or just a piecewise function is a little non-convincing for the happy high-school student I was trying to refer to. :) Mar 23, 2017 at 21:36
• I did something like this a while ago: desmos.com/calculator/hrlzf1zyxi Mar 24, 2017 at 0:37

Sure. The function

$8\frac{(n-2)(n-3)(n-4)(n-5)(n-6)}{(1-2)(1-3)(1-4)(1-5)(1-6)}$

equals

0 when $n=2,3,4,5,6$ because there's a zero factor in the numerator and 8 when $n=1$ because each factor in the numerator cancels with one in the denominator.

We can

construct another five such terms -- e.g., the one involving $y$ will be $y\frac{(n-1)(n-2)(n-3)(n-4)(n-6)}{(5-1)(5-2)(5-3)(5-4)(5-6)}$ -- and add them up.

• maybe I understood wrong, but for n=2 shouldn't the result be 15 not 0? Or am I missing something? Mar 23, 2017 at 11:13
• Ah!. Never mind. You explained how to construct one single term. Ignore me. Mar 23, 2017 at 11:15
• Well, that was quick and easy! Your solution is also nice because it can be constructed for any sequence. Mar 23, 2017 at 11:47
• Yup. It's called the Lagrange interpolation formula. Note that if you're actually doing interpolation for any practical purpose that formula is probably the wrong way to do the calculations. Mar 23, 2017 at 12:38
• @GarethMcCaughan I beg to differ. In some advanced high school maths streams you'll need to know it, and in Olympiad mathematics it's also a useful algebraic tool. Mar 23, 2017 at 20:21

Using @garethmccaughan's procedure in his answer, here is the full version that creates the bottom table in the question. Self-answer for completeness.

\begin{aligned} \frac{1}{24}\Bigl( & (54-y)n^5 - 16(54-y)n^4 \!+ 95(54-y)n^3 \bigr. \\& -4(3501-65y)n^2 + 12(1463-27y)n -48(160-3y) \Bigr ) \end{aligned}

Raw version:

1/24*((54-a)*n^5-16*(54-a)*n^4+95*(54-a)*n^3
-4*(3501-65*a)*n^2+12*(1463-27*a)*n-48*(160-3*a))