question about parallel sequence making prime

[Brendan McKay]

Hi,  This problem occurred in my formal languages course.
I'm guessing there is some interesting exploration possible.

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

Example:
   1  3  7  8 24 25 27 32 48 ...
   1  8 24  3  7 48 32 27 25 ...
Thus 24+7 is prime, but 24+1,24+8,24+24,24+3,24+48,24+32,24+27,24+25 aren't.

It is fairly clear that such a sequence exists.  Choose in the
order a(1),b(1),a(2),b(2),... and probably <I didn't do it!> it
is not hard to prove that a choice is always available.
I made the example in this fashion starting with a(1)=1 and
always choosing the smallest available value.  For example,
b(3)=24 is the smallest number such that a(1)+b(3) and 
a(2)+b(3) are composite but a(3)+b(3) is prime.

Note the curious way that the second sequence looks like a
permutation of the first (so far).  Why is that?

Brendan.



If the terms of the sequences are chosen greedily in the order a(1),
b(1), a(2), b(2), etc. then the a- sequence has to be increasing.

Given that, since b(10) = 504 and a(25) = 468, a(26) = 519, the two

But the rate of growth of the sequences, as well as what percentage of the
b-sequence terms are contained in the a-sequence, is an interesting
question.

Jeffrey Shallit


> From seqfan-owner at ext.jussieu.fr  Wed Feb 21 08:21:18 2007
> From: Brendan McKay <bdm at cs.anu.edu.au>
> To: seqfan at ext.jussieu.fr
> Subject: question about parallel sequence making prime
> 
> Hi,  This problem occurred in my formal languages course.
> I'm guessing there is some interesting exploration possible.
> 
> 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
> 
> Example:
>    1  3  7  8 24 25 27 32 48 ...
>    1  8 24  3  7 48 32 27 25 ...
> Thus 24+7 is prime, but 24+1,24+8,24+24,24+3,24+48,24+32,24+27,24+25 aren't.
> 
> It is fairly clear that such a sequence exists.  Choose in the
> order a(1),b(1),a(2),b(2),... and probably <I didn't do it!> it
> is not hard to prove that a choice is always available.
> I made the example in this fashion starting with a(1)=1 and
> always choosing the smallest available value.  For example,
> b(3)=24 is the smallest number such that a(1)+b(3) and 
> a(2)+b(3) are composite but a(3)+b(3) is prime.
> 
> Note the curious way that the second sequence looks like a
> permutation of the first (so far).  Why is that?
> 
> Brendan.
>