question about parallel sequence making prime

[Dean Hickerson]

Brendan McKay wrote:

> Consider a pair of positive integer sequences
>    a(1),a(2),a(3),...
>    b(1),b(2),b(3),...
> with this property:
>   * for all i, a(i)+b(i) is prime
>   * for all i,j not equal, a(i)+b(j) is composite
...

Jeffrey Shallit replied:

> As a followup, here is a proof that the sequences actually exist and
> are infinite.  The proof was slightly trickier than I thought it would be.

The proof can be simplified.  Instead of the Chinese Remainder Theorem
and Dirichlet's theorem, we just use the fact that the set of primes is
infinite and has density zero.

> Suppose a(1), b(1), ..., a(k), b(k) have been computed.  Now we want
> to find a(k+1), the least positive integer t such that 
> b(1)+t, b(2)+t, ..., b(k)+t are all composite.   We need to ensure
> such an integer exists.  To do so, use the Chinese Remainder theorem
> and ask that
...

The primes have density 0 so, for almost all integers t, none of b(1)+t, ...,
b(k)+t are prime.

> Now we have to show b(k+1) exists.  To do so, we need to use both the
> Chinese remainder theorem and Dirichlet's theorem on primes in arithmetic
> progressions.  We want to ensure the existence of an s such that
> a(1)+s, a(2)+s, ..., a(k)+s are all composite, and a(k+1)+s is prime.
...

Since the primes have density 0, there exist arbitrarily large gaps between
consecutive primes.  Pick a prime p such that none of p-a(1), ..., p-a(k)
are prime and let  s = p-a(k+1).

Dean Hickerson
dean at math.ucdavis.edu