Thread: Other Primes
View Single Post
Old 2021-10-18, 23:44   #282
Batalov's Avatar
Mar 2008

9,857 Posts

Originally Posted by paulunderwood View Post
Congrats tp Ryan and Serge for the record Near-rep Digit / Palindrome prime 101888529 - 10944264 - 1
Yet another custom sieve for such hybrid beasts:
quick sketch:

We are searching for NRP(K,n) = 102n+1-K*10n-1. K can only be 1,2,4,5,7,8. (K=3 has algebraic factorization, which is not needed ...because the whole expression is divisible by 3 when 3|K).

Step 1. Let x=10^n, then NRP(K,n) = 10x2-Kx-1 . I solve this quadratic equation just like in school but x is some Mod(x,p) then sieve by p

Step 2. If quadratic equation has solution (nearly half the time; if it doesn't , nothing to sieve out), then --

Step 3. Solve 10^n = x1 and 10^n = x2. This is called znlog() and these values will periodically repeat with period znorder().

Step 4. Sieve out and repeat for 7<= p <= 10^11 or 10^12.

Step 5: remove special cases for p={7,11,13} (this actually removes a huge fraction of candidates with K=2, that's why it is the "thinnest" K)

The trick is to code steps 1, 2 and 3, and to know how.

Step 6. Test. (we test all six number forms in order of size. The fact that K=1 produced the first hit is accidental. With K=1, the number looks a bit more elegant.)
Batalov is offline   Reply With Quote