[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]=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?
More information about the SeqFan
mailing list