5
$\begingroup$

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.

$\endgroup$
13
  • $\begingroup$ The answer to the question is, yes, the sequence of primes satisfies the condition. But you already know this, and you know that various subsequences (e.g., the primes 1 more than a multiple of 4) also satisfy the condition, so you must be wanting to ask something other than what you are actually asking. $\endgroup$ Jun 30, 2013 at 0:33
  • $\begingroup$ Gerry, I planned but forgot to mention that the sequence of primes is the slowest among increasing sequences of integers $> 1$ and such that each pair of its different terms is relatively prime. But (as I've written already in the original version of the question--at this moment there is one version anyway) it seems difficult to obtain such sequences which are either easy to compute or which admit a simple algebraic definition. $\endgroup$ Jun 30, 2013 at 1:11
  • $\begingroup$ Cont. Such sequences could serve as an approximation of the sequence of all primes (except that they don't want to). $\endgroup$ Jun 30, 2013 at 1:36
  • $\begingroup$ You might be able to show for some recurrences that slow growing means existence of a p that divides more than one term. You might also enjoy wheel sieving, which is a sped-up Eratosthenes sieve; I have four lines of obfuscated code which generate such sieves available upon request. $\endgroup$ Jun 30, 2013 at 1:52
  • 3
    $\begingroup$ From Erdős/Surányi (the Hungarian version of the 2nd edition is from 1995): "We can also produce other such sequences whose elements are pairwise relatively prime, but no such sequence is known that would give a significantly better lower bound" on the prime-counting function than the $c\cdot\log \log x$ obtained from the Fermat sequence. $\endgroup$
    – balpha
    Jul 2, 2013 at 11:17

2 Answers 2

3
$\begingroup$

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}$).

$\endgroup$
4
  • 1
    $\begingroup$ Doesn't the sequence $n!+1$ satisfy your conditions? It grows fast, but not as fast as $e^{n\log n}$, so definitely not doubly-exponential. $\endgroup$ Jun 30, 2013 at 5:01
  • 3
    $\begingroup$ @Gerry No, it turns out that $661$ divides $n!+1$ for $n=8, 17, 294, 318, 576, 643, 660.$ Also, $3!+1$ and $6!+1$ are both multiples of $7.$ For $p$ prime we have that $(p-1)!+1$ is a multiple of $p.$ But often $p$ divides $n!+1$ for a smaller $n$. $\endgroup$ Jun 30, 2013 at 7:22
  • 1
    $\begingroup$ The small bits I have presented in this thread are all very naive--post-Euclidean and pre-Euler. But the challenge seems to be real. I infer it experimentally or something like this: there must be a good reason why non-elementary analytic methods are so dominant in the theory of prime numbers. But never say die. Hence my stubborn question. $\endgroup$ Jun 30, 2013 at 8:41
  • $\begingroup$ PS. Thumbs up for both of the preceding comments--by Gerry and Aaron, they illustrate the theme, give a glimpse into it. $\endgroup$ Jun 30, 2013 at 8:47
1
$\begingroup$

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)]”

$\endgroup$
3
  • 1
    $\begingroup$ Interesting, even weird. I read in OEIS that the derived sequence (of the first differences) $\gcd(R(n-1)\ n)$ for $n=2\ 3\ \ldots$ consists of $1$s and primes only. The Euclid so beautiful proof, and the Fermat sequence, give a very poor idea about the prime distribution. Thus one wants slower sequences. But this one doesn't seem to help, doesn't give any clear bounds. There are a lot of $1$s, and the same primes occur multiple times. Thus it's all fun but of a different kind. $\endgroup$ Jul 2, 2013 at 17:55
  • $\begingroup$ it looks like sequence $5\ 11\ 23\ ...$ exhibits exponential growth. I am curious about the growth of the sequence $\nu(k)$ such that $R(n)=2\cdot n+2$ (I guess I'll check the link provided by you). $\endgroup$ Jul 2, 2013 at 18:04
  • $\begingroup$ The sentence about exponential growth meant to be a quote from the Waldemar's Answer. $\endgroup$ Jul 2, 2013 at 22:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.