# Sequences of pairwise coprime numbers: trade-off between growth rate and simplicity?

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$$?

• When you say really, really fast, you mean $2^{2^n}$, which isn't... that fast. Many algorithms and math problems deal with functions that are iterated powers of 2, that is they satisfy $f(n)=2^{f(n-1)}$. See also en.wikipedia.org/wiki/Ackermann_function for a really, really fast function. Nice question, though. – Aravind May 21 at 9:16
• The growth rate of $p(n)$ is $p(n)\sim n\ln{(n)}$ by the prime number theorem. – Peter Foreman May 21 at 9:16