Category Archives: primes

Quickly recognizing primes less than 1000: memorizing exceptional composites

Posted on October 15, 2018 by

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

Posted on October 11, 2018 by

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

Posted on September 16, 2018 by

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

Primality testing: recap

Posted on September 10, 2018 by

Whew, this is developing into one of the longest post series I’ve ever written (with quite a few tangents and detours along the way). I thought it would be worth taking a step back for a minute to recap what … Continue reading →

Posted in computation, number theory, primes | Tagged , , , | 2 Comments

The Fermat primality test

Posted on August 3, 2018 by

After several long tangents writing about orthogons and the chromatic number of the plane, I’m finally getting back to writing about primality testing. All along in this series, my ultimate goal has been to present some general primality testing algorithms … Continue reading →

Posted in computation, number theory, primes | Tagged , , | 5 Comments

Fast and slow machines

Posted on January 27, 2018 by

In my previous post, I presented three hypothetical machines which take a positive integer as input and give us something else as output: a factorization machine gives us the complete prime factorization of ; a factor machine gives us one … Continue reading →

Posted in computation, number theory, primes | Tagged , , , , , , , , , , | 1 Comment

New Mersenne prime

Posted on January 11, 2018 by

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 , , , ,