John D. Cook

I was reading a recent blog post by Evelyn Lamb where she mentioned in passing that 314159 is a prime number and that made me curious how many such primes there are. Let’s look at numbers formed from the digits of π to see which ones are prime. Obviously 3 and 31 are prime. 314 […]

The prime number theorem says that π(x), the number of primes less than or equal to x, is asymptotically x / log x. So it’s easy to estimate the number of primes below some number N. But what if we want to estimate the number of prime powers less than N? This is a question […]

Simple groups are to groups as prime numbers are to numbers.A simple group has no non-trivial normal subgroups, just as a prime number has no non-trivial factors. Classification Finite simple groups have been classified into five broad categories: Cyclic groups of prime order Alternating groups Classical groups Exceptional groups of Lie type Sporadic groups. Three […]

Suppose you want to multiply two 2 × 2 matrices together. How many multiplication operations does it take? Apparently 8, and yet in 1969 Volker Strassen discovered that he could do it with 7 multiplications. Upper and lower bounds The obvious way to multiply two n × n matrices takes n³ operations: each entry in […]

I was looking back over an old blog post and noticed some code in the comments that I had overlooked. Tom Pollard gives the following code for drawing Spirograph-like curves. import matplotlib.pyplot as plt from numpy import pi, exp, real, imag, linspace def spiro(t, r1, r2, r3): """ Create Spirograph curves made by one circle of […]

I use Windows, Mac, and Linux, each for different reasons. When I run Windows, I like to have a shell that works sorta like bash, but doesn’t run in a subsystem. That is, I like to have the utility programs and command editing features that I’m used to from bash on Mac or Linux, but […]

If you don’t get any outside input into your life, you’re literally an idiot, someone in your own little world. But if you get too much outside input, you become a bland cliche. I’ve written about this a couple times, and ran across a new post this morning from someone expressing a similar idea. I […]

Pareto’s 80-20 rule says that 80% of your results often come from 20% of your effort. Maybe 80% of your profit comes from 20% of your customers, or maybe 80% of the bugs in your software are removed in the first 20% of the time you spend debugging. The rule is named after Italian economist […]

Archaic measurement systems were much more complicated than the systems we use today. Even modern imperial units, while more complicated than metric (SI) units, are simple compared to say medieval English units. Why didn’t someone think of something like the metric system a thousand years ago? I imagine they did. I don’t think they were […]

My first math classes used the terms one to one and onto to describe functions. These Germanic names have largely been replaced with their French equivalents injective and surjective. Monic and epic are the category theory analogs of injective and surjective respectively. This post will define these terms and show how they play out in several contexts. In […]

A recent video by Quanta Magazine says that the eigenvalues of random matrices and the zeros of the Riemann zeta function appear to have the same distribution. I assume by “random matrices” the video is referring specifically to Gaussian orthogonal ensembles. [Update: See the first comment below for more details. You need some assumptions on […]

It’s much easier to multiply numbers together than to factor them apart. That’s the basis of RSA encryption. In particular, the RSA encryption scheme rests on the assumption that given two large primes p and q, one can quickly find the product pq but it is much harder to recover the factors p and q. For the size numbers you’ll […]

I was playing around with some geographic features of Mathematica this morning and ran across an interesting example in the documentation for the PolyhedronProjection function given here. Here’s what you get when you project a map of the earth onto each of the five regular (Platonic) solids. How the images were made At first I right-clicked […]

A few days ago I blogged about the elliptic curve secp256k1 and its use in Bitcoin. This curve has a sibling, secp256r1. Note the “r” in the penultimate position rather than a “k”. Both are defined in SEC 2: Recommended Elliptic Curve Domain Parameters. Both are elliptic curves over a field zp where p is a […]

I wrote a new blog post this morning, but for some reason it posted with an earlier date and so it doesn’t show up at the top of the blog. Here it is: Addition carries and Markov chains

Many consider Ada Lovelace to be the first programmer. An article from a couple days ago asks what did her program do? In a sense, nothing. It was written for a computer that did not exist, so it was never executed. But it was written to compute the 8th Bernoulli number. The article’s author created […]

It’s been known for some time that carbon can form structures with positive curvature (fullerenes) and structures with zero curvature (graphene). Recently researches discovered a form of carbon with negative curvature (schwartzites). News story here. More curvature posts: Squircles Curvature of an egg Curvature and automatic differentiation

Descriptions of cryptography algorithms often start with something like “Let p be a large prime” or maybe more specifically “Let p be a 256 bit prime.” How hard is it to find large prime numbers? Let’s look at the question in base b, so we can address binary and base 10 at the same time. The prime number […]

Schnorr groups, named after Claus Schnorr, are multiplicative subgroups of a finite field. They are designed for cryptographic application, namely as a setting for hard discrete logarithm problems. The application of Schnorr groups to Schnorr signatures was patented, but the patent ran out in 2008. There has been a proposal to include Schnorr signatures in Bitcoin, […]

Bitcoin uses the Elliptic Curve Digital Signature Algorithm (ECDSA) based on elliptic curve cryptography. The particular elliptic curve is known as secp256k1, which is the curve y² = x³ + 7 over a finite field to be described shortly. Addition on elliptic curves in the plane is defined geometrically in terms of where lines intercept […]

Currying is a simple but useful idea. (It’s named after logician Haskell Curry [1] and has nothing to do with spicy cuisine.) If you have a function of two variables, you can think of it as a function of one variable that returns a function of one variable. So starting with a function f(x, y), […]

There’s no perfectly satisfying way to map the globe on to a flat surface. Every projection has its advantages and disadvantages. The Mercator projection, for example, is much maligned for the way it distorts area, but it has the property that lines of constant bearing correspond to straight lines on the map. Obviously this is […]

The original butterfly effect The butterfly effect is the semi-serious claim that a butterfly flapping its wings can cause a tornado half way around the world. It’s a poetic way of saying that some systems show sensitive dependence on initial conditions, that the slightest change now can make an enormous difference later. Often this comes up […]

In The Big Bang Theory, Sheldon Cooper explains an extension of the game Rock, Paper, Scissors by introducing two more possibilities, Lizard, and Spock. Sam Kass and Karen Bryla invented the game before it became widely known via the television show. The diagram below summarizes the rules: Alternative rules Imagine yourself in the position of Sam […]

Given two objects A and B, Hom(A, B) is simply the set of functions between A and B. From this humble start, things get more interesting quickly. Hom sets To make the above definition precise, we need to say what kinds of objects and what kinds of functions we’re talking about. That is, we specify […]

How do you operate a data-driven application before you have any data? This is known as the cold start problem. We faced this problem all the time when I designed clinical trials at MD Anderson Cancer Center. We uses Bayesian methods to design adaptive clinical trial designs, such as clinical trials for determining chemotherapy dose […]

Today’s exponential sum looks like three octagons, slightly rotated with respect to each other. I thought that the graph was tracing out one octagon, then another, then another. But that’s not what it’s doing at all. You can see for yourself by going to the exponential sum page and clicking the animate link. The curve […]

Today’s the first day of a new month, which means the exponential sum of the day will be simpler than usual. The exponential sum of the day plots the partial sums of where m, d, and y are the month, day, and (two-digit) year. The n/d term is simply n, and integer, when d = 1 and so it has no effect […]

Here’s how to construct what John Horton Conway calls his “subprime fib” sequence. Seed the sequence with any two positive integers. Then at each step, sum the last two elements of the sequence. If the result is prime, append it to the sequence. Otherwise divide it by its smallest prime factor and append that. If […]

Symmetric Gaussian matrices The previous post looked at the distribution of eigenvalues for very general random matrices. In this post we will look at the eigenvalues of matrices with more structure. Fill an n by n matrix A with values drawn from a standard normal distribution and let M be the average of A and its transpose, i.e. M = ½(A […]

Suppose you create a large matrix M by filling its components with random values. If M has size n by n, then we require the probability distribution for each entry to have mean 0 and variance 1/n. Then the Girko-Ginibri circular law says that the eigenvalues of M are approximately uniformly distributed in the unit disk in the complex plane. […]

Here are the most popular posts on my site according to the number of points given on Hacker News. The most important skill in software development (742) Four hours of concentration (329) Why programmers are not paid in proportion to productivity (278) Golden powers are nearly integers (277) Why isn’t everything normally distributed? (250) Kalman […]

Names for extremely large numbers are kinda pointless. The purpose of a name is to communicate something, and if the meaning of the name is not widely known, the name doesn’t serve that purpose. It’s even counterproductive if two people have incompatible ideas what the word means. It’s much safer to simply use scientific notation […]

Melissa O’Neill has a new post on generating random numbers from a given range. She gives the example of wanting to pick a card from a deck of 52 by first generating a 32-bit random integer, then taking the remainder when dividing by 52. There’s a slight bias because 232 is not a multiple of […]

When mathematicians run out of symbols, they turn to other alphabets. Most math symbols are Latin or Greek letters, but occasionally you’ll run into Russian or Hebrew letters. Sometimes math uses a new font rather than a new alphabet, such as Fraktur. This is common in Lie groups when you want to associate related symbols to […]

I don’t understand homotopy groups of spheres, and it’s OK if you don’t either. Nobody fully understands them. This post is really more about information compression than homotopy. That is, I’ll be looking at ways to summarize what is known without being overly concerned about what the results mean. The task: map two integers to […]

Which has more mobility on an empty chessboard: a rook, a king or a knight? On an ordinary 8 by 8 chessboard, a rook can move to any one of 14 squares, no matter where it starts. A knight and a king both have 8 possible moves from the middle of the board, fewer moves […]

I’ve written before about a knight’s random walk on an ordinary chess board. In this post I’d like to look at the generalization to three dimensions (or more). So what do we mean by 3D chess? For this post, we’ll have a three dimensional lattice of possible positions, of size 8 by 8 by 8. […]

NASA has fueled the development of lots of spinoff technologies: smoke detectors, memory foam, infrared ear thermometers, etc. NASA didn’t pursue these things directly, but they were a useful side effect. Something analogous happens in mathematics. While pursuing one goal, mathematicians spin off tools that are useful for other purposes. Algebraic topology might be the […]

If all you know about a person is that he or she is around 5′ 7″, it’s a toss-up whether this person is male or female. If you know someone is over 6′ tall, they’re probably male. If you hear they are over 7″ tall, they’re almost certainly male. This is a consequence of heights […]

When I was in college, one of the professors seemed to lecture at a sort of quadratic pace, maybe even an exponential pace. He would proceed very slowly at the beginning of the semester, so slowly that you didn’t see how he could possibly cover the course material by the end. But his pace would […]

A friend asked me a question the other day that came out of a graphics application. He needed to trace out an ellipse in such a way that the length of curve traced out each second was constant. For a circle, the problem is simple: (cos(t), sin(t)) will trace out a circle covering a constant […]

The Catalan numbers Cn are closely related to the central binomial coefficients I wrote about recently: In this post I’ll write C(n) rather than Cn because that will be easier to read later on. Catalan numbers come up in all kinds of applications. For example, the number of ways to parenthesize an expression with n terms is the nth Catalan […]

The sum of the squares of consecutive Fibonacci numbers is another Fibonacci number. Specifically we have and so we have the following right triangle. The hypotenuse will always be irrational because the only Fibonacci numbers that are squares are 1 and 144, and 144 is the 12th Fibonacci number.

It’s hard to find bounds on binomial coefficients that are both simple and accurate, but in 1990, E. T. H. Wang upper and lower bounds on the central coefficient that are both, valid for n at least 4. Here are a few numerical results to give an idea of the accuracy of the bounds on a […]

The blog post that kicked off the recent series of posts looked at how far apart xy and yx are for quaternions. There I used the Euclidean distance, i.e. || xy – yx ||. This time I’ll look at the angle between xy and yx, and I’ll make some analogous graphs for octonions. For vectors x and y in three dimensions, the dot […]

An earlier post included code for multiplying quaternions, octonions, and sedenions. The code was a little clunky, so I refactor it here. def conj(x): xstar = -x xstar[0] *= -1 return xstar def CayleyDickson(x, y): n = len(x) if n == 1: return x*y m = n // 2 a, b = x[:m], x[m:] c, […]

Quaternion multiplication is associative but not commutative. An earlier post looked at the average size of the commutator xy – yx as a measure of how far quaternion multiplication is from being commutative. This post looks at an analogous question for octonions. Octonion mulitplication is neither commutative nor associative. So in this post we look at the […]

The previous post discussed octonions. This post will implement octonion multiplication in Python, and then sedenion multiplication. Cayley-Dickson construction There’s a way to bootstrap quaternion multiplication into octonion multiplication, so we’ll reuse the quaternion multiplication code from an earlier post. It’s called the Cayley-Dickson construction. For more on this construction , see John Baez’s treatise […]

A group is a set with a binary operation that closed associative, has an identity, and has inverses. This post will look at each of these properties and what happens if you modify or remove it. Magmas Closed means that applying the binary operation to any two elements of the set yields another elements of […]