John D. Cook

The imbalance conjecture is now a theorem. James Alexander Schreib and Yousof Yavari posted a proof last week. What does the conjecture theorem say? Start with a graphG with no edge between two nodes of the same degree. Then for every edge, calculate the absolute value of the difference of the degree of each end. [...]The post The imbalance theorem first appeared on John D. Cook.

Suppose you have a planet in an elliptical orbit around a star. The math is identical for any light object orbiting a heavy object, such as a moon or satellite orbiting a planet, but we'll call the heavy object a star and the light object a planet. The center of the star is not quite [...]The post Mean distance to the sun first appeared on John D. Cook.

The first post in the recent series of posts on Hadamard matrices describes a way of constructing new Hadamard matrices from two other Hadamard matrices by taking their Kronecker product. Starting with a Hadamard matrixH0 and a Hadamard matrix G, you can construct a sequence of Hadamard matrices by Hn+1 = G Hn for [...]The post Proportion of 1s in a Hadamard matrix first appeared on John D. Cook.

Error correcting codes are most simply described in terms of the errors they can certainly correct. For example, the Hadamard code used for the Mariner 9 probe to Mars encoded each 6-bit pixel to a 32-bit codeword in such a way that the original pixel could be recovered if no more than 7 bits were [...]The post Probability of correcting errors first appeared on John D. Cook.

Hadamard matrices are in the news following the recent announcement of a newly discovered Hadamard matrix. I've written three posts on Hadamard matrices recently, one as a sort of introduction and two on applications: the error correcting code used in the Mariner 9 probe and constructing sphere packings. A Hadamard matrix is an orthogonal matrix [...]The post Compressing a Hadamard matrix first appeared on John D. Cook.

Yesterday Levent Alpoge announced that he and his colleagues had discovered a new Hadamard matrix using Claude AI. That motivated a post I wrote this morning on how to construct Hadamard matrices. I mentioned in that post that these matrices arise in applications. This evening I gave an example, describing how NASA used a Hadamard [...]The post Hadamard Codes and Sphere Packing first appeared on John D. Cook.

NASA set Mariner 9 to photograph Mars in 1971. The images had to be encoded for transmission using an error-correcting code, otherwise they would be significantly corrupted when they were received on Earth. The images were encoded for transmission using a code based on Hadamard matrices, specifically a (32, 6, 16) Hadamard code. This means [...]The post How NASA's Mariner 9 probe encoded images first appeared on John D. Cook.

A Hadamard matrix is an orthogonal matrix whose entries are all either 1 or - 1. For example is a Hadamard matrix of order 2. True to Stigler's law of eponymy, James Joseph Sylvester investigated Hadamard matrices before Jacques Hadamard. Sylvester saw how to bootstrap the example above into more examples. If H is a [...]The post Constructing Hadamard matrices first appeared on John D. Cook.

Suppose you've never worked at the command line and you're reading a book about the bash shell. You read that !$ is a shortcut to refer to the last word of the previous command. That little fact will almost certainly not stick in your head for a couple reasons. First, you probably see no need [...]The post Cryptic but consistent first appeared on John D. Cook.

I was reading a blog post on boat names because it was on Hacker News this morning. The post contained a link to a data set on dog names in NYC and I poked around the data a little. The top names were not at all what I expected, but then again this is limited [...]The post Dogs and fat tails first appeared on John D. Cook.

Suppose you were able to go back in time, to an era before computers, and give someone contemporary cryptography. Encryption methods that are essentially unbreakable now would certainly be unbreakable then. But there's a catch: not only do attackers not have computers, neither do users. Manual cryptography If you told someone about RSA encryption, for [...]The post Manually unbreakable cryptography first appeared on John D. Cook.

The following extraordinary paragraph comes from Knuth's TAOCP Volume 4A, right before the last set of exercises. Many of the exercises below ask a modern reader to find and/or to correct errors in the literature of bygone days. The point is not to gloat over how smart we are in the 21st century; the point [...]The post Learning from historical mistakes first appeared on John D. Cook.

