Prime numbers and primality testing Yahoo Group 4 new forms of primes =============================================== mikeoakes2@aol.com Message 1 of 4 Feb 8, 2002 ----------------------------------------------- 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 =============================================== djbroadhurst Message 2 of 4 Feb 8, 2002 ----------------------------------------------- Wow! It's going to take me some time to digest these Oakes numbers. Thanks Mike! =============================================== mikeoakes2@aol.com Message 3 of 4 Feb 11, 2002 ----------------------------------------------- In a message dated 08/02/2002 18:45:42 GMT Standard Time, d.broadhurst@... writes: > Wow! It's going to take me some time to digest > these Oakes numbers. Thanks, David - that's high praise indeed, from the Lucasmeister himself :-) As a response to your offlist challenge to find **non-M+** primes big enough for Chris Caldwell's database - and how could one resist such a challenge! - here is the first "F+" (28673 digits):- Primality testing (10000202+2)^(4096)+lucasV(10000202+2,10000202+2,4096)+1 [N-1/N+1, Brillhart-Lehmer-Selfridge] Calling N-1 BLS with factored part 50.09% and helper 0.01% (150.28% proof) (10000202+2)^(4096)+lucasV(10000202+2,10000202+2,4096)+1 is prime! (2443.140000 seconds) An M- should be equally easy to find. Any takers for the F- challenge?? Mike =============================================== djbroadhurst Message 4 of 4 Feb 11, 2002 ----------------------------------------------- Off list, I have been telling Mike what he knows already: that his classification has lovely math behind it, scoping much of what we know and love into his basket and adding value thereto. Personally, I was disappointed that the (largely) non-BLS forms M- and F- do not have loopholes (as far as I can see) for Brent-Dubner-Keller-Steward-deWater-Irvine-Leyland-Walker-Broadhurst style work on N^2-1 with ECM, in the hope of a final WL or KP coup. But that's just the way the cookie crumbles. Mike's classification is so solid that no other quadratic-number-field extension of Mers/Ferm would make as much sense as what he so clearly explained. Please write _2_ articles Mike, and then these forms can become Caldwell-commentable. David =============================================== Cached by Georg Fischer at Nov 14 2019 12:47 with clean_yahoo.pl V1.4