Sequence for which no closed form can exist I was wondering whether there exists a (computable) sequence of numbers, for which it can be proven that no closed form can exist. 
Edit: By closed form I mean an expression involving only a constant number of elementary functions. So something like a sum can not occur in the expression. 
 A: Inevitably, the answer will depend on what one means by closed form.  We consider computable sequences of non-negative integers, that is, computable functions  $f(x)$ from  the non-negative integers to the non-negative integers. We will allow the least number operator $\mu$, as well as operations of ordinary arithmetic. 
The least number operator may not be familiar, so we define it. Let $R(y,x_1,\dots,x_n)$ be a relation such that for all $x_1,\dots,x_n$ there is a $y$ such that $R(y, x_1,\dots,x_n)$ holds. Then $\mu y R(y,x_1,\dots,x_n)$ is the least such $y$. 
As a consequence of Matijasevic's solution of Hilbert's Tenth Problem, there is a fixed polynomial $P(e, x, u_1,\cdots, u_k)$ with the following property. 
For any computable function $f$, there is a non-negative integer $e=e(f)$ such that for any $x$,
$$f(x)=[\mu y( P(e, x, [y]_1,[y]_2, \dots, [y]_k)=0)]_0.$$
Here by $[w]_i$ we mean the exponent of the $i$-th prime $p_i$ in the prime power decomposition of $w$.  (The $0$-th prime is $2$.)
This gives what I would consider a positive answer to the closed form question: Every computable sequence has a closed form. Many theorems of the same general kind were known long before the work of Matijasevic, except that instead of a polynomial $P$, one had a more complicated function. 
If the $\mu$-operator is not allowed, there are quite a few different workarounds. 
A: The most famous and interesting one is probably the sequence of primes (if you mean a closed form in terms of elementary functions).
Goldbach proved that no polynomial with integer coefficients can give a prime for all integer values. However it is not fully clear that there isn't some elementary function that generates all primes.
There is a whole wikipedia article on formulas for primes.
A: I am going to guess that closed form numbers can be computed in polynomial time or some kind of bounded complexity (depends on your definition of closed form), but there are for sure computable sequences that take much longer to compute
