Tag Archives: algorithm

Post without words #23

Image | Posted on by | Tagged , , , | 11 Comments

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

Modular exponentiation by repeated squaring

In my last post we saw how to quickly compute powers of the form by repeatedly squaring: ; then ; and so on. This is much more efficient than computing powers by repeated multiplication: for example, we need only three … Continue reading

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

More on sums of palindromes

In my previous post I reported on a recent proof that every positive integer can be written as the sum of three palindromes. The first thing to report in this follow-up post is that Lewis Baxter sent me the Python … Continue reading

Posted in arithmetic, computation, links | Tagged , , , | 7 Comments

Every positive integer is a sum of three palindromes

I recently learned from John Cook about a new paper by Javier Cilleruelo, Florian Luca, and Lewis Baxter proving that every positive integer can be written as a sum of three palindromes. A palindrome is a number that is the … Continue reading

Posted in arithmetic, computation, links | Tagged , , , , , | 14 Comments

Efficiently listing orthobraces

In my last couple posts, we talked about a simple yet inefficient method for listing all orthobraces of a particular size. So how do we generate them efficiently? It turns out that it can be done: in 2011, Karim, Sawada, … Continue reading

Posted in combinatorics, computation | Tagged , , , , , , , , , , , | 1 Comment