John D. Cook

Here's a puzzle by Martin Garnder [1]. Can a queen, king, rook, bishop, and knight be placed on a 4^2 board so no piece attacks another? There are two solutions, plus symmetries. Note that in all non-attacking chess puzzles, the colors of the pieces are irrelevant. In the solutions I chose the piece colors to [...]The post A crowded little chess puzzle first appeared on John D. Cook.

The Boolean satisfiability problem is to determine whether there is a way to assign values to variables in a set of Boolean formulas to make the formulas hold [1]. If there is a solution, the next task would be to enumerate the solutions. You can solve the famous eight queens problem, or its generalization ton-queens, [...]The post Formulating eight queens as a SAT problem first appeared on John D. Cook.

There are 92 ways to place eight queens on a chessboard so that no queen is attacking any other. These fall into 12 equivalence classes. The 92 solutions are all rotations and reflections of these 12 basic solutions. If you think about the previous numbers a minute, you might wonder why the total number of [...]The post Special solutions to the eight queens problem first appeared on John D. Cook.

How many bishops can you place on a chessboard so that no bishop is attacking any other bishop? For a standard 8 * 8 chessboard the answer is 14. In general, for an n * n chessboard the answer is 2n - 2. Here's one way to place the maximum number of non-attacking bishops. To [...]The post The non-attacking bishops problem first appeared on John D. Cook.

This morning I wrote about the frequencies of names for popes and kings. This involved sorting strings with Roman numerals since it's common for popes and kings to have Roman numerals after their names. Something that surprised me was that sorting Roman numerals alphabetically roughly sorts them in numerical order, especially for small numbers. It's [...]The post Sorting Roman numerals first appeared on John D. Cook.

After I wrote the code to make the bar graph of papal names for the previous post, I decided to reuse the code to make a similar graph for monarchs of England. Just as there is some complication in counting papal names, there are even more complications in counting names of English monarchs. Who was [...]The post Frequency of names of English monarchs first appeared on John D. Cook.

The new pope chose the name Leo XIV. That made me curious about the distribution of names of popes and so I made the graph below. (I'm Protestant, so wasn't familiar to me.) Looks like Leo is tied with Clement for fourth place, the top three names being John, Benedict, and Gregory. There are a [...]The post Frequency of papal names first appeared on John D. Cook.

The recent post Converting between quaternions and rotation matrices describes an algorithm as a mathematically correct but numerically suboptimal method/" Let's just look at a small piece of that post. The post explains how to find a rotation matrix to describe the same rotation as pre- and post- multiplying by a unit quaternion q, and [...]The post Square root of a small number first appeared on John D. Cook.

Large language models display emergence behaviors: when the parameter count is scaled to a certain value, suddenly the LLM is capable of performing a new task not possible at a smaller size.Some say the abruptness of this change is merely a spurious artifact of how it is measured. Even so, many would like to understand, [...]The post Why do LLMs have emergent properties? first appeared on John D. Cook.

In the previous post I wrote about representing rotations with quaternions. This representation has several advantages, such as making it clear how rotations compose. Rotations are often represented as matrices, and so it's useful to be able to go between the two representations. A unit-length quaternion (q0, q1, q2, q3) represents a rotation by an [...]The post Converting between quaternions and rotation matrices first appeared on John D. Cook.

Every rotation in 3D fixes an axis [1]. This is Euler's rotation theorem from 1775. Another way to state the theorem is that no matter how you rotate a sphere about its center, two points stay fixed. The composition of two rotations is a rotation. So the first rotation fixes some axis, the second rotation [...]The post Composing rotations using quaternions first appeared on John D. Cook.

This is the 5,000th post on this blog. I started blogging in 2008, and Wayne Joubert started contributing posts last year. We've written an average of between five and six posts a week for the last 17 years. I thought about listing some of the most popular posts over the years, but that's not as [...]The post 5,000th post first appeared on John D. Cook.