In science and engineering classes, you might describe a system using Newton's laws and end up with a differential equation. You then solve the differential equation, analytically or numerically, to see how the solutions behave. You might also do the opposite, especially in a mathematics class: look at what differential equation a set of functions [...]The post Inverse differential equations first appeared on John D. Cook.

I was reading a book on the history of the discovery of the structure of DNA [1] and was surprised by a few passing references to Bessel functions. According to Claude, When X-rays are diffracted by a helical structure, the resulting diffraction pattern breaks into a series of horizontal layer lines." Cochran, Crick, and Vand [...]The post DNA and Bessel functions first appeared on John D. Cook.

At the end of my post on how not to calculate cosine I said that the first step in calculating cosine, particularly cosine of a large number, would be to do range reduction. This post will present a simple range reduction method by Cody and Waite that is adequate for moderately large arguments. If you [...]The post A simple range reduction method first appeared on John D. Cook.

I have a program that shares files between my laptop and my phone. It works well, except for apostrophes. When I type an apostrophe ' on my laptop, it becomes aTM on my phone. And when I type 's on my phone, it becomes on my laptop. Apparently the phone turns the apostrophe (U+0027) [...]The post Corrupted apostrophes first appeared on John D. Cook.

Calculus professors with no experience in numerical computing will tell students that computers calculate trig functions with power series. They don't. I worked on the implementation of trig functions in hardware, and I can assure you we didn't just use power series. Power series are an excellent way to calculate functions near the center of [...]The post How not to calculate cosine first appeared on John D. Cook.

In a footnote to the previous post, I said that Python's math library can calculate the logarithm of extremely large numbers but not the cosine. This post will expand on that comment. In this post I'll use n = 200! as my example rather than 1000! because this value of N is larger than the [...]The post cos(200!) first appeared on John D. Cook.

The previous post pointed out that the following code such as the following unexpectedly works. >>> from math import log, factorial >>> log(factorial(1000)) 5912.128178488163 If you don't find this unexpected, note that if you replace math.log with numpy.log the code will fail [1]. Functions like natural logarithm operate on real numbers. Real numbers are represented [...]The post Calculating log(1000!) first appeared on John D. Cook.

Last week I wrote a post on hiding cryptographic keys in decks of cards. I wrote some code for that post that shouldn't work, but before fixing I noticed that it in fact did work. The code computes logarithms for integers larger than the largest representable float. For example, the largest float is on the [...]The post The code that didn't break first appeared on John D. Cook.

A few days ago I wrote a post on counting rooted trees. That post looked at the sequence c(n) which counts the number of rooted trees with n nodes. Here one node is distinguished as the root, but the nodes below the root are not distinguished from each other; all that matters is how the [...]The post Enumerating trees and circles first appeared on John D. Cook.

After writing the previous post about metallic ratios, I thought about the analogy to alchemy and the attempt to make precious metals out of base metals. When can you make one metallic ratio out of another? Can you make the golden ratio out of the lead ratio? Before we can make gold out of lead, [...]The post Mathematical alchemy first appeared on John D. Cook.

The golden ratio is the first and best known of the metallic ratios. I've written about the silver ratio a few times, most recently here. And I've mentioned the bronze ratio a couple times. The metallic ratios after bronze don't have standard names. The nth metallic ratio M(n) is the number whose continued fraction representation [...]The post Ratio of metallic ratios first appeared on John D. Cook.

Yesterday I wrote that a lot of the special functions that pop up in mathematical physics are solutions to second order linear differential equations with polynomial coefficients. More generally, holonomic functions are defined to be those functions that are the solutions to linear differential equations, of any order, with polynomial coefficients. Most special functions are [...]The post Holonomic functions first appeared on John D. Cook.

In this post I mentioned two series which I denotedt(n) andc(n). The former is the number of unlabeled rooted trees withn nodes. The latter is the cumulative sum of the former, i.e. The sequencec(n) is also the number of constraints on an n-step Runge-Kutta method; that's how I became interested in it. Now thet(n) sequence [...]The post Estimating a cumulative sum first appeared on John D. Cook.

