What number comes next in the sequence? - MathOverflow [closed] most recent 30 from http://mathoverflow.net 2013-05-21T09:06:49Z http://mathoverflow.net/feeds/question/49237 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/49237/what-number-comes-next-in-the-sequence What number comes next in the sequence? Jason 2010-12-13T09:44:27Z 2010-12-14T01:37:14Z <p>It always bothers me when I hear a problem such as the following:</p> <p>The first few numbers in the sequence are 1, 2, 4, 8. What number comes next?</p> <p>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.</p> <p>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:</p> <p>(Arithmetic): If there exists $d \in \mathbb{N}$ such that $a_{i+1} = a_i + d$ for all $i &lt; n$, then $a_{n+1} = a_n + d$.</p> <p>(Geometric): If there exists $d \in \mathbb{N}$ such that $a_{i+1} = da_{i}$ for all $i &lt; n$, then $a_{n+1} = da_n$.</p> <p>(Triangular): If $a_{i+1} = a_i + i$ for all $i &lt; n$, then $a_{n + 1} = a_n + n$.</p> <p>(Squares): If $a_{i} = i^2$ for all $i \leq n$, then $a_{n+1} = (n+1)^2$.</p> <p>(Cubes): If $a_{i} = i^3$ for all $i \leq n$, then $a_{n+1} = (n+1)^3$.</p> <p>(Fibonacci): If $a_0 = 0$, $a_1 = 1$, and $a_{i+2} = a_i + a_{i+1}$ for all $i &lt; n - 1$, then $a_{n+1} = a_{n-1} + a_{n}$.</p> <p>These seem to be a reasonable minimum set of conditions given by <a href="http://www.mathsisfun.com/numberpatterns.html" rel="nofollow">http://www.mathsisfun.com/numberpatterns.html</a> . </p> <p>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.</p> <p>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.</p> <p>My question then is as follows: <BLOCKQUOTE> 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? </BLOCKQUOTE></p> <p>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 <a href="http://en.wikipedia.org/wiki/Primitive_recursive_function#Definition" rel="nofollow">http://en.wikipedia.org/wiki/Primitive_recursive_function#Definition</a> .) </p>