[seqfan] Re: Coprime To Sums

[franktaw at netscape.net]

Any elements in this sequence (after 1) must be either primes or 
squares of primes; and in the latter case, the prime itself must appear 
in the sequence.

Note first that the condition "the smallest integer > a(n-1)" could 
just as well be "the smallest integer that has not yet appeared in the 
sequence"; if a value m < a(n-1) is eligible at step n, it was also 
eligible at step n-1, and would have been preferred to a(n-1).

The first value in the sequence -- if there is one -- divisible by any 
given prime p is p itself.  Anything else is larger.  Once a proper 
multiple of p has appeared in the sequence, there is a sum divisible by 
p, so no further multiples can occur.  Now if k*p occurred for some 1 < 
k < p, there is a prime divisor q of k, q < p, and by induction the 
only possible multiples of q  in the sequence are q and q^2.  So p^2 is 
the next and only multiple of p which could occur.

Here's a PARI program to compute the sequence:

al(n)={local(pl,r,p,q,m,ps);pl=vector(2*n);
 r=vector(n);r[1]=1;p=2;q=2;
 for(k=2,n,
   
while(pl[primepi(p)],p=nextprime(p+1));while(pl[primepi(q)],q=nextprime(q
+1));
  if(p<q^2,m=p;p=nextprime(p+1),m=q^2;q=nextprime(q+1)); r[k]=m;
   
for(j=1,k-1,ps=factor(r[j]+m)[,1]~;for(i=1,#ps,pl[primepi(ps[i])]=1)));r}


(I can't prove that the 2*n in the top line is always large enough, but 
it seems to be.  If it isn't, you will get an indexing error and can 
simply increase it.)

This produces:

1, 2, 4, 7, 13, 19, 29, 37, 43, 53, 59, 67, 73, 79, 89, 97, 103, 109, 
127, 137, 149, 157, 163, 173, 179, 191, 197, 211, 223, 229, 239, 251, 
257, 263, 269, 277, 283, 293, 307, 313, 331, 337, 347, 353, 359, 367, 
373, 379, 389, 397, 409, 419, 431, 439, 449, 457, 463, 479, 487, 499, 
509, 521, 541, 547, 557, 563, 569, 577, 587, 593, 599, 607, 613, 619, 
631, 641, 647, 653, 659, 673, 683, 691, 701, 709, 719, 727, 733, 739, 
751, 757, 769, 787, 797, 809, 821, 827, 839, 853, 859, 877,....

 From the density of these numbers, I think it unlikely that any more 
primes squared appear in the sequence; but I don't see any way to try 
proving it.

Probabilistically, if there are k terms less than n = p^2, there are 
k*(k-1)/2 relevant sums (the sums including p can be ignored).  The 
probability that none of these sums is divisible by p is 
(1-1/p)^(k*(k-1)/2).  It appears that k is on the order of n/log(n); 
substituting, the probability is on the order of 
(1-1/p)^(c*p^2/log(p)^2) for some c; this is approximately 
e^(-c*p/log(p)^2).  The sum of these, even over all integers, is 
finite, so one expects only finitely many primes squared in the 
sequence.

Franklin T. Adams-Watters

Leroy, if you have already submitted this sequence, please give me a 
reminder when it appears and I will add these values and program.  If 
you have not, please include them.

-----Original Message-----
From: Leroy Quet <q1qq2qqq3qqqq at yahoo.com>

I think this sequence was worth submitting during Neil's vacation.

%I A164901
%S A164901 1,2,4,7,13,19,29,37,43,53,59
%N A164901 a(1)=1, a(2) = 2. For n >=3, a(n) = the smallest integer > 
a(n-1)
that is coprime to every sum of any two distinct earlier terms of this 
sequence.

%e A164901 The first 4 terms are 1,2,4,7. The sums of every pair of 
distinct
terms are: 1+2=3, 1+4=5, 2+4=6, 7+1=8, 7+2=9, and 7+4=11. So, we are 
looking for
the smallest integer > 7 that is coprime to 3, 5, 6, 8, 9, and 11. This 
number,
which is a(5), is 13.
%Y A164901 A164902,A164903
%K A164901 more,nonn
%O A164901 1,2

... Are there any more composites in the sequence? If so, are there an
infinite number of composites? If so, could someone please calculate a 
number of
terms of the sequences where one sequence contains the primes of 
A164901, and
the other sequence contains the composites?