Second order linear differential equations with polynomial coefficients form their own area of study. This seems like a narrow class of equations, but it's very important in applications. This class of equations seems like a mathematically natural topic, but why is it so important in applications? I did a PhD in differential equations without ever [...]The post Why polynomial coefficients? first appeared on John D. Cook.

Combinatorial problems can be interesting for their own sake, but they are more interesting when there is a connection to a problem outside combinatorics, and the more unexpected the connection the better. Counting the number of unlabeled rooted trees [1] with n nodes is a pure mathematics problem. Designing numerical methods for solving differential equations [...]The post Counting rooted trees first appeared on John D. Cook.

The textbook version of the Runge-Kutta method for solving differential equations has 4 stages and has 4th order error. For lower order versions of RK the number of stages s also matches the order of the error p. But in order to achieve error on the order ofp >= 5, you need more than p [...]The post Runge-Kutta order versus stages first appeared on John D. Cook.

I was digging into the Runge-Kutta method for solving differential equations and a line from [1] piqued my curiosity. These calculations, which are not reproduced in Kutta's paper (they are however in Huen (1900)), are very tedious. The calculations are a set of eight constraints that the parameters of a fourth-order Runge-Kutta method must satisfy. [...]The post Solving the RK4 design equations first appeared on John D. Cook.

A couple years ago I wrote about how to compute the inverse of factorial. I used that code in writing the previous post because the post required solving the equation log2(n!) >= b given b. That is, given a number of bits b, find the smallest value of nsuch that n! >= 2b. What the [...]The post Inverse factorial improved first appeared on John D. Cook.

The previous post looked at the idea of storing a cryptographic key in the order of a deck of cards. A deck of 52 cards can store 225 bits of data because log2(52!) = 225. Here x isx rounded down to the nearest integer. If we want to store bigger keys, we're going to need [...]The post Cryptographic Keys and Decks of Cards first appeared on John D. Cook.

The latest issue of Paged Out! has an article by Stephen Hewitt An off-line backup of your cryptographic key using playing cards." The idea is to use a deck of 52 to store a 128-bit cryptographic key. To erase the key, shuffle the deck. Hewitt gives his algorithm for embedding a key, one that can [...]The post Hiding data in permutations first appeared on John D. Cook.

My post from yesterday on permutation roots ends with a Mathematica code for finding the probability that a permutation of n elements has a kth root. This is done by finding the coefficient of xn in the generating function I wanted to say more about this, and look at implementing the same code in SymPy. [...]The post Counting permutations with roots first appeared on John D. Cook.

It's well known that you can convert the base 16 (hex) representation of an integer to the base 2 (binary) representation by simply converting each digit from hex to binary. For example, CAFEhex = 1100 1010 1111 1110two I imagine it's less well known that you can do the same thing with floating point numbers. [...]The post Printing floating point numbers in binary first appeared on John D. Cook.

Let be a permutation on n elements. If there is a permutation such that applying twice has the same effect on the list of elements as applying once, we say = ^2 and is a square root of . If we let our n elements be the integers 0 [...]The post Permutation roots first appeared on John D. Cook.

The function expq(x) is defined by taking the power series for exp(x) and keeping only the terms whose index is a multiple of q. For example, exp2(x) keeps only the even-numbered terms in the exponential power series and so equals cosh(x). In general, The first sum uses Iverson's bracket notation: a Boolean expression in brackets [...]The post exp_q first appeared on John D. Cook.

I was working with a wide spreadsheet from a client the other day and I had to convert between Excel column labels and column numbers. I had never paid attention to how Excel labels columns and implicitly thought it was base 26 using letters rather than digits. But then I realized that's not right. Excel [...]The post Excel column numbering first appeared on John D. Cook.

This post takes a more abstract view of the previous post. That post looked at the concrete question of whether a number ever has the same sine in radians as in degrees. The relation between radians and degrees is irrelevant except that /180 is an irrational number. Suppose and are two positive numbers [...]The post An almost periodic function first appeared on John D. Cook.

Ordinarily the sine of x radians and the sine of x degrees are very different numbers. Having your calculator in radian mode when it should be in degree mode, or vice versa, results in a major error. But sometimes it doesn't matter. A trivial example is when x = 0. A more interesting example is [...]The post When sine of x degrees equals sine of x radians first appeared on John D. Cook.

I recently had a project in which I had to reverse engineer a data analysis. There was some ambiguity regarding which of several possibilities someone chose for several of the variables, something analogous to the following example. Suppose you have three numbers with uncertain values with a known, or at least purported, sum. The first [...]The post Forensic accounting in Python first appeared on John D. Cook.

A couple days ago, Levent Alpoge, a mathematician working at Anthropic, discovered a counterexample to the Jacobian conjecture using Claude Fable 5. I was curious whether most mathematicians were trying to prove or disprove the conjecture, so I asked Claude. Before a counterexample to the Jacobian conjecture was found, did most mathematicians believe it was [...]The post Locally everywhere does not imply everywhere first appeared on John D. Cook.

The volume of a sphere of radius r is V = 4r^3 / 3 and the surface area is A = 4r^2 and so the ratio of volume to area is V / A = r / 3. Surprisingly, the same ratio holds for all regular solids ifr is the radius of the largest sphere [...]The post Volume to Area ratio for Regular Solids first appeared on John D. Cook.

I've written several posts about using Claude or ChatGPT to generate Prolog or Lean code to solve a chess puzzle. I didn't think Grok would be up to the task, though I didn't try it. I've heard good things about Grok 4.5, so I gave it a shot. It did great. Here's the problem, a [...]The post Solving a chess puzzle with Grok 4.5 first appeared on John D. Cook.

Suppose you want to search for a list of words. If you're using grep, you can add the -f flag provide a file of regular expressions, and you can add the -F to tell it that the regular expressions are in fact just words. I did something like this a couple days ago when searching [...]The post Fitting a regular expression to a list of words first appeared on John D. Cook.

Squares, high and low Let p be an odd prime number. Then half the numbers from 1 through p - 1 are squares and half are not. That is, for half of numbers 1 k < p, the equation x^2 = k mod p has a solution. The traditional name for these numbers is [...]The post Sum of low squares first appeared on John D. Cook.

Quick follow up to the previous two posts on ICD-10 codes and HCPCS codes. This post uses Python's squarify library to create treemaps visualizing how many codes begin with each letter. Here's the treemap for HCPCS codes. And here's the treemap for ICD-10 codes. The sizes of the squares are proportional to the number of [...]The post Visualizing Medical Code Hierarchy first appeared on John D. Cook.

Since I revisited my old post on ICD code matching, I thought I'd revisit by post on HCPCS codes too. HCPCS stands for Healthcare Common Procedure Coding System, and is pronounced hick picks." When most people say HCPCS, they technically mean HCPCS Level II, and that's what I mean here. The format of a HCPCS [...]The post Regular expressions for HCPCS codes first appeared on John D. Cook.

Seven years ago I wrote a post about regular expressions to match diagnosis codes. I wanted to revisit that post looking at speed and error rates. Regular expressions usually do not exactly match what you're looking for and nothing else. They have error false positives and false negatives. But they also have advantages, and context [...]The post Regular expression speed and error rates first appeared on John D. Cook.

I've been thinking about ICD-10 codes; they come up a lot in my work. The ICD-10-CM standard is divided into 21 chapters, which generally correspond to the first letter of a code. However, a chapter may contain blocks beginning with more than one letter, and codes starting with a single letter, namely D, can span [...]The post ICD-10 chapters and code letters first appeared on John D. Cook.

A few days ago I wrote a post entitled Does additional data always reduce posterior variance?. In a nutshell, the answer is no, not always. That led the previous post which looked at posterior means for three Bayesian models, showing how the posterior mean is a weighted average of the prior mean and the mean [...]The post Posterior variance first appeared on John D. Cook.