3 added a tag for increased visibility
2 added 2514 characters in body

Can we make

First let's formally introduce some minimum set of conditions for what it means for the question, "What next number comes next?to be "more precise so 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 indeed only one correct answer?

I believe that research has been done on this very question 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 partial positive answercomputable function that extends the sequence correctly according to the above rules.

By associating each finite sequence $\langle s_0, but I'm not sure 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 exact referencesones 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 .)

Post Closed as "not a real question" by Mark Sapir, Ryan Budney, Chandan Singh Dalawat, Daniel Moskovich, Willie Wong
1