I recently ran across a simple way to generate random points uniformly distributed on a sphere: Generate random points in a cube until you get one inside the sphere, then push it to the surface of the sphere by normalizing it [1]. In more detail, to generate random points on the unit sphere, generate triples [...]The post A simple way to generate random points on a sphere first appeared on John D. Cook.

I recently ran into Recaman's sequence. N. J. A. Sloane, the founder of the Online Encyclopedia of Integer Sequences calls Recaman's sequence one of his favorites. It's sequence A005132 in the OEIS. This sequence starts at 0 and thenth number in the sequence is the result of moving forward or backwardn steps from the previous [...]The post Recaman's sequence first appeared on John D. Cook.

The last four post have looked at the bifurcation diagram for the logistic map. There was one post on the leftmost region, where there is no branching. Then two posts on the region in the middle where there is period doubling. Then a post about the chaotic region in the end. This post returns the [...]The post Cycle order in period doubling region first appeared on John D. Cook.

The last several posts have been looking at the bifurcation diagram below in slices. The first post looked at the simple part, corresponding to the horizontal axis r running from 0 to 3. The next post looked at the first fork, forr between 3 and 3.4495. The previous post looked at the period doubling region, [...]The post An island of stability in a sea of chaos first appeared on John D. Cook.

The last couple posts have been looking at the logistic bifurcation diagram a little at a time. The first post in the series looked at the details of that part of the diagram that looks like the graph of a function, where there parameterr in the logistic map f(x) =rx(1 -x) varies from o to [...]The post Spacing between branches first appeared on John D. Cook.

The previous post looked at iterations of the logistic map f(x) =rx(1 -x) for 0 r 3. This post will look at the range 3 r 1 + 6. If you're not familiar with the logistic map I'd suggest reading the previous post first then coming back to this one. The [...]The post The first fork first appeared on John D. Cook.

Five years ago I wrote a blog post entitled Logistic bifurcation diagram in detail. Looking back at that post it doesn't seem to be that much in detail," though it does go into more detail than most popular accounts. The logistic map is given by f(x) =rx(1 -x) wherex is a variable between 0 and [...]The post The simple part of the logistic map isn't that simple first appeared on John D. Cook.

It's possible to place n queens on an n * n chess board so that no queen is attacking any other queen, provided n > 3. A queen is able to move any number of squares in any horizontal, vertical, or diagonal direction. Another way to put it is that the queen can move in [...]The post n-queens in 3D first appeared on John D. Cook.

In the latest two posts, we have needed to find the percentage points for a chi square random variable when the parameter , the number of degrees of freedom, is large. In Volume 2 of Knuth's magnum opus TAOCP, he gives a table of percentage points for the chi square distribution for small values of [...]The post Knuth's series for chi squared percentage points first appeared on John D. Cook.

In the previous post I needed to know the tail percentile points for a chi squared distribution with a huge number of degrees of freedom. When the number of degrees of freedom is large, a chi squared random variable has approximately a normal distribution with the same mean and variance, namely mean and [...]The post Chi squared approximations first appeared on John D. Cook.

In the previous post, I did a simulation to illustrate a theorem about the number of steps needed in the Euclidean algorithm. The distribution of the number of steps is asymptotically normal, and fornumbers 0 <a<b<x the mean is asymptotically 12 log(2) log(x) / ^2. What about the variance? The reference cited in the previous [...]The post Variance of variances. All is variance. first appeared on John D. Cook.

The worst case run time for the Euclidean algorithm occurs when you give the algorithm a pair of consecutive Fibonacci numbers. The algorithm takes n steps to compute the greatest common divisor of Fn+1 and Fn+2. Thenth Fibonacci number is the nearest integer to n/5 where = (1 + 5)/2 is the golden ratio. [...]The post Distribution of run times for Euclidean algorithm first appeared on John D. Cook.

The previous post looked at adjoints in the context of linear algebra. This post will look at adjoints in the context of category theory. The adjoint of a linear operator T between inner product spaces V and Wis the linear operatorT* such that for allv inV and allw inW, Tv, wW = v, [...]The post Adjunctions first appeared on John D. Cook.

