10
$\begingroup$

I'm working on an OEIS submission that counts the number of n-digit A157711 primes. Working with PrimeQ as my primality determinator, I can generate some 1200 terms. However, it has been pointed out to me that as the terms get larger so does the probability that at least one of the probable primes thus counted may turn out to be composite.

In an effort to put my terms on a more secure mathematical footing I decided to recalculate the initial terms using ProvablePrimeQ instead of PrimeQ. ProvablePrimeQ is one of those old Mathematica functions that was never incorporated into Wolfram proper. It needs PrimalityProving`. I was able to go somewhat further than expected, but at n=142 I ran into what I'm calling a recalcitrant prime. ProvablePrimeQ appeared to be stuck on 10^141+10^131+10^49+1. I don't know if I just needed to wait longer for the primality determination or if Mathematica was in some sort of buggy loop. At any rate, since other length-142 integers were not so encumbered, it was easy to step around the number (using factordb to confirm its proven primality status) and continue with the effort in Mathematica.

Since then, I have run into other recalcitrant provable primes (10^158+10^99+10^42+1, 10^160+10^95+10^56+1, 10^163+10^43+10^35+1, 10^164+10^124+10^84+1, ...) and my idea of getting up to n=200 is on hold because there are too many interruptions to make the process palatable. I welcome insights and/or suggestions.

Update: Recalcitrant Provable Primes 2.0

Stan Wagon has pointed out that some of the ProvablePrimeQ non-responses using the Atkin–Morain primality test (which is the default for integers greater than 10^50) may be proven prime by using the Pratt test (which requires a complete factorization of the integer minus one). Why does ProvablePrimeQ only use one or the other? As I mentioned earlier, the approach is somewhat old. Using only the Pratt test already gives non-responses for n in the 70s (on my computer) while Atkin-Morain takes it all the way to n=142.

Fine. I'll build a procedure that, when ProvablePrimeQ fails to give a result after 20 seconds, it will try ProvablePrimeQ with "Small Prime" -> 10^300 (which forces the Pratt test) for 2 minutes. If that fails, it will print the integer for subsequent, external verification. This printout then represents Recalcitrant Provable Primes version 2.0.

s={}; Do[q = 10^(n-1) + 1; p = 0; 
Do[qx = q + 10^x; 
Do[qy = qx + 10^y; If[TimeConstrained[ProvablePrimeQ[qy], 20, TimeConstrained[ProvablePrimeQ[qy, "SmallPrime" -> 10^300], 120, 
Print["10^",n-1,"+10^",x,"+10^",y,"+1"]]], p++], {y, x-1, 1, -1}], {x, n-2, 
2, -1}]; AppendTo[s,p], {n, 140, 200}]
  • 10^163+10^43+10^35+1
  • 10^166+10^138+10^51+1
  • 10^166+10^79+10^26+1
  • 10^167+10^90+10^14+1
  • 10^169+10^71+10^25+1
  • 10^172+10^61+10^2+1
  • 10^174+10^137+10^22+1
  • 10^174+10^110+10^63+1
  • 10^177+10^35+10^23+1
  • 10^178+10^106+10^34+1
  • 10^178+10^97+10^28+1
  • 10^180+10^154+10^27+1
  • 10^181+10^127+10^45+1
  • 10^181+10^99+10^43+1
  • 10^183+10^49+10^43+1
  • 10^184+10^164+10^58+1
  • 10^185+10^153+10^33+1
  • 10^185+10^66+10^50+1
  • 10^187+10^106+10^42+1
  • 10^188+10^87+10^70+1
  • 10^190+10^137+10^24+1
  • 10^190+10^95+10^14+1
  • 10^190+10^88+10^13+1
  • 10^190+10^53+10^18+1
  • 10^191+10^188+10^8+1
  • 10^191+10^174+10^84+1
  • 10^191+10^60+10^8+1
  • 10^192+10^45+10^26+1
  • 10^192+10^28+10^8+1
  • 10^193+10^177+10^109+1
  • 10^194+10^93+10^36+1
  • 10^195+10^183+10^39+1
  • 10^195+10^60+10^40+1
  • 10^196+10^165+10^28+1
  • 10^197+10^178+10^72+1
  • 10^197+10^151+10^75+1
  • 10^197+10^151+10^67+1
  • 10^197+10^128+10^62+1
  • 10^197+10^51+10^37+1
  • 10^197+10^30+10^20+1
  • 10^198+10^65+10^42+1
  • 10^198+10^62+10^42+1

Thus 42 RPPs in the range of n=140 to n=200. This took about 2 hours on my computer. Another 15 minutes to manually (copy/paste) these into factordb and verify proven primality. A printout of s matches the probable prime counts derived by using PrimeQ as the primality determinator.

I hadn't realized that ProvablePrimeQ is listed in the Wolfram Function Repository (version 1.0.0: 7 March 2019). It may well be the same code as the PrimalityProving` version (with the exception of upping the "SmallPrime" default value from 10^10 to 10^50) that appears to go back to Mathematica 3.0 (1996). Almost 30 years old! Is it any wonder that the function struggles?

