## Question

Fermat sequence

$$ \forall_{n=1\ 2\ \ldots}\quad F_n:=2^{2^{n-1}}+1$$

has every two different terms relatively prime, and $1$ does not appear as any of them. Thus it would be a nice (algorithmic, algebraic) substitute for the rather compicated sequence of primes except that it grows way too fast. There is an entire $2$-parameter family of such sequences but all of them grow about as fast as the Fermat sequence. As an illustration I'll present this family below, under the question. Later I'll add one more example, a bit more complex but growing much slower--still awfully fast, super-exponentially. Thus the question arises:

are there "simple" sequences $(a_n: n=1\ 2\ ...)$ of integers such that $\forall_{n=1\ 2\ \ldots}\ |a_n|\ne 1$, every two terms are relatively prime, and the sequence of maxima $\max(|a_k|:k=1\ldots n)$ grows exponentially or slower?

"Simple" may be meant in terms of computing or of the complexity of the definition (formula, etc). I don't want to constrain this question in a formal straight jacket. All examples which shed light on the sequence of primes are welcome, as well as any theorems which show that in a sense (this time in a "formal sense") such sequences are impossible.

As a minimum, any sequence as above provides an upper bound on the $n$-th prime $p_2$ since:

$$ \max(|a_k|:k=1\ldots n) \ge p_n $$

**REMARK** A sparse subsequence of values $-1\ \ 1$ may be allowed if it somehow helps to obtain a nice formula (when it does not help too much the slowness of the growth of the sequence).

## Euclid-Fermat sequences

Let integers $a\ b$ be such that $|a|>1$ and $\gcd(a\ b)=1$. Then let:

- $a_1:=a$
- $a_{n+1} := (a_n-b)\cdot a_n+b$

Then a simple induction or naive three-dot argument shows that:

$$a_{n+1}-b\ =\ (a_n-b)\cdot a_n\ =\ (a_{n-1}-b)\cdot a_{n-1}\cdot a_n\ =\ \ldots$$

hence

$$a_{n+1}\ \ =\ \ (a-b)\cdot a_1\cdot\ldots\cdot a_n\ +\ b$$

which shows that every two terms $a_k\ a_n\ \ (k\ne n)$ are relatively prime (and relatively prime to $a-b$ too, so that one could incorporate $a_0:=a-b$ into the sequence, especially when $|a-b|\ne 1$).

All this is in the spirit of Euclid prime inifinitude. For $(a\ b)\ :=\ (2\ 1)$ we obtain the sequence which Euclid could use in his proof. For $(a\ b)\ :=\ (3\ 2)$ we get the Fermat sequence.

8more comments