Recursive Sequence: Highest Prime Divisors

jens at jens at
Tue Sep 16 09:26:17 CEST 2003

Kennedy wrote:
> After fiddling around with your sequence for a few minutes,
> I got the sense that it is akin to the as yet intractable 3n+1
> about which Paul Erdös supposedly commented:
> "Mathematics is not yet ready for such problems."

Why so pessimistic; the above sequence is several orders of magnitude
easier to handle than the Collatz problem.

An equivalent sequence is defined as follows:
b(1) and b(2) are primes, and b(n+2) is the largest prime
divisor or b(n) + b(n+1).
The key observation is that for "large" start (or intermediate) values,
the terms of the sequence are quite rapidly decreasing which shows:

(i) If b(1) and b(2) are not equal, then b contains the prime 2
infinitely many times.

Similarly, if b is not constant and p is the smallest prime ever
preceding a 2 in b, then p cannot be too large:

(ii) If b(1) and b(2) are not equal, then at some point in the
sequence, a 2 is preceded by a 3 or a 5.

(i) and (ii) easily yield

(iii) Every non-constant sequence b is periodic with period (3, 5, 2,


Before you criticize someone, you should walk a mile in his shoes.   
That way, when you criticize him, you are a mile away from him and you
have his shoes.

More information about the SeqFan mailing list