3
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Aravind May 21 at 9:16
  • 1
    $\begingroup$ The growth rate of $p(n)$ is $p(n)\sim n\ln{(n)}$ by the prime number theorem. $\endgroup$ – Peter Foreman May 21 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.