# [seqfan] Re: Coprime To Sums

franktaw at netscape.net franktaw at netscape.net
Sun Aug 30 22:26:31 CEST 2009

```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;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.

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?

```