2 ms·
I can't tell you what your code is doing wrong, but I promise 1729 should pass the test you described. EDIT: And of course I forgot about non-relatively-prime
by cperciva 15y ago
I can't tell you what your code is doing wrong, but I promise 1729 should pass the test you described.
EDIT: And of course I forgot about non-relatively-prime values. But those are asymptotically sparse; you're seeing a random set of pseudoprimes for k=50 because with that many trials you have a good chance of catching small primes, but for larger Carmichael numbers you'll need a very large number of trials to get good odds.
- jgeralnik 15y agoThe calculations you described are wrong. If a is a multiple of 7 (or 13 or 19), then (a^6)^144 = (0^6)^144 = 0 mod 7. We can confirm this (using python): >>> (7864)%1729 742L