Tag Archives: algorithm

Post without words #23

Posted on October 29, 2018 by Brent

Posted in pattern, pictures, posts without words | Tagged algorithm, Calkin-Wilf, Euclidean, tree | 11 Comments

Quickly recognizing primes less than 1000: memorizing exceptional composites

Posted on October 15, 2018 by Brent

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 1000, algorithm, composite, exception, memorize, prime, recognize, test | Comments Off

Quickly recognizing primes less than 1000: divisibility tests

Posted on October 11, 2018 by Brent

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 1000, algorithm, prime, recognize, test | 3 Comments

Modular exponentiation by repeated squaring

Posted on August 18, 2018 by Brent

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 algorithm, exponentiation, logarithmic, modular, primality, repeated, squaring, test | 4 Comments

More on sums of palindromes

Posted on April 11, 2018 by Brent

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 algorithm, news, palindromes, sum | 7 Comments

Every positive integer is a sum of three palindromes

Posted on April 9, 2018 by Brent

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 algorithm, constructive, news, palindromes, proof, sum | 14 Comments

Efficiently listing orthobraces

Posted on March 26, 2018 by Brent

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 algorithm, Almagir, bracelet, enumeration, Husnine, Karim, list, listing, orthobraces, orthogonal, orthogons, Sawada | 1 Comment

Haskell code to naively list orthobraces

Posted on March 21, 2018 by Brent

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 algorithm, bracelet, enumeration, Haskell, list, listing, orthobraces, orthogonal, orthogons | 1 Comment

Fast and slow machines

Posted on January 27, 2018 by Brent

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 algorithm, division, efficiency, exponential, factor, factorization, machine, polynomial, primality, testing, trial | 1 Comment

From primitive roots to Euclid’s orchard

Posted on July 26, 2017 by Brent

Commenter Snowball pointed out the similarity between Euclid’s Orchard… …and this picture of primitive roots I made a year ago: At first I didn’t see the connection, but Snowball was absolutely right. Once I understood it, I made this little … Continue reading →

Posted in pattern, pictures, posts without words | Tagged algorithm, Euclidean, gcd, orchard, primitive, roots | Comments Off