In the previous post we offered a partial answer to proving a Proth Number is prime
The result would be a probable prime to base 2.
.
74665 is not a Proth Number. Is 74665 a strong Euler-Jacobi Pseudoprime?
Of the 37 initial terms in OEIS sequence A047713 we found the following:
One Pseudoprime passed the filter – 74665
Three were Incalculable as p-1 not divisible by 4
Five were marked ‘not applicable’ as we can only apply our filter when (2/p)=1
One in twenty-nine passed the filter which means we eliminated 96% of the Pseudoprimes using this extra filter.
If you count the 8 for which our filter could not be used then we still eliminated 3/4 of the Pseudoprimes.
For the conjecture at the top of this page, we would always be dealing with (p-1) divisible by 8 and 2^((p-1)/2) = 1 mod p
So our filter would likely achieve near the 96% we achieved here.
Having amended the previous post, this filter is already incorporated into our prime test.
If reading this post has got you interested in Probable Prime theory then the following resources might offer some further reading: