Comments from Andrew V. Sutherland (drew(AT)math.mit.edu)
on A139317 and A139319.

Date: 13 Apr 2008 18:53:41 -0400

I have a few quick observations on your sequences. I should preface these 
with the caveat that I threw together a program to do these computations 
quickly and have not taken the time to carefully vet the results.

1) The first million entries of both sequences appear to be prime, the 
maximum value for A139317 in this range is a(860831)=156671243, and for 
A139319 we have a(919447)=150789307. I used a probabilistic primality test, 
so these results are not guaranteed.

2) Every prime less than 65536 occurs within the first 32723 terms of 
A139317. The corresponding value for A139319 is 32749.

3) For both sequences, the growth rate of max(a(n)) appears to be faster 
than cn*log^2(n) but slower than cn*log^3(n). This is a cursory estimate 
based on a quick glance a the data and could easily be wrong.

Regarding your questions, I note that an affirmative answer to the first 
implies the second, i.e. if there are no composites in the sequence, then 
every prime must occur. If p is a prime, then A139317(p-1) is either equal 
to p, or some earlier term in the sequence is a multiple of p, but if all 
terms are prime this must be p itself. A similar argument applies to 
A139319(p+1).

I believe that conjectured bounds on the least prime in arithmetic 
progressions would assure that for sufficiently large n there is a prime 
congruent to 1 mod n which is smaller than n^2. This would suffice, in 
conjuction with the argument above, to show every term is prime. However 
the best effective bounds I have heard are something like O(n^4.5) which 
leaves a lot of room for composites whose prime factors are all bigger than 
n to creep in.

Regards,

Drew

On Apr 13 2008, Leroy Quet wrote:

>I just submitted these two sequences:
>
>%S A139317 2,3,7,5,11,13,29,17,19,31,23,37
>%N A139317 a(n) = the smallest value of the form
>n*k +1, k = positive integer, that is coprime to
>all the previous terms of this sequence.
>%C A139317 Are there any composites in this
>sequence? If not, is this sequence a permutation
>of the primes?
>%e A139317 For a(7) we check: 7*1 +1= 8, which is
>not coprime to a(1)=2. 7*2 +1= 15, which is not
>coprime to either a(2)=3 or to a(4)=5. 7*3 +1 =
>22, which is not coprime to either a(1)=2 or to
>a(5)=11. But 7*4+1 = 29, which is coprime to
>terms a(1) through a(6). So a(7) = 29.
>%Y A139317 A139318,A139319
>%O A139317 1
>%K A139317 ,more,nonn,
>
>%S A139319 1,1,2,3,19,5,13,7,17,29,43,11
>%N A139319 a(n) = the smallest value of the form
>n*k -1, k = positive integer, that is coprime to
>all the previous terms of this sequence. a(1)=1.
>%C A139319 Are there any composites in this
>sequence? If not, is this sequence, with the
>exception of terms a(1) and a(2), a permutation
>of the primes?
>%e A139319 For a(10) we check: 10*1 -1= 9, which
>is not coprime to a(4)=3. 10*2 -1= 19, which is
>not coprime to a(5)=19. But 10*3 -1 = 29, which
>is coprime to terms a(1) through a(9). So a(10) =
>29.
>%Y A139319 A139317,A1393120
>%O A139319 1
>%K A139319 ,more,nonn,
>
>A139318 and A139320 are the sequences of k's for
>sequences A139317 and A139319.
>
>
>See the C-lines for the questions I have.
>(Perhaps simply calculating a few more terms will
>answer if there are indeed composites, even if it
>does not prove that the sequences contain all
>primes.)
>
>Thanks,
>Leroy Quet
>
>