Tag Archives: algorithm

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

Haskell code to naively list orthobraces

Let’s see some simple Haskell code to generate orthobraces, by generating all sequences and throwing away ones we’ve already generated. First, some library imports we’ll need. > import Data.List > import qualified Data.Set as S Here’s a function to generate … Continue reading

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