4 ms·

The primality test uses Fermat's Little Theorem, but I thought it was not 100% perfect. (Or perhaps it is for left-truncatable primes?) I didn't know about the

by epx 9y ago

The primality test uses Fermat's Little Theorem, but I thought it was not 100% perfect. (Or perhaps it is for left-truncatable primes?) I didn't know about the third parameter in pow(), either. Quite interesting.

CarolineW 9y ago
It's good enough for smallish primes, especially when you use multiple bases. There aren't many Carmichael numbers, and the early ones all have a small factor. So the test is certainly adequate in this range.
ColinWright 9y ago
It's not perfect, but it's fast, easy to code, and the first false positive for this version is a long way out. Early Carmichael numbers have small factors, and although I'm only testing against prime bases up to 19, I'm not sure where the first false positive is. But it's a long way further out than the numbers we're dealing with here. I should go looking ...
- svat 9y ago
  Here are the first ten false positives for the is_prime function in the post, along with their factors: 252601: 41 61 101 294409: 37 73 109 399001: 31 61 211 410041: 41 73 137 488881: 37 73 181 512461: 31 61 271 1152271: 43 127 211 1193221: 31 61 631 1461241: 37 73 541 1857241: 31 181 331
  - ColinWright 9y ago
    Thanks for that. As it happens it's not a problem because the first 30 all have even digits and so can't be a final segment of a left-truncatable prime, except 7519441, and 441 isn't prime. I could write a more comprehensive test - didn't seem worth it for this case, but it's an interesting exercise. It's easy to extend this test so the list of primes used goes as far as the smallest factor in each of these factorisations, say, 109. Then these would all be correctly identified as composite. It would also be easy to combine it with Pollard Rho or PPP tests, to extend the range before we need to do something more serious. Anyway, here are the first 30 with factorisations 252601 : 41 61 101 294409 : 37 73 109 399001 : 31 61 211 410041 : 41 73 137 488881 : 37 73 181 512461 : 31 61 271 1152271 : 43 127 211 1193221 : 31 61 631 1461241 : 37 73 541 1615681 : 23 199 353 1857241 : 31 181 331 1909001 : 41 101 461 2508013 : 53 79 599 3057601 : 43 211 337 3581761 : 29 113 1093 3828001 : 101 151 251 4335241 : 53 157 521 5049001 : 31 271 601 5148001 : 41 241 521 5444489 : 29 197 953 5481451 : 31 151 1171 5968873 : 43 127 1093 6189121 : 61 241 421 6733693 : 109 163 379 6868261 : 43 211 757 7519441 : 41 241 761 8134561 : 37 109 2017 8927101 : 31 37 43 181 9439201 : 61 271 571 9494101 : 23 61 67 101
    - svat 9y ago
      Yes the full program for left-truncatable primes happens to be fine (no false positives in its output for any length, as I verified with a different primality test). The primality test in the post (Fermat's test) is interesting to analyze though. BTW how did you generate your list of false positives? I didn't mention it earlier, but as a shortcut I used the list from https://oeis.org/A001567 https://oeis.org/A001567 (the base-2 pseudoprimes up to 10^12), and found that the function in the post has 2690 of these false positives less than 10^12. I wrote out only the first 10 above (after piping through `factor`). 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 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. And even if we went that far, we'd encounter the next false positive soon after, at 1025414056801 (factors 7561 8101 16741) and then (if we included primes up to 7561) at 1196508858409 (factors 8059 11833 12547). (See https://oeis.org/A083876 https://oeis.org/A083876) I think compared to the Fermat test used in the post, the Miller-Rabin test is almost as easy to write (only a few lines longer), and it comes with stronger guarantees. Not only is it a test used in the real world (using it with just a few random bases gives a high degree of confidence), but it also comes with guarantees when a deterministic set of primes (like your idea) is used: for example with the first 13 primes (2 to 41), the first false positive is over 3.3 × 10^24 (https://en.wikipedia.org/w/index.php?title=Miller%E2%80%93Rabin_primality_test&oldid=797113714#Deterministic_variants https://en.wikipedia.org/w/index.php?title=Miller%E2%80%93Ra...). See also https://miller-rabin.appspot.com/ https://miller-rabin.appspot.com/
      - svat 9y ago
        For what it's worth, here is an implementation of the Miller-Rabin primality test that first tries the smallest 13 primes and then tries some random bases: def is_probable_prime(n, num_random_trials=5): """ An implementation of the Miller-Rabin primality test. If this function returns False, then n is definitely not prime. If this function returns True, then n is probably prime: the probability of n being composite is less than 1/4^(num_random_trials), and nonzero only if n >= 3317044064679887385961981 > 3.3*10^24 > 1.3*2^81 (by https://arxiv.org/abs/1509.00864). """ assert n == abs(int(n)), 'Need a nonnegative integer, got %s' % n if n < 2: return False if n % 2 == 0: return n == 2 (s, d) = (0, n - 1) while d % 2 == 0: (s, d) = (s + 1, d // 2) assert n - 1 == (2**s) * d and d % 2 == 1 small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41] for i in range(len(small_primes) + num_random_trials): a = small_primes[i] if i < len(small_primes) else random.randrange(small_primes[-1], n - 1) if a >= n: break if not (pow(a, d, n) == 1 or any(pow(a, 2**j * d, n) == n - 1 for j in range(s))): return False return True
waynecochran 9y ago
3rd parameter is the modulus : power(a,b,c) = a^b % c
dmurray 9y ago
It can provide false positives but not false negatives, so it's good enough because the goal was only to prove that the number on the pencil is the largest left-truncatable prime. If it provided a positive result the author would have checked that one separately or added more primes to the check.
- deleted 9y ago
  [deleted]

by epx 9y ago

CarolineW 9y ago

It's good enough for smallish primes, especially when you use multiple bases. There aren't many Carmichael numbers, and the early ones all have a small factor. So the test is certainly adequate in this range.

ColinWright 9y ago

It's not perfect, but it's fast, easy to code, and the first false positive for this version is a long way out. Early Carmichael numbers have small factors, and although I'm only testing against prime bases up to 19, I'm not sure where the first false positive is. But it's a long way further out than the numbers we're dealing with here. I should go looking ...

svat 9y ago
Here are the first ten false positives for the is_prime function in the post, along with their factors: 252601: 41 61 101 294409: 37 73 109 399001: 31 61 211 410041: 41 73 137 488881: 37 73 181 512461: 31 61 271 1152271: 43 127 211 1193221: 31 61 631 1461241: 37 73 541 1857241: 31 181 331
- ColinWright 9y ago
  Thanks for that. As it happens it's not a problem because the first 30 all have even digits and so can't be a final segment of a left-truncatable prime, except 7519441, and 441 isn't prime. I could write a more comprehensive test - didn't seem worth it for this case, but it's an interesting exercise. It's easy to extend this test so the list of primes used goes as far as the smallest factor in each of these factorisations, say, 109. Then these would all be correctly identified as composite. It would also be easy to combine it with Pollard Rho or PPP tests, to extend the range before we need to do something more serious. Anyway, here are the first 30 with factorisations 252601 : 41 61 101 294409 : 37 73 109 399001 : 31 61 211 410041 : 41 73 137 488881 : 37 73 181 512461 : 31 61 271 1152271 : 43 127 211 1193221 : 31 61 631 1461241 : 37 73 541 1615681 : 23 199 353 1857241 : 31 181 331 1909001 : 41 101 461 2508013 : 53 79 599 3057601 : 43 211 337 3581761 : 29 113 1093 3828001 : 101 151 251 4335241 : 53 157 521 5049001 : 31 271 601 5148001 : 41 241 521 5444489 : 29 197 953 5481451 : 31 151 1171 5968873 : 43 127 1093 6189121 : 61 241 421 6733693 : 109 163 379 6868261 : 43 211 757 7519441 : 41 241 761 8134561 : 37 109 2017 8927101 : 31 37 43 181 9439201 : 61 271 571 9494101 : 23 61 67 101
  - svat 9y ago
    Yes the full program for left-truncatable primes happens to be fine (no false positives in its output for any length, as I verified with a different primality test). The primality test in the post (Fermat's test) is interesting to analyze though. BTW how did you generate your list of false positives? I didn't mention it earlier, but as a shortcut I used the list from https://oeis.org/A001567 https://oeis.org/A001567 (the base-2 pseudoprimes up to 10^12), and found that the function in the post has 2690 of these false positives less than 10^12. I wrote out only the first 10 above (after piping through `factor`). 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 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. And even if we went that far, we'd encounter the next false positive soon after, at 1025414056801 (factors 7561 8101 16741) and then (if we included primes up to 7561) at 1196508858409 (factors 8059 11833 12547). (See https://oeis.org/A083876 https://oeis.org/A083876) I think compared to the Fermat test used in the post, the Miller-Rabin test is almost as easy to write (only a few lines longer), and it comes with stronger guarantees. Not only is it a test used in the real world (using it with just a few random bases gives a high degree of confidence), but it also comes with guarantees when a deterministic set of primes (like your idea) is used: for example with the first 13 primes (2 to 41), the first false positive is over 3.3 × 10^24 (https://en.wikipedia.org/w/index.php?title=Miller%E2%80%93Rabin_primality_test&oldid=797113714#Deterministic_variants https://en.wikipedia.org/w/index.php?title=Miller%E2%80%93Ra...). See also https://miller-rabin.appspot.com/ https://miller-rabin.appspot.com/
    - svat 9y ago
      For what it's worth, here is an implementation of the Miller-Rabin primality test that first tries the smallest 13 primes and then tries some random bases: def is_probable_prime(n, num_random_trials=5): """ An implementation of the Miller-Rabin primality test. If this function returns False, then n is definitely not prime. If this function returns True, then n is probably prime: the probability of n being composite is less than 1/4^(num_random_trials), and nonzero only if n >= 3317044064679887385961981 > 3.3*10^24 > 1.3*2^81 (by https://arxiv.org/abs/1509.00864). """ assert n == abs(int(n)), 'Need a nonnegative integer, got %s' % n if n < 2: return False if n % 2 == 0: return n == 2 (s, d) = (0, n - 1) while d % 2 == 0: (s, d) = (s + 1, d // 2) assert n - 1 == (2**s) * d and d % 2 == 1 small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41] for i in range(len(small_primes) + num_random_trials): a = small_primes[i] if i < len(small_primes) else random.randrange(small_primes[-1], n - 1) if a >= n: break if not (pow(a, d, n) == 1 or any(pow(a, 2**j * d, n) == n - 1 for j in range(s))): return False return True

waynecochran 9y ago

3rd parameter is the modulus : power(a,b,c) = a^b % c

dmurray 9y ago

It can provide false positives but not false negatives, so it's good enough because the goal was only to prove that the number on the pencil is the largest left-truncatable prime. If it provided a positive result the author would have checked that one separately or added more primes to the check.

deleted 9y ago
[deleted]