View Single Post 2020-06-11, 23:46 #1 jshort   "James Short" Mar 2019 Canada B16 Posts Proths of the form 2^{k+1}(2^{k} - 1) + 1, 2k+1 is prime (I guess am sort of answering my own question here......but here goes) Are Proth Primes of the form worthwhile to search for? Fyi - I'm specifically referring to the special case when is itself a prime number and when So here are my reasons for choosing these numbers and restrictions. 1) I noticed that potential composite factors have to satisfy some very strict congruence conditions when is prime (even more strict than prime factors of Mersenne numbers). For example, because the order of 2 over can be shown to be equal to . 2) Sieving out composite Proths of this form is very easy due to the fact that all potential prime factors have the form (unless , but the congruence restrictions on prevent this). Fyi - I personally used the Pollard-rho algorithm with the iterating function to weed out many composites (here is a basic program: rho1(n)= { local(x,y); x=2; y=2^(24p) + 1; while(gcd(y-x,n)==1, x=(x^(24p)+1)%n; y=(y^(24p)+1)%n; y=(y^(24p)+1)%n ); gcd(n,y-x) } ) Note: You don't necessarily need to use the 'extra' multiplier in the exponent of the iterating function, however the exponent of the iterating function definitely needs to be a "highly composite number" multiple of (if not equal to itself) to be the most efficient at weeding out composite Proths of this form . Alternatively, the p-1 test could be used instead to weed out composites. I'm not sure which of the two would be more efficient tbh (if anyone knows the answer to this, that'd be awesome!).  