prime chains generated by f(x)=ax+b

[Edwin Clark]

Don,

I just saw your message. This is just to let you know that I am
(slowly) working on prime chains of the type p, f(p), f(f(p)),...
for f(x)=ax+b for small values of a and b. This is not original with me,
of course. Apparently this is discussed in the paper by Lehmer:
(Some are already in the OEIS. Neil asked me to put the one for 3x+2 in
OEIS after I mentioned it.) I discovered these papers afterwards.
---------------------------------------------------------------------------
Lehmer, D. H. 
On certain chains of primes. 
Proc. London Math. Soc. (3) 14a 1965 183--186.
10.47

A prime chain of length $\lambda$ based on $(a,b)$ is a sequence of primes
$p_0,p_1,\cdots,p_{\lambda-1}$, where $a$ and $b$ are relatively prime,
$a>1$, and $p_k=ap_{k-1}+b$ for $k=1(1)\lambda-1$. The initial prime $p_0$
is called the leader of the chain. The author gives necessary conditions
for $p_0$ to lead a chain of length $\lambda$, discusses the problem of
searching for such chains and states some results for the case $a=2$,
$b=1$: For $p_0<10^7$, there are 714 chains of length 4, 142 chains of
length 5, 39 chains of length 6, 3 chains of length 7, and 0 chains of
length 8.
---------------------------------------------------------------------------
And chains using f(x) = ax^2-b are discussed in the following paper, as
you are probably aware.

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

Last night I ran a program to find the sequences a(n) = p where p is the
first prime such that for i from 0 to n-1  (f@@i)(p) is prime. (Here
(f@@i) is the Maple code for f composed with itself i times.) I did it for
the functions below. Each was run for just 15 minutes using Maple and a
not very efficient program:

f(t) = t+6, [2, 5, 5, 5, 5]
f(t) = t+2, [2, 3, 3]
f(t) = t+4, [2, 3, 3]
f(t) = 2*t+1, [2, 2, 2, 2, 2, 89, 1122659, 19099919]
f(t) = 2*t-1, [2, 2, 2, 1531, 1531, 16651, 16651, 15514861]
f(t) = 2*t+3, [2, 2, 2, 2, 47, 47, 6047, 477727]
f(t) = 2*t+5, [2, 3, 7, 13, 13, 13, 541, 4594309]
f(t) = 3*t+2, [2, 3, 5, 29, 1129, 10009, 575119]
f(t) = 3*t+4, [2, 3, 3, 23, 3203, 34613, 165443, 1274803]
f(t) = 4*t+5, [2, 2, 3]
f(t) = 4*t+3, [2, 2, 2, 2, 1447, 9769, 17231, 17231, 32611, 18527009]
f(t) = 4*t+1, [2, 3, 3]
f(t) = 4*t-1, [2, 2, 3]
f(t) = 5*t+2, [2, 3, 13, 19, 373, 135859, 135859, 18235423, 26588257]
f(t) = 5*t+6, [2, 5, 7, 7, 79, 79, 345431]
f(t) = 5*t+4, [2, 3, 5, 83, 263, 5333, 5333, 6714497]
f(t) = 6*t+1, [2, 2, 2, 61]
f(t) = 6*t-1, [2, 2, 3, 239]
f(t) = 6*t+5, [2, 2, 2, 2, 11, 13, 115571]

Some of these are known and/or easily explainable, like, t+2, t+4, t+6,
2t+1, 2t-1. I may understand the other short sequences better
after I read the above mentioned papers --which I haven't done yet.
I plan to enter the ones not already in the OEIS in a day or so.

--Edwin



PS I found your message a little hard to decipher. Could you state more
succintly the relationship to the above if any. Thanks.