The transpose of a matrix turns the matrix sideways. Suppose A is an m * n matrix with real number entries. Then the transpose A is ann * m matrix, and the (i,j) element of A is the (j,i) element ofA. Very concrete. The adjoint of a linear operator is a more abstract concept, though [...]The post Transpose and Adjoint first appeared on John D. Cook.

I've heard that barbershop quartets often sing the 7th in a dominant 7th a little flat in order to bring the note closer in tune with the overtone series. This post will quantify that assertion. The overtones of a frequencyf are 2f, 3f, 4f, 5f, etc. The overtone series is a Fourier series. Here's a [...]The post Overtones and Barbershop Quartets first appeared on John D. Cook.

I ran across a video that played around with the equipentatonic scale [1]. Instead of dividing the octave into 12 equal parts, as is most common in Western music, you divide the octave into 5 equal parts. Each note in the equipentatonic scale has a frequency 21/5 times its predecessor. The equipentatonic scale is used [...]The post Equipentatonic scale first appeared on John D. Cook.

I've written about the Coupon Collector Problem and variations several times, most recently here. Brian Beckman left a comment linking to an article he wrote, which in turn links to a paper on the Double Dixie Cup Problem[1]. The idea behind the Coupon Collector Problem is to estimate how long it will take to obtain [...]The post The multiple coupon collector problem first appeared on John D. Cook.

Musician Adam Neely made a video asking What is the fastest music humanly possible? He emphasizes that he means the fastest music possible to hear, not the fastest to perform. The video cites a psychology article [1] from 1894 that found that most people can reliably distinguish an inter-onset interval (time between notes) of 100 [...]The post Morse code and the limits of human perception first appeared on John D. Cook.

Toward the end of last year I wrote several blog posts about calendars. The blog post about the Gregorian calendar began with this paragraph. The time it takes for the earth to orbit the sun is not an integer multiple of the time it takes for the earth to rotate on its axis, nor is [...]The post Running the Gregorian calendar backwards first appeared on John D. Cook.

The Fredholm alternative is so called because it is a theorem by the Swedish mathematician Erik Ivar Fredholm that has two alternative conclusions: either this is true or that is true. This post will state a couple forms of the Fredholm alternative. Mr. Fredholm was interested in the solutions to linear integral equations, but his [...]The post Fredholm Alternative first appeared on John D. Cook.

The previous post on kernels and cokernels mentioned that for a linear operator T:VW, the index ofT is defined as the difference between the dimension of its kernel and the dimension of its cokernel: index T = dim ker T- dim cokerT. The index was first called the Fredholm index, because of it came up [...]The post Fredholm index first appeared on John D. Cook.

The kernel of a linear transformation is the set of vectors mapped to 0. That's a simple idea, and one you'll find in every linear algebra textbook. The cokernel is the dual of the kernel, but it's much less commonly mentioned in textbooks. Sometimes the idea of a cokernel is there, but it's not given [...]The post Kernel and Cokernel first appeared on John D. Cook.

This post will venture further into abstract mathematics than most of my posts. If this isn't what you're looking for, you might try browsing here for more concrete articles. Incidentally, although I'm an applied mathematician, I also appreciate pure math. I imagine most applied mathematicians do as well. But what I do not appreciate is [...]The post Topological Abelian Groups first appeared on John D. Cook.

I was poking around Richard Stanley's site today and found the following problem on his miscellaneous page. Find a positive integer n < 10,000,000 such that the first four digits (in the decimal expansion) of n1,000,000 are all different. The problem should be solved in your head. The solution is not unique, but the solution [...]The post Millionth powers first appeared on John D. Cook.

One day Eric Temple Bell (1883-1960) was looking at the power series for the double exponential function, exp(exp(x)) and noticed a similarity to the power series for exp(x). You can find his account in [1]. He would have calculated the series by hand, but we have the advantage of software like Mathematica. We can get [...]The post Mr. Bell and Bell numbers first appeared on John D. Cook.

