It's time for an announcement:-

M+[s,n] = (s+2)^n - lucasV(s+2,s+2,n) + 1
M-[s,n] = s^n - lucasV(s+2,s,n) + 1
are series of "Mersenne" type, in that they are composite unless n is prime,
the n'th term divides the (k*n)'th term, and so on;

and
F+[s,n] = (s+2)^n + lucasV(s+2,s+2,n) + 1
F-[s,n] = s^n + lucasV(s+2,s,n) + 1
are series of "Fermat" type, in that they are composite unless n=2^k, and so
on.

In these formulae, s is any positive or negative integer, n >= 0,
and lucasV(P,Q,n) can be defined (for any P and Q) by the recurrence
relations:-
v[0] = 2
v[1] = P
v[n+2] = P*v[n+1] - Q*v[n] for n >= 0.

----------

I have spent several months of Athlon 1200 time doing a systematic
investigation of all 4 series for |s| <= 20 and n <= 16384, and for some
larger values of s <= 10^20. They have many remarkable properties. For
instance, the relation between n and possible prime factors is along the
lines of the Mersenne p=1 mod 2*n, but too long a story for this post; but it
allows fast sieves to be coded.

Consider first the "M+" series:

For each value of s (except for s=-2,-1,+2) the series contains a (probably
infinite) number of primes, and (except for s=-3) these are all BLS-provable!

Certain of the smaller s values are special:-
s = -3: (-1)^n - lucasV(-1,-1,n) + 1 = L(n) for n odd, = L(n)+2 for n even,
where L(n) are the Lucas numbers, i.e. L(n) = 2,1,3,4,7,.... for n =
0,1,2,3,4,...
s = -2: 0^n - lucasV(0,0,n) + 1 = 1 for all n.
s = -1: 1^n - lucasV(1,1,n) + 1 = 0,1,3,4,3,1,0,... (repeating with a period
of 6) for n=0,1,2,...
s = 0: 2^n - lucasV(2,2,n) + 1, norm of "Gaussian Mersenne".
s = 1: 3^n - lucasV(3,3,n) + 1, norm of "Eisenstein Mersenne".
s = 2: 4^n - lucasV(4,4,n) + 1 = (2^n-1)^2, square of Mersenne.

These few forms have already been quite extensively investigated, but (as far
as I know) all the other s values are virgin territory. A first example from
this new landscape:-

s = -4: M+[-4,-4,n] = (-2)^n - lucasV(-2,-2,n) + 1,
is prime for the following values of n:-
2,3,7,13,19,43,61,151,257,751,859,1453,3767,3889,8171,15959,61961
The last of these is large enough for Chris Caldwell's database, and was
found using PFGW for a PRP search, followed by the following "-tc"
certification:-

Primality testing (-4+2)^61961-lucasV(-4+2,-4+2,61961)+1 [N-1/N+1,
Brillhart-Lehmer-Selfridge]
Calling N-1 BLS with factored part 34.53% and helper 0.02% (103.61% proof)
(-4+2)^61961-lucasV(-4+2,-4+2,61961)+1 is prime!

A couple more "M+" examples:-
M+[15,n] = (15+2)^15971 - lucasV(15+2,15+2,15971)+1 is prime (19652 digits)
M+[-10^6,1459] = (-10^6+2)^1459 - lucasV(-10^6+2,-10^6+2,1459) + 1 is prime
(8752 digits)

----------

Where do these series come from? Let's reverse the process by which they were
arrived at, looking at just the "M+" form to simplify the notation.

The lucasV function has the completely equivalent definition:-
lucasV(P,Q,n) = ((P + sqrt(P^2-4*Q))/2)^n + ((P - sqrt(P^2-4*Q))/2)^n

So M+[s,n] = (s+2)^n - ((s+2+sqrt(s^2-4))/2)^n - ((s+2-sqrt(s^2-4))/2)^n + 1
= {((s+2+sqrt(s^2-4))/2)^n - 1} * {((s+2-sqrt(s^2-4))/2)^n - 1}

Let s^2-4 = m*t^2, where m is *square-free*.
Then the last rhs above is just the norm of the following integer in the ring
Z[sqrt(m)] :-
I[s,n] = ((s+2+sqrt(s^2-4))/2)^n - 1 = (u[s]+1)^n - 1,
where u[s] = (s+sqrt(s^2-4))/2 = (s/2 + sqrt(m)*t/2) is a *positive unit* of
the ring, i.e. has norm +1:-
{(s+sqrt(s^2-4))/2} * {(s-sqrt(s^2-4))/2} = +1

Note that the value of m is only a function of |s|, but that the unit u[s]
itself depends on the sign of s as well.

