2 ms·
Hi - thanks for the response. This will be brief, as I'm very short of time. > Yes the full program for left-truncatable primes happens to be fine ... Yes -
by ColinWright 9y ago
Hi - thanks for the response. This will be brief, as I'm very short of time.
> Yes the full program for left-truncatable primes happens to be fine ...
Yes - although it's a little lucky, but easy enough to run an extra confirmation.
> how did you generate your list of false positives?
Nothing clever - I literally wrote a slow trial division program, then ran through all integers up to some limit - 10^8 I think - and when the "is_prime" routine said it was prime I called the slow version to see if it was right. Machines are fast.
> the function in the post has 2690 of these false positives less than 10^12. ... Of these 2690 false positives, these have the 5 largest smallest prime factors:
> 681719179681: 5743 8527 13921
> 802204143001: 5981 8971 14951
> 747734199031: 6791 8731 12611
> 949631589089: 6917 10193 13469
> 251994268081: 354961 709921
That's cool.
> And indeed the `small_primes` used by the test needs to be extended up to the prime 6917, if we want to get no false positives at least for numbers up to 10^12.
We can augment this with the Perrin Psuedo-Prime test, but Miller-Rabin is still probably the best way to go to do it "properly". If I re-wrote the material on the Perrin tests[0] I'd probably use M-R.
So we're pulling in the same direction, although making different trade-offs. And it's fun to play and see what happens.
[0] http://www.solipsys.co.uk/new/FindingPerrinPseudoPrimes_Part1.html?HN_20171023 http://www.solipsys.co.uk/new/FindingPerrinPseudoPrimes_Part...