Recursive Sequence: Highest Prime Divisors

[John Conway]

> 
> >In message <E19z5oZ-0005ss-00 at hall.mail.mindspring.net>, Leroy Quet
> ><qqquet at mindspring.com> writes
> >
> >>If we start with two positive integers {m,n}, and let
> >>a(1) = m, a(2) = n,    and for k >= 3,  a(k) = 
> >>(highest prime dividing a(k-1)) + 
> >>(highest prime dividing a(k-2)),

    It shouldn't be hard to prove the relevant facts about these.
We can replace the terms a(k) by the highest primes b(k) that divide 
them without losing any information.  Then if all terms are odd, b(k) 
is bounded above by the mean of b(k-1)  and b(k-2), and so by their 
maximum, and the sequence is bounded, and therefore periodic.  Of course 
the same holds if the terms are all odd  beyond some point.  Otherwise, 
the sequence b(k), if not all 2s,  looks like

    2, p, odd numbers =< p+2, ending with  p',
    2, q, odd numbers =< q+2, ending with  q',
    2, r, odd numbers =< r+2, ending with  r', ... .

   Now how could  q  strictly exceed  p  in such a sequence?  Obviously
only if  p' = p  or  p+2,  and in the latter case, only when  p,p+2,p+4 
are all prime, which forces them to be  3,5,7  and makes the sequence be

    2,3,5,2,7,3,5,2,7,...,  

which is periodic.  Apart from this we can only have the former case,
with  p,p+2  twin primes, which makes the sequence look like

     2,p,p+2,...,p,2,p+2,x,y,...

where  p  is at least 5 for us not to be in the case just discussed,
which entails that  x  is at most  (p+4)/3  since  p+4  cannot be prime,
and so  y  is at most the mean of  p+2  and this,  which is  (2p+5)/3,
which is at most  p  unless  2p+5 > 3p,  ie, 5>p, which we know ain't so.

   What this proves is that all the odd numbers following that second 2
are at most p, so the number following the next 2 must be at most p+2.
If it is  p  or  p+2  the sequence has gone periodic, and if not, we
have strictly decreased p.

   Conclusion:  it is indeed the case that all such sequences are
ultimately periodic.   Let's concentrate again on the sequences that
look like
    2,p,...,2,p+2,....,2,p,...   
or
    2,p,...,2,p+2,...,2,p+2,...,

since in the other cases  p  gets reduced, so we can ignore them.

   Any consecutive pair of numbers in that first block must include
one that's at least p, since otherwise the terms in that block from
then on would be < p, which leads to a contradiction.   If it starts
2,p,p+2,x,y  (x,y odd) then  x =< (p+1)/2, y =< (3p+5)/4,  and both
of these are < p  unless  3p+5 >=4p,  ie., 5 > p, which we can 
suppose it isn't.  

    If it starts  2,p,q,x   (where  q < p+2  and  q  and  x  are odd),  
then we have  q =< (p+2)/3,  x =< (p+q)/2 = (2p+1)/3, and both these
are  < p  unless  3p < 2p+1,  which again it isn't.  

   What this shows is that we get a reduction unless either the third or 
fourth term is 2,  say  2,p,q,2  or  2,p,p+2,x,2.  But in the first form,
either  q = p+2, which makes the term after the  2  be at most  (p+4)/3,
strictly less than  p  unless  3p =< p+4, which it isn't; or  q  is
at most  (p+2)/3  making the term after the  2  be  at most  2 + that,
ie., (p+8)/3,  which is  <  p  unless  3p =< p+8,  which it isn't.

   In the second form, we know that  x  is at most  (p+1)/2, so the term
after the 2 at most  2 + that  =  (p+5)/2,  which is  < p  unless  
2p =< p+5,  which again it isn't.  

    The conclusion is therefore that we get a strict reduction from
any  2,p,...  sequence unless  p =<5.  So all sequences that contain
a 2 but are not entirely 2s from some point on lead into 
3,5,2,7,3,5,2,7... .  If they don't contain 2s, then we get strict
decrease unless all the terms from some point on are equal.

   I remind you that I have been talking about the b(k) sequence.
The  a(k) sequence is obtained by adding adjacent pairs of terms, and so
is either ultimately constant or is  8,7,9,10,8,7,9,10,... , as
the original questioner conjectured.

   John Conway