Tag Archives: prime

Quickly recognizing primes less than 1000: memorizing exceptional composites

In my previous post I wrote about a procedure for testing the primality of any number less than : Test for divisibility by all primes up to , and also . (In practice I test for 2 and 5 first, … Continue reading

Posted in arithmetic, computation, primes | Tagged , , , , , , , | Leave a comment

Quickly recognizing primes less than 1000: divisibility tests

I took a little hiatus from writing here since I attended the International Conference on Functional Programming, and since then have been catching up on teaching stuff and writing a bit on my other blog. I gave a talk at … Continue reading

Posted in arithmetic, computation, primes | Tagged , , , , | 2 Comments

Quickly recognizing primes less than 100

Recently, Mark Dominus wrote about trying to memorize all the prime numbers under . This is a cool idea, but it made me start thinking about alternative: instead of memorizing primes, could we memorize a procedure for determining whether a … Continue reading

Posted in arithmetic, computation, primes | Tagged , , , | 18 Comments

New Mersenne prime

With impeccable timing, just in the middle of my series about primality testing, a new Mersenne prime has been announced, a little under two years after the previous one. In particular, it has been shown that is prime; this is … Continue reading

Posted in number theory, primes | Tagged , , , ,

Four formats for Fermat: correction!

In my previous post I explained three variants on Fermat’s Little Theorem, as well as a fourth, slightly more general variant, which it turns out is often called Euler’s Totient Theorem. Here’s what I said: If and is any integer, … Continue reading

Posted in number theory, primes | Tagged , , , , , , | 4 Comments

The route puzzle

While poking around some old files I came across this puzzle: (Click for a larger version.) I didn’t make it, and I have no idea where I got it from (do you know?). But in any case, wherever it comes … Continue reading

Posted in arithmetic, challenges, number theory, proof, puzzles | Tagged , , , , , , | 7 Comments

M74207281 is prime!

I’m a bit late to the party, but the Great Internet Mersenne Prime Search has recently announced a newly verified prime number, , with a whopping 22,338,618 decimal digits! This is now the largest known prime number (though of course … Continue reading

Posted in computation | Tagged , , , ,