Formulas for sequences of integers Does there exist a sequence of integers such that it is provable that there is no formula for the $n$-th term of the sequence expressed in terms of $n$?
Edit: By formula I mean an expression in terms of known arithmetic operations, functions, but not necessarily finitely many of them.
If you have an example, please provide a link to the proof that such a formula does not exist.
 A: Conway's sequence ?
$1,11, 21, 1211,111221,\dots$
If you want an actual answer, you need to precise what you mean by "formula"
A: The Kolakoski sequence $(K_n ) $, $A000002$ in the OEIS, has a fractal nature. This make difficullt to express 
explicitly  $K_n $ wrt $n $.
A: Here's one possible definition of "formula for the $n$'th term": a statement $S(X,Y)$ (in some particular language) with free variables $X$ and $Y$, such that for every positive integer $n$ there is at most one integer $y$ such that $S(n,y)$ is true.  The sequence $a_n$ is given by the formula $S(X,Y)$ if $S(n,a_n)$ is true for every $n$.
I'll assume that the language has a finite alphabet, such that all statements in the language correspond to finite strings in this alphabet.  Then there are only countably many formulas, and they can (in principle) be enumerated in lexicographic order.  Let $S_k(X,Y)$ be the $k$'th formula in this enumeration.  
Then the following sequence $a_n$ is not given by any formula.
$$
a_n = \cases{0 & if  $S_n(n,1)$ is true\cr
             1 & otherwise \cr}
$$