In this post we want to count the number of ways to divide a regular polygon [1] into triangles by connecting vertices with straight lines that do not cross. Squares For a square, there are two possibilities: we either connect the NW and SE corners, or we connect the SW and NE corners. Pentagons For [...]The post How many ways can you triangulate a regular polygon? first appeared on John D. Cook.

Last week I wrote about a hypothetical radio station that plays the top 100 songs in some genre, with songs being chosen randomly according to Zipf's law. Thenth most popular song is played with probability proportional to 1/n. This post is a variation on that post looking at text consisting of the the 1,000 most [...]The post 1000 most common words first appeared on John D. Cook.

As longtime readers of this blog have probably noticed, I like to poke around in Unicode occasionally. It's an endless system of rabbit holes to explore. This morning I was looking at the Miscellaneous Mathematical Symbols block. These are mostly obscure symbols, though I'm sure for each symbol that I think is obscure, there is [...]The post Miscellaneous mathematical symbols first appeared on John D. Cook.

If any field of mathematics has been thoroughly combed over, it's Euclidean geometry. But once in a while someone will come up with a new theorem that seems it should have been discovered centuries ago. Here's a theorem conjectured by Paul Erds in 1935 and proved by Louis Mordell later the same year. If from [...]The post Erds-Mordell triangle theorem first appeared on John D. Cook.

Here's a strange integral I ran across recently [1]. It's a little surprising that the integral even exists, and more surprising that its value has a simple expression. Here's a plot of the integrand. The plot doesn't do justice to all the activity on the left end. There are an infinite number of increasingly vertical [...]The post Logarithmic sawtooth first appeared on John D. Cook.

Eight years ago I wrote a blog post on the Leading digits of powers of 2. In that post I said that Benford's law gives remarkably good predictions for the distribution of leading digits of 2n. In this post I'll make that statement stronger. A sequence obeys Benford's law, in base 10, if the proportion [...]The post When Benford's law is exact first appeared on John D. Cook.

The exponential sum of the day page draws a new figure each day by plotting the partial sums of and drawing a line between consecutive terms. Herem,d, andy are the month, day, and last two digits of the year. Today's sum has an unusual number of lines that are parallel to the horizontal and vertical [...]The post Lots of flat sides first appeared on John D. Cook.

Suppose you want to hear the top 100 songs in some music genre, so you listen to a radio station that specializes in that kind of music. How long would it take to hear each of the songs at least once? This is a variation on the coupon collector problem. If a radio station plays [...]The post Top 100 radio first appeared on John D. Cook.

If you see a light moving in the sky, how could you tell whether it's an airplane or a satellite? If it is a satellite, could you tell how high of an orbit it's in? For an object in a circular orbit, v^2 = /r wherer is the orbit radius and is the standard [...]The post Estimating satellite altitude from apparent motion first appeared on John D. Cook.

The Korteweg-De Vries (KdV) equation is a nonlinear PDE used to model shallow water waves. The linear counterpart omits the nonlinear term in the middle. This variant is useful in itself, but also for understanding the nonlinear KdV equation. Solitons Solutions to the linear KdV equation spread out over time. The nonlinear term in the [...]The post Linear KdV dispersion first appeared on John D. Cook.

Differential equations, especially nonlinear differential equations, rarely have a closed-form solution, but sometimes it happens. As I wrote about a year ago It is unusual for a nonlinear PDE to have a closed-form solution, but it is not unheard of. There are numerous examples of nonlinear PDEs, equations with important physical applications, that have closed-form [...]The post Closed-form minimal surface solutions first appeared on John D. Cook.

The fundamental solution" to a PDE solves the equation with the right-hand side set to . Intuitively, you can think of the delta function as striking something with a hammer in order to see how it rings. An aside on rigor A novice might be OK with the explanation above. A sophomore might rightly object [...]The post Fundamental solution first appeared on John D. Cook.

The following quote stuck with me when I read it years ago. Looking back I appreciate it even more. Now, when solving differential equations, or indeed solving any problem, it is permissible to use any methods at all, no matter how dubious, provided that once the solution has been found it can be proved to [...]The post No matter how dubious first appeared on John D. Cook.