Around about exactly this time a year ago, I bought the frivolous domain name three.onefouronefivenine.com, to celebrate π Day and to indulge my curiosity about a marvellous algorithm to compute π’s digits.
This year, I’ve been thinking about prime numbers, and my hosting provider has run another sale on domain names. So, I’ve bought isthisprime.com. You can probably guess what I’ve made it do.
That’s right: if you go to, for example, isthisprime.com/57, it’ll tell you that 57 is not a prime number. And if you go to isthisprime.com/239539, it’ll tell you that 239539 is a prime number. What’s more, if you get really adventurous and go to isthisprime.com/19999999999999900019, it’ll tell you that 19999999999999900019 is probably a prime number.
It does all this using the deterministic Miller test for primality on smaller numbers, and then the probabilistic Miller-Rabin test for bigger ones. As someone who’s previously only ever written a slightly-optimised Sieve of Eratosthenes routine before, this is basically magic: by looking at residues of polynomials modulo a few bases, you can be certain ± ε that a number is prime or composite in an astonishingly short time.
Normally when I do this sort of clever maths thing, I relish the opportunity to explain how it all works. I can’t do that this time. I copied the pseudocode for the primality tests from Wikipedia and did a little bit of thinking about where I’d need arbitrary precision arithmetic (thanks to BigInteger.js), but I really don’t understand how it works. I know that it has something to do with equalities in modular arithmetic, but that’s about it. What I do know is that I haven’t got anywhere near to an optimal implementation of the tests – there are all sorts of facts you can prove about what bases you need to use in order to avoid unnecessary calculations – but I’m happy with being able to get an answer for a 10 digit number fairly quickly.
So that’s isthisprime.com. I bought it thinking it’d be a one-job site, but I’ve also had another idea bumping around in my head: a game where you’re shown a succession of numbers and have to say whether they’re prime or not prime.
A possibly apocryphal story has it that Alexandre Grothendieck, asked to pick a prime number to work as an example for something he was explaining, picked 57. Ironically, Marcus du Sautoy once told me that the Grothendieck prime was 59, which is a brain fart of the second degree.
Enter The “Is this prime?” game. The aim of the game is to sort as many numbers as possible into “prime” or “not prime” in under a minute. It’s very simple, but infuriatingly difficult. Having played quite a few rounds of it today, I’m beginning to empathise with Alexandre Grothendieck – 57 really does look a lot like a prime number. Though my personal Grothendieck prime seems to be 91: every time it comes up, some part of my brain shortcuts the bit that just circulated a memo about it not being prime, and makes me hit the Yes button before the rest of my little grey cells have had a chance to protest.
Sometimes, however, I just fail because of a complete and sudden blowout of my maths inner tube:
It was a hit on Twitter last night, and thanks to input from a few people I made a few improvements to my original design: I added keyboard shortcuts to make the ‘y’ and ‘n’ keys click the corresponding buttons in order to save valuable mouse-moving time, and I added an option to set a cap on the numbers shown, for teachers who want to use the game in classes.
I’ve been going back to it whenever I’ve had a couple of spare minutes today. Maybe it’ll have some long-term educational value – did you know that 111 is composite? Did you know for sure? Play the game.
Check if a number is prime: isthisprime.com
Play the “Is this prime?” game: isthisprime.com/game
Nice! It works for Belphegor’s Prime: 1000000000000066600000000000001
You mentioned 111. It has always amazed me that it is not prime despite the digit sum clearly indicating otherwise.
You can get definitive results for quite a bit larger results by using deterministic variants. There are very efficient sets for 64-bit inputs, and a recent result works to ~ 2^82. Using very dated web tools, but I’ve had http://sti15.com/nt/primality.cgi running for quite a while. It will do various probable prime tests (BPSW, plus a couple Frobenius types), BPSW+ which does a BPSW test, an extra random-base Miller-Rabin test, followed by a quick proof attempt for “easy” numbers in the 20-60 digit range, and proofs (even shows the certificate). It’s all server-side code though.