What number comes next in the sequence?

2010-12-13T09:44:27Z

It always bothers me when I hear a problem such as the following:

The first few numbers in the sequence are 1, 2, 4, 8. What number comes next?

Presumably, the "correct" answer is 16, but it could also be 15 (Use $f(n) = n^3/6 - n^2/2 + 8n/6$) or any other number.

First let's formally introduce some minimum set of conditions for what it means for the next number to be "correct" in the sense of the "most obvious pattern." Given a finite sequence $a_0, a_1, a_2, \ldots, a_n$ for say $n \geq 4$, we define $a_{n+1}$ to be "correct" with respect to the given sequence if all of the following conditions are met:

(Arithmetic): If there exists $d \in \mathbb{N}$ such that $a_{i+1} = a_i + d$ for all $i < n$, then $a_{n+1} = a_n + d$.

(Geometric): If there exists $d \in \mathbb{N}$ such that $a_{i+1} = da_{i}$ for all $i < n$, then $a_{n+1} = da_n$.

(Triangular): If $a_{i+1} = a_i + i$ for all $i < n$, then $a_{n + 1} = a_n + n$.

(Squares): If $a_{i} = i^2$ for all $i \leq n$, then $a_{n+1} = (n+1)^2$.

(Cubes): If $a_{i} = i^3$ for all $i \leq n$, then $a_{n+1} = (n+1)^3$.

(Fibonacci): If $a_0 = 0$, $a_1 = 1$, and $a_{i+2} = a_i + a_{i+1}$ for all $i < n - 1$, then $a_{n+1} = a_{n-1} + a_{n}$.

These seem to be a reasonable minimum set of conditions given by http://www.mathsisfun.com/numberpatterns.html .

Letting $\mathcal{C}$ be the class of computable functions, define $F: \bigcup_{4 \leq n}{\mathbb{N}}^{n+1} \rightarrow \mathcal{C}$ to be a correct function if for every $s \in \mathbb{N}^{n+1} \cap dom(F)$ (finite sequences of Natural numbers of length at least 5: index from 0 to $n$, inclusively), $F(s)_{n+1}$ is correct with respect to $s$. In other words, a function is correct if each finite sequence of Natural numbers of length at least 5 is assigned a computable function that extends the sequence correctly according to the above rules.

By associating each finite sequence $\langle s_0, s_1, \cdots, s_n\rangle$ with $\prod_{i=0}^n p_i^{s_i}$ where $p_i$ is the $i^{th}$ prime number and each computable function with its Natural number program index for some fixed Universal Turing Machine, we may use the Cantor pairing function to code each $(s, f) \in F$ as a Natural number $\langle s, f\rangle$. Consequently, $F$ can be associated with a subset of Natural numbers. We can then say that $F$ is computable if this corresponding subset of Natural numbers is decidable.

My question then is as follows:

We can verify that there are correct computable functions according to the above characterization, but are there any ones that are completely determined by some reasonable description?

For example, do we have one that assigns each sequence $s$ a primitive recursive function $f_s$ such that for all primitive recursive $f$ correctly extending $s$, $f_s$ requires the shortest proof showing that it is primitive recursive using the primitive recursive axioms? (See http://en.wikipedia.org/wiki/Primitive_recursive_function#Definition .)

What number comes next in the sequence? - MathOverflow [closed]

What number comes next in the sequence?