# 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 '17 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. :) – Therkel Mar 23 '17 at 21:36
• I did something like this a while ago: desmos.com/calculator/hrlzf1zyxi – greenturtle3141 Mar 24 '17 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? – Marius Mar 23 '17 at 11:13
• Ah!. Never mind. You explained how to construct one single term. Ignore me. – Marius Mar 23 '17 at 11:15
• Well, that was quick and easy! Your solution is also nice because it can be constructed for any sequence. – Therkel Mar 23 '17 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. – Gareth McCaughan Mar 23 '17 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. – boboquack Mar 23 '17 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))