3x+2

[Edwin Clark]

On Tue, 10 Jun 2003, y.kohmoto wrote:

>     On Mon, 9 Jun 2003 Edwin Clark wrote:
> 
> >On Sun, 8 Jun 2003, Jud McCranie wrote:
> >
> >> At 05:41 AM 6/8/2003, y.kohmoto wrote:
> >> %N A000001 a(n) is the greatest prime factor of 3*a(n-1)+2 .
> >>
> >> >     I conjectured as follows :
> >> >     "for all number m, if a(1)=m then the sequence becomes cyclic."
> >> >
> >> >     Is there any counter example?
> >>
> >> A quick test shows it holds to 2,120,000 (at least).
> >>
> >>
> >
> >I got similar results. Note that one just needs to check it for
> >primes. This raises the question: Let f(x)=3x+2. Is it true that for each
> >n there is a prime p such that (f@@i)(p) is prime for i = 0, 1, 2, ...,
> >n. [Here f@@i is the composition of f with itself i times.]
> >
> > If a(n) = the least such prime then we have the sequence
> >
> >    2, 3, 5, 29, 1129, 10009, 575119
> >
> >For example, this means that if p = 29 then p,f(p),f(f(p)),f(f(f(p))) are
> >primes.
> >
> >Is there another term in this sequence?
> >
> >Has anyone seen another such sequence with a different f?
> >
> >--Edwin
> >
> >
> 
>     Dear Jud
>     Thanks for the verifying up to 2,120,000.
> 
>     Dear Edwin
>     I thought the same thing.
>     "a prime p such that (f@@i)(p) is prime for i = 0, 1, 2, ...,"
>     It looks like a Sophi German prime or Cuningham's prime chain.
>     Is it true if your sequence is infinit then a counter example exists?
> 

After writing the above I searched the literature and found the references
in Guy's UPNT to Cunningham sequences where f(x)=2x+1 or f(x)=2x-1 and the
reference to Lehmer's paper where he discusses the general case f(x) =
ax+b where gcd(a,b)=1. I also came across a paper which discusses the case
f(x) = ax^2-b in MathSciNet:
-------------------------------------------------------------------------
Teske, Edlyn(3-WTRL-B); Williams, Hugh C.(3-MB-C) 
A note on Shanks's chains of primes. (English. English summary) 
Algorithmic number theory (Leiden, 2000), 563--580, 
Lecture Notes in Comput. Sci., 1838, 
Springer, Berlin, 2000. 
11Y55 (11A41)
           
A Shanks chain of primes $p_1,p_2,\dots,p_k$ is a list of $k$ primes where
$p_{i+1}=ap_i^2-b$ for $1\le i<k$ and $a,b$ are integers. The authors show
that for all but 56 pairs of $a,b$ values with $ab\le 1000$, any
corresponding Shanks chain must have bounded length. The proof of this
result is based in part on extensive computer calculations. The authors
motivate this problem with an excerpt from a letter Daniel Shanks wrote to
D. H. and Emma Lehmer in 1969. 
---------------------------------------------------------------------------

For your sequences I see no reason not to use cx+d or cx^2+d or any
reasonable function for that matter and since you aren't looking for
primes there is no need to assume gcd(c,d) = 1. 

I checked the sequences a(n) = max prime factor of c*a(n-1) + d where
a(1) = m for c,d in {1,2,...,6} for m from 1 to 1000 and found each to be
ultimately periodic. The sequences using a(n) = max prime factor of
c*a(n-1)^2 + d are harder to check since the numbers grow in size so
rapidly.

Certainly if a(n) is prime for all n then the sequence is not ultimately
periodic. But is the converse true (when gcd(c,d) = 1)? Maybe the papers
by Lehmer and the above shed some light on this question. I haven't looked
them up.

Best wishes,

Edwin