For 0 <= s <= 20, we easily find:-
s m u[s]
0 -1 0 + sqrt(-1)
1 -3 1/2 + sqrt(-3)/2
2 0 [analysis doesn't apply]
3 5 3/2 + sqrt(5)/2
4 3 2 + sqrt(3)
5 21 5/2 + sqrt(21)/2
6 2 3 + sqrt(2)*2
7 5 7/2 + sqrt(5)*3/2
8 15 4 + sqrt(15)
9 77 9/2 + sqrt(77)/2
10 6 5 + 2*sqrt(6)
11 13 11/2 + sqrt(13)*3/2
12 35 6 + sqrt(35)
13 165 13/2 + sqrt(165)/2
14 3 7 + 4*sqrt(3)
15 221 15/2 + sqrt(221)/2
16 7 8 + 3*sqrt(7)
17 285 17/2 + sqrt(285)/2
18 5 9 + 4*sqrt(5)
19 357 19/2 + sqrt(357)/2
20 11 10 + 3*sqrt(11)

Not all the Z[sqrt(m)] are simple (Class number 1). For example:-
s=8 => s^2-4=60 => m=15 (and t=2), and the field Q[sqrt(15)] has Class number
2; and
s=65 => s^2-4=4221 => m=469 (and t=3), and Q[sqrt(469)] has Class number 3.

To summarize, M+[s,n] is norm((u+1)^n-1), where u is a unit of the ring
Z[sqrt(m)] with norm(u)=+1.

It is straightforward to verify in the same way that
F+[s,n] is norm((u+1)^n+1), where u is a unit of the ring Z[sqrt(m)] with
norm(u)=+1.
M-[s,n] is norm((u+1)^n-1), where u is a unit of the ring Z[sqrt(m)] with
norm(u)=-1.
F-[s,n] is norm((u+1)^n+1), where u is a unit of the ring Z[sqrt(m)] with
norm(u)=-1.

For "F+", the m and u[s] values are as for "M+", and again certain of the
smaller s values are special:-
s = -3: (-1)^n + lucasV(-1,-1,n) + 1 = -L(n) for n odd, = 2-L(n) for n even.
s = -2: 0^n + lucasV(0,0,n) + 1 = 1 for all n.
s = -1: 1^n + lucasV(1,1,n) + 1 = 4,3,1,0,1,3,4,... (repeating with a period
of 6) for n=0,1,2,...
s = 0: 2^n + lucasV(2,2,n) + 1, = (2^(n/2)+1)^2 for n=0 mod 8, =
(2^(n/2)-1)^2 for n = 4 mod 8, else is divisible by 5.
s = 1: 3^n + lucasV(3,3,n) + 1, norm of "Eisenstein Fermat" (see
http://groups.yahoo.com/group/primenumbers/message/4607)
s = 2: 4^n + lucasV(4,4,n) + 1 = (2^n+1)^2, square of Fermat.

F+[s,n] gives BLS-provable primes for the same s values as M+[s,n]. Here is
an "F+" series example:-
F+[29,512] = (29+2)^512 + lucasV(29+2,29+2,512) + 1 is prime (764 digits)

The values of m and u[s] for M-and F- are also straightforward to compute
(but different from the M+/F+ values).

For "M-", the following s values are special:-
s = -2: (-2)^n - lucasV(0,-2,n) + 1 = -(2^n-1) for n odd, = (2^n-1)^2 for n
even.
s = -1: (-1)^n - lucasV(1,-1,n) + 1 = -L(n) for n odd, = 2-L(n) for n even.
s = 0: 0^n - lucasV(2,0,n) + 1, = -(2^n-1), negative of Mersenne number.
s = 1: 1^n - lucasV(3,1,n) + 1, = -L(n)^2 for n odd, = -5*Fib(n)^2 for n
even,
where Fib(n) is the usual Fibonacci series 0,1,2,3,5,..

And for "F-" these s same values give:-
s = -2: (-2)^n + lucasV(0,-2,n) + 1 = -(2^n-1) for n odd, = (2^n+1)^2 for n
even.
s = -1: (-1)^n + lucasV(1,-1,n) + 1 = L(n) for n odd, = L(n)+2 for n even.
s = 0: 0^n + lucasV(2,0,n) + 1, = 2^n+1, Fermat number.
s = 1: 1^n + lucasV(3,1,n) + 1, = 5*Fib(n)^2 for n odd, = L(n)^2 for n even.

(Note how the Lucas numbers L(n) turn up in all 4 of the forms!)

M-[s,n] and F-[s,n] give BLS-provable primes for s=-8,-4,-2,+4; for all other
s values they are only PRP. For M-[20,16111], for example, which has 21319
digits, PFGW with "-tc" says:-

Primality testing (20)^16111-lucasV(2+20,20,16111)+1 [N-1/N+1,
Brillhart-Lehmer-Selfridge]
Calling N+1 BLS with factored part 22.78% and helper 0.06% (68.40% proof)
(20)^16111-lucasV(2+20,20,16111)+1 is Fermat and Lucas PRP!

I am submitting about 20 PRPs from these "M-" and "F-" series to Henri
Lifchitz's database, among them:-
M-[10^20,557] = (10^20)^557 - lucasV(10^20+2,10^20,557) + 1 (11123 digits)
So far, no "F-" primes have reached his entry criterion of 10000 digits, the
largest found to date being:-
F-[56,512] = (56)^512 + lucasV(56+2,56,512) + 1 (900 digits)

The "M+" forms are well suited to "prime hunters". Rather like the so-called
generalized Fermat forms, one can choose what size of base to work with:
large bases give you bigger primes more quickly but with a reduced prime
probability for given n. There's no reason why the world's biggest prime
should not be of "M+" type - it just depends on attracting machine horsepower
comparable to that at GIMPS's disposal. (Or maybe George would like to offer
his clients a *choice* of prime form?)

It would make an ageing amateur number theorist very happy if his name were
to become associated with these forms.

Mike Oakes