Examples of sequences whose asymptotics can't be described by elementary functions It is somewhat miraculous to me that even very complicated sequences $a_n$ which arise in various areas of mathematics have the property that there exists an elementary function $f(n)$ such that $a_n = \Theta(f(n))$ or, even better, $a_n \sim f(n)$.  Examples include 


*

*Stirling's approximation $n! \sim \sqrt{2\pi n} \left( \frac{n}{e} \right)^n$ (and its various implications),

*The asymptotics of the partition function $p_n \sim \frac{1}{4n \sqrt{3}} \exp \left( \pi \sqrt{ \frac{2n}{3} } \right)$,

*The prime number theorem $\pi(n) \sim \frac{n}{\log n}$,

*The asymptotics of the off-diagonal Ramsey numbers $R(3, n) = \Theta \left( \frac{n^2}{\log n} \right)$.


What are examples of sequences $a_n$ which occur "in nature" and which provably don't have this property (either the weak or strong version)?  Simpler examples preferred.
(I guess I should mention that I am not interested in sequences which don't have this property for computability reasons, e.g. the busy beaver function.  I am more interested in, for example, natural examples of sequences with "half-exponential" asymptotic growth.)
 A: Davenport–Schinzel sequences are related to complexity of arrangements of various geometric shapes (e.g. envelopes of line segments). Their asymptotics is described in terms of the inverse Ackermann function.
A: The Bell numbers, have asymptotics related to the Lambert W function.
EDIT: I was poking around on mathworld today, and found that the Gram Points also have W function related asymptotics.
A: Consider Cantor staircase function $f:\ [0,1]\rightarrow [0,1]$ and the moment function $F(x):=\int_0^1 (f(t))^x dt$. When $x$ tends to $+\infty$, it behaves like $x^{-\sigma}$, $\sigma:=\ln 3/\ln 2$. But the limit $F(x)\cdot x^{\sigma}$ does not exist: this value oscillates very slowly around a constant $1.9967\dots$
See more in Russian here: http://www.math.spbu.ru/analysis/f-doska/lap_can.pdf
A: Some algorithms have a running time which involves $\log^* n$, the number of iterations of $\log$ before the result is at most $1$. This is essentially the inverse of tetration base $e$. For example, the Fredman-Tarjan algorithm for finding a minimal weight spanning tree has run time $E ~\log^* V$, and the randomized algorithm by Clarkson et al. for triangulating a simple polygon with $n$ vertices has expected running time $n ~\log^* n$. (In both cases, there are asymptotically faster algorithms by Bernard Chazelle.) 
A: Suppose F is a field of finite characteristic and u,v,w lie in A=F[x,y]. Let a_n be the dimension of the vector space A/(u^n,v^n,w^n). Suppose a_1 is >0 and finite. Then as n grows,
(a_n)/(n^2), though bounded above and bounded away from 0 generally has an oscillating "fractal-like" behavior.
A: Since this is community wiki, I won't feel that bad about not offering any crisp answers, but more of an abstract point of view which might suggest another avenue of pursuit. 
To me the basic subject matter goes by the name "Hardy fields": fields of germs of real-valued functions at infinity. One of the basic examples is the field of germs of all functions that can be built up from polynomials, exponentials, and logarithms, and closed under the four arithmetic operations and composition. 
A wonderful fact is the trichotomy law: that such "log-exp functions" are either eventually positive, eventually zero, or eventually negative. This is perhaps along the lines of the monotonicity assumptions Qiaochu mentioned above. It guarantees that the germs at infinity of such functions do indeed form a field $K$. Sitting inside the field is a valuation ring consisting of germs of bounded functions, $O$. There is a corresponding valuation on $K$ whose value group is $K^\ast/O^\ast$. 
The elements of $K^\ast/O^\ast$ may be called "rates of growth". Indeed, two germs of functions $[f]$, $[g]$ are equivalent mod $O^\ast$ iff both $f/g$ and $g/f$ are bounded, which is to say they are asymptotic (up to a constant) -- remember that by trichotomy, these bounded functions do not oscillate but tend to a definite limit. 
From this point of view, we are interested in naturally arising Hardy fields whose value groups strictly contain the value group of the log-exp class mentioned above (so that we get "intermediate rates of growth"). 
The reason I mention all this is that I think there is a pretty big literature on constructions of Hardy fields (which unfortunately I am not very familiar with). One area of research is via model theory and particularly o-minimal structures, where o-minimality guarantees the trichotomy law above. There are experts out there (for example, David Marker, if he's listening) who may be able to give us "natural" examples of o-minimal structures with such intermediate rates of growth at infinity. I'd be interested in this myself. 
Edit: And now that I've written this, I have a memory that there are theorems in o-minimal structure theory which tend to rule out such intermediate rates of growth! That in itself would be interesting, and anyhow maybe someone like David Marker would know some interesting examples anyway, whether from o-minimal structure theory or not. 
A: Several arithmetical functions don't have an equivalent in terms of an elementary function, but only have an equivalent "in the mean". For instance $d(n)$, the number of divisors of $n$, is quite irregular, but satisfies
$$\frac1n(d(1)+\cdots+d(n))\sim\log n.$$
Likewise, the sum $\sigma(n)$ of divisors of $n$ is irregular (though a little less than $d(n)$) but satisfies
$$\frac1n(\sigma(1)+\cdots+\sigma(n))\sim\frac{\pi^2n}{12}.$$
Finally, the average order of the Euler indicator $\phi(n)$ is $\frac{3n}{\pi^2}$.
A: Iterated exponentials $\exp^{[n]}(x)$ grow faster than any elementary function.
It is possible to construct many functions which grow even faster.