Improve this question
$\endgroup$
1
  • $\begingroup$ Try other online prime testing algorithms. $\endgroup$ Commented Jun 2 at 16:36

1 Answer 1

Reset to default
11
$\begingroup$

I can certify the first one (10^141 etc) by the Pratt certificate method, because n - 1 can be factored by FactorInteger in about a minute. The code for PrattCertificate is in the CNT package from my book "A Course in Computational Number Theory". The factors are {24013402372679486891, 31287081842422526489, 13425039207313011083693, 5517185725625527082792120257170582338864034435760219,599,3,2^42, 5^42}. I have not tried the others. But if you can factor n - 1, that should do it.

Stan Wagon

Edit: Now trying the others. The first two work the same way. I will give the prime factors of n-1 tomorrow or later.

Edit: Here are the 5 cases:

{141, 131, 49, 0}, {158, 99, 42, 0}, {160, 95, 56, 0}, {163, 43, 35,0}, {164, 124, 84, 0}

Here are the factorizations of n-1 for the first 3 cases. This means the Pratt certificate method will certify these 3.

{{2, 49}, {3, 1}, {5, 49}, {7, 1}, {13, 1}, {23, 1}, {37, 1}, {311, 1}, {12391, 1}, {38185671398471, 1}, {22322935996007137397005352291, 1}, {131035600074555313722845023822092335167, 1}},

{{2, 42}, {3, 1}, {5, 42}, {599, 1}, {24013402372679486891, 1}, {31287081842422526489, 1}, {13425039207313011083693, 1}, {5517185725625527082792120257170582338864034435760219, 1}}

{{2, 56}, {3, 1}, {5, 56}, {661, 1}, {1185407921, 1}, {8190513577, 1}, {154511803838727007, 1}, {3361527462378006776196985813099908677404271190697905101664987
4313, 1}}};

Ah: I had a typo. Fixed. The last case is easy because of the large power of 10.

{2, 84}, {3, 1}, {5, 84} , {7, 1}, {13, 1}, {31, 1}, {37, 1}, {61, 1}, {211, 1}, {241, 1}, {2161, 1}, {9901, 1}, {2906161, 1}, {4188901, 1}, {39526741, 1}, {99990001, 1}, {100009999999899989999000000010001, 1}

So this takes care of four of the five. Given the factorization, getting the Pratt certificate is routine. Here it is for the last example: The key number is 41, indicating that 41 is a primitive root for the number. The method is recursive but for any prime under 10^16 (where PrimeQ is proved reliable) no certificate is needed. So the certificate is pretty short, with just one recursive step.

{100000000000000000000000000000000000000010000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000001, 41, {2, 3, 5, 7, 13, 31, 37, 61, 211, 241,2161, 9901, 2906161, 4188901, 39526741, 99990001,

{100009999999899989999000000010001, 23, {2, 3, 5, 11, 17, 73, 101, 137, 952439, 1050041, 5882353}}}}

So really, the only question that remains is to factor n-1, where n is the {163, 43, 35,0} case.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.