4 ms·

Thanks! However, I'm not quite convinced. I ran the given Scheme implementation with k=10000 and it correctly reported all the numbers at http://www.kobepharma-

Thanks! However, I'm not quite convinced. I ran the given Scheme implementation with k=10000 and it correctly reported all the numbers at http://www.kobepharma-u.ac.jp/~math/notes/note02.html http://www.kobepharma-u.ac.jp/~math/notes/note02.html less than 4294967087 as composite. (4294967087 is the largest random number Racket can give.) However, running it with k=50 gave a random set of them each time. So perhaps the probability data I gave was not right.

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 ago
  The 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