General Euclid-Fermat sequences

Question

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.

Answer 1

This is a continuation of my "QUESTION" (to make editing easier; possibly, reading too?)

I'll present another sequence which in a naive sense is much slower than E-F sequences but unfortunately still hopelessly fast, it's still super-exponential. Perhaps you can simplify my description or provide a simpler and slower sequence.

A sequence slower than Euclid-Fermat sequences

Let $\mathbb N\ :=\ \{1\ 2\ \ldots\}$. Let an auxiliary sequence   $ A:\mathbb N\rightarrow\mathbb N$   be given by the following three conditions:

• $ A(1)\ :=\ 3 $
• $ A(2)\ := 10 $
• $ A(n+1)\ :=\ A(n-1)\cdot(A(n)-A(n-1)) $

for every   $n = 2\ 3\ \ldots$.   Next, let

• $ s(0) := 2 $
• $ s(1) := 3 $
• $ s(3) := 5 $
• $ s(n+1)\ :=\ A(n) - A(n-1) $

for every   $ n = 2\ 3\ \ldots $.   Thus   $s(n)$   is a prime for every   $n=0\ldots 7$,   but not for   $n=8$.   Anyway, every two different terms of sequence   $s$   are relatively prime, and

$$ \forall_{n=3\ 4\ \ldots}\qquad s(n)\ <\ 2^{\Phi^n} $$

where

$$ \Phi\ :=\ \frac{1+\sqrt 5}2 $$

(That's awful but much better than $2^{2^n}$).

Answer 2

The following is an example of the sequence satisfying your conditions when “simple” is meant in terms of the complexity of the definition (formula). From computational perspective the sequence seems to be useless. Integers in this sequence are primes (not only pairwise relatively prime). The example comes from here.

Start with Rowland's Sequence (mentioned also in Wikipedia) $$R(1) = 7$$ for $ n\geq 2$: $R(n) = R(n - 1) + gcd(R(n - 1); n)$

First terms of the sequence can be found here

Now if we record in Rowland's sequence every $n + 1$ such that $R(n) = 2n + 2$, then we’ll get the sequence (let's call it Cloitre's sequence): $5; 11; 23; 47; 101; 233; 467; 941; 1889; 3779; 7559; 15131; 30323; 60647; …$

It exhibits “[primes in increasing order (and the growth is exponential)]”