Apologies for the somewhat vague nature of this question, I'll include a more concrete question at the end.
I'm interested in sequences $a(1), a(2), a(3), \ldots$ satisfying
(*) $\qquad \gcd(a(m), a(n)) = 1$ for all $m, n$.
A famous, ancient, foolproof way of generating such sequences is repeated application of the construction in Euclid's proof that there are infinitely many prime numbers. Starting with $a(1) = 2$ this yields $a(1) = 2$, $a(2) = 3$, $a(3) = 7$, $a(4) = 43$, $a(5) = 1807$ etc. It is easy to see that these numbers are generated by the easy recurrence
$$(R1) \qquad a(n+1) = a(n)(a(n) - 1) + 1.$$
Proofs from the Book shows that the sequence of Fermat numbers also satisfy (*); they are generated by the somewhat similar recurrence relation:
$$(R2) \qquad a(0) = 3; \quad a(n+1) = (a(n) - 1)^2 + 1.$$
Finally there is a very neat argument (which I believed I learned from Proofs from the Book, but I checked and it isn't there, but perhaps it is in an earlier edition?) that the sequence generated by the recurrence
$$(R3) \qquad a(0) = 3; \quad a(n+1) = a(n)^2 - 2$$
also satisfies (*).
Now what sequences $R1, R2, R3$ have in common, besides satisfying (*) is:
1) They are generated by a really simple recurrence.
2) They grow really really fast.
When I say really really fast really mean really really fast. This is the kind of growth that makes asking for 1 grain of rice on the first square of chess board, two on the second and so on look like the epitome of modesty.
So my vague question is:
Are properties 1) and 2) somehow related? Is there a heuristic that suggests that, within the world of sequence satisfying (*), there is some sort of trade-off between simplicity and speed, with easier to describe sequences growing faster and the other way around?
Case in point: the slowest growing sequence satisfying (*) is of course the the sequence $p(1) = 2, p(2) = 3, p(3) = 5, \ldots$ of primes. From the Prime Number Theorem one can show (I believe) that $p(n) \leq n^2 + 1$ and sooner rather than later the numbers $n^2 + 1$ get so big that they can barely see the tiny number $p(n)$ from up there. So growth of $p(n)$ is really of a different order of magnitude than that of the sequences $a(n)$ above.
But at the same time so is the simplicity: it is conventional wisdom that no (direct or recursive) formula for $p(n)$ will be found in our lifetime for generous definitions of 'our'.
So in a sense I feel that the $a(n)$ and $p(n)$ represent two ends of a spectrum with slow, complicated sequences on one end and simple, fast sequences on the other.
Of course these examples don't answer the question what I mean by 'simplicity' in the supposed trade-off between simplicity and speed and frankly: I don't know.
So to compensate for this vagueness here a concrete question:
Can you give examples of sequences $b(n)$ satisfying (*) generated by an explicit (recurrence) formula that have growth rate 'intermediate' between $p(n)$ and the $a(n)$ above, e.g. satisfying $b(n) \sim 2^n$ or even $b(n) \sim n^2$?