View Single Post
Old 2022-03-31, 01:57   #10
pvaldivia
 
Mar 2022

1116 Posts
Default Related set of primes

Hello all,

A following is to my knowledge unproven (although I might be ignorant since I’m a recreational type), but also may relate to some of the interest in finding a Lucas-Lehmer-like algorithm for Wagstaff primes that a few people in this forum have described interest in. Consider the numbers (5*4^k + 1)/3, which are the average of two successive numbers of the form (2*4^k+1)/3. Primality of these numbers might be tested using a Lucas-Lehmer-like test – the following appears to work as high as I’ve checked: up to k=1000 have been checked both by standard means as well as the below test, and the results agree for all k except for k=1 (the prime 7, which the below test doesn’t identify as prime).

Specifically, setting the Lucas-Lehmer s(0)=4 and using the standard algorithm with s(n)=(s(n)^2-2) % ((5*4^k + 1)/3), the test indicates primality when s(2k-1)^5-5*s(2k-1)^3+5*s(2k-1)+4 % ((5*4^k + 1)/3) = 0.

As an example: for 6827 (k=6), s(11)=3054. So we compute: (3054^5 -5*(3054^3)+5*3054 + 4) % 6827 = 0 which indicates that 6827 is prime. The use of 2k-1 steps in the first part of the test, as well as the use of the polynomial x^5-x^3+5x were inspired by the paper by H.C. Williams: "A class of primality tests for trinomials which includes the Lucas-Lehmer test" (1982) which developed Lucas-Lehmer tests for numbers of a slightly different form.
pvaldivia is offline   Reply With Quote