John D. Cook

It's fascinating that there's such a thing as the World Jigsaw Puzzle Championship. The winning team of the two-person thousand-piece puzzle round can assemble a Ravensburger puzzle in less than an hour-that's about 3 -1/2 seconds per piece. It makes you wonder, how could you measure the hardness of a jigsaw puzzle? And what would [...]The post The impossible puzzle first appeared on John D. Cook.

The use of the word moment" in mathematics is related to its use in physics, as in moment arm or moment of inertia. For a non-negative integer n, the nth moment of a function f is the integral of xn f(x) over the function's domain. Uniqueness If two continuous functions f and g have all [...]The post When do moments determine a function? first appeared on John D. Cook.

In the early days of computing hardware (and actually before) mathematicians put a lot of effort into understanding and mitigating the limitations of floating point arithmetic. They would analyze mundane tasks such as adding a list of numbers and think carefully about the best way to carry out such tasks as accurately as possible. Now [...]The post Floating point: Everything old is new again first appeared on John D. Cook.

I've been writing code for the Z3 SMT solver for several months now. Here are my findings. Python is used here as the base language. Python/Z3 feels like a two-layer programming model-declarative code for Z3, imperative code for Python. In this it seems reminiscent of C++/CUDA programming for NVIDIA GPUs-in that case, mixed CPU and [...]The post How hard is constraint programming? first appeared on John D. Cook.

The band-limited expansion of the function f(x) is given by where sinc(x) = sin(x)/x. This is also called the sinc expansion, or the Whittaker cardinal after its discoverer E. T. Whittaker [1]. This is called the band-limited expansion of f because each term in the infinite sum is band-limited, i.e. only has Fourier spectrum within [...]The post Band-limited expansion first appeared on John D. Cook.

Sometimes the future state of a system depends not only on the current state (position, velocity, acceleration, etc.) but also on the previous state. Equations for modeling such systems are known as delay differential equations (DDEs), difference differential equations, retarded equations, etc. In a system with hysteresis, it matters not only where you are but [...]The post Delay differential equations first appeared on John D. Cook.

The way Laplace transforms, as presented in a typical differential equation course, are not very useful. Laplace transformsareuseful, but not as presented. The use of Laplace transforms is presented is as follows: Transform your differential equation into an algebraic equation. Solve the algebraic equation. Invert the transform to obtain your solution. This is correct, but [...]The post Laplace transform inversion theorems first appeared on John D. Cook.

The Mellin transform of a function f is defined as For example, it follows directly from the definition that the gamma function (s) is the Mellin transform of the function e-x. I ran across an exercise that states an impressive-looking theorem about the Mellin transform, namely that where F(s) denotes the Mellin transform of f(x). [...]The post Mellin transform and Riemann zeta first appeared on John D. Cook.

I woke up around 3:00 this morning to some sort of alarm outside. It did not sound like a car alarm; it sounded like a sawtooth wave. The pattern was like a few Morse code O's. Not SOS, or I would have gotten up to see if anyone needed help. Just O's. A sawtooth wave [...]The post Sawtooth waves first appeared on John D. Cook.

A mathematician's reputation rests on the number of bad proofs he has given. (Pioneer work is clumsy.)" - A. S. Besicovitch I'm sure I've written about this quote somewhere, but I can't find where. The quote comes from A Mathematician's Miscellany by J. E. Littlewood, citing Besicovitch. I've more often seen the quote concluding with [...]The post Pioneering work is ugly first appeared on John D. Cook.

Mersenne numbers have the form 2p - 1. A Mersenne prime is a Mersenne number that is also a prime. A new Mersenne prime discovery was announced today: 2p - 1 is prime for p = 136279841. The size of the new Mersenne prime is consistent with what was predicted. For many years now, the [...]The post New Mersenne prime found first appeared on John D. Cook.

Claude Shannon's famous paper A Mathematical Theory of Communication [1] includes an example saying that the channel capacity of a telegraph is log2 W where W is the largest real root of the determinant equation Where in the world did that come from? I'll sketch where the equation above came from, but first let's find [...]The post Channel capacity of a telegraph first appeared on John D. Cook.

I ran across the following theorem in Ross Honsberger's book Mathematical Morsels: Every odd square ends in 1 in base 8, and if you cut off the 1 you have a triangular number. A number is an odd square if and only if it is the square of an odd number, so odd squares have [...]The post Squares, triangles, and octal first appeared on John D. Cook.

Most random number generators are pseudorandom number generators (PRNGs). The distinction may be pedantic or crucial, depending on context. In the context of cryptography, it's critical. For this post, RNG will mean a physical, true random number generator. A PRNG may be suitable for many uses-Monte Carlo simulation, numerical integration, game development, etc.-but not be [...]The post RNG, PRNG, CSPRNG first appeared on John D. Cook.

Let a, b, and c be the sides of a triangle. Let r be the radius of an inscribed circle and R the radius of a circumscribed circle. Finally, let p be the perimeter. Then the previous post said that 2prR = abc. We could rewrite this as 2rR = abc / (a + b [...]The post Triangle circle maximization problem first appeared on John D. Cook.

Let a, b, and c be the sides of a triangle. Let p be perimeter of the triangle. Let r be the radius of the largest circle that can be inscribed in the triangle, and let R be the radius of the circle through the vertices of the triangle. Then all six numbers can be [...]The post Relating six properties of a triangle in one equation first appeared on John D. Cook.

Repetitive text compresses efficiently. Text like the lyrics to Jingle Bells ought to compress more efficiently than ordinary prose, assuming the compression algorithm can exploit the repetition. The idea of the Burrows-Wheeler transform is to permute text in before compressing it. The hope is that the permutation will make the repetition in the text easier [...]The post Preprocessing text to make it more compressible first appeared on John D. Cook.

The original form of radio broadcast was amplitude modulation (AM). With AM radio, the changes in the amplitude of the carrier wave carries the signal you want to broadcast. Frequency modulation (FM) came later. With FM radio, changes to the frequency of the carrier wave carry the signal. I go into the mathematical details of [...]The post Why does FM sound better than AM? first appeared on John D. Cook.

It's interesting to visualize functions of a complex variable, even very simple functions like f(z) = 1/z. The previous post looked at what happens to triangles under the reciprocal map w = 1/z. This post will look at the same map applied to a polar grid, then look at the effect a shift has, replacing [...]The post Shifted reciprocal first appeared on John D. Cook.

The set of functions of the form f(z) = (az + b)/(cz + d) with ad bc are called bilinear transformations or Mobius transformations. These functions have three degrees of freedom-there are four parameters, but multiplying all parameters by a constant defines the same function-and so you can uniquely determine such a function by [...]The post Triangles to Triangles first appeared on John D. Cook.

A golden ellipse is an ellipse whose axes are in golden proportion. That is, the ratio of the major axis length to the minor axis length is the golden ratio = (1 + 5)/2. Draw a golden ellipse and its inscribed and circumscribed circles. In other words draw the largest circle that can fit [...]The post Golden ellipse first appeared on John D. Cook.

Barycentric coordinates are sometimes called area coordinates or areal coordinates in the context of triangle geometry. This is because the barycentric coordinates of a point P inside a triangle ABC correspond to areas of the three triangles PBC, PCA and PAB. (This assumes ABC has unit area. Otherwise divide the area of each of the [...]The post Areal coordinates and ellipse area first appeared on John D. Cook.

Let d(n) be the number of divisors of an integer n. For example, d(12) = 6 because 12 is divisible by 1, 2, 3, 4, 6, and 12. The function d varies erratically as the following plot shows. But if you take the running average of d f(n) = (d(1) + d(2) + d(3) + [...]The post Average number of divisors first appeared on John D. Cook.

Lucas numbers [1] are sometimes called the companions to the Fibonacci numbers. This sequence of numbers satisfies the same recurrence relation as the Fibonacci numbers, Ln+2 = Ln + Ln+1 but with different initial conditions: L0 = 2 and L1 = 1. Lucas numbers are analogous to Fibonacci numbers in many ways, but are also [...]The post Lucas numbers and Lucas pseudoprimes first appeared on John D. Cook.

Given a hash value, can you determine what algorithm produced it? Or what algorithm probably produced it? Obviously if a hash value is 128 bits long, then a 128-bit algorithm produced it. Such a hash value might have been produced by MD5, but not by SHA-1, because the former produces 128-bit hashes and the latter [...]The post Identifying hash algorithms first appeared on John D. Cook.

Random number generators are subtle. Unless the generator is some physical device, random number generators (RNGs) are usually technically pseudorandom number generators (PRNGs), deterministic algorithms designed to mimic randomness. Suppose you have a PRNG that produces the digits 0 through 9. How might you test the output to see whether it (acts like it) is [...]The post Testing random number generators first appeared on John D. Cook.

Why do Venn diagrams almost always show the intersections of three sets and not more? Can Venn diagrams be generalized to show all intersections of more sets? That depends on the rules you give yourself for generalization. If you require that your diagram consist of circles, then three is the limit. As John Venn put [...]The post Limitations on Venn diagrams first appeared on John D. Cook.

I was just talking to a colleague about edit distance because it came up in a project we're working on. Technically, we were discussing Levenshtein distance. It sounds more impressive to say Levenshtein distance, but it's basically how much editing effort it would take to turn one block of text into another. Edit distance is [...]The post Edit distance first appeared on John D. Cook.

The birthday problem is a party trick with serious practical applications. It's well known to people who have studied probability, but the general public is often amazed by it. If you have a group of 23 people, there's a 50-50 chance that at least two people have the same birthday. With a larger group, say [...]The post Birthday problem approximation first appeared on John D. Cook.

I keep running into the function f(z) = (1 - z)/(1 + z)." I wrote this three years ago and it's still true. This function came up implicitly in the previous post. Ramanujan's excellent approximation for the perimeter of an ellipse with semi-axes a and b begins by introducing = (a - b)/(a + [...]The post (1 - z) / (1 + z) first appeared on John D. Cook.

Ramanujan discovered an incredibly accurate approximation for the perimeter of an ellipse. This post will illustrate how accurate the approximation is and push its limits. As with all computations involving ellipses, the error of Ramanujan's approximation increases as eccentricity increases. But the error increases slowly, asymptotically approaching an upper bound that is remarkably small. Let [...]The post Error in Ramanujan's approximation for ellipse perimeter first appeared on John D. Cook.

Someone with no exposure to probability or statistics likely has an intuitive sense that averaging random variables reduces variance, though they wouldn't state it in those terms. They might, for example, agree that the average of several test grades gives a better assessment of a student than a single test grade. But data from a [...]The post The Cauchy distribution's counter-intuitive behavior first appeared on John D. Cook.

I recently ran across a theorem connecting the arithmetic mean, geometric mean, harmonic mean, and the golden ratio. Each of these comes fairly often, and there are elegant connections between them, but I don't recall seeing all four together in one theorem before. Here's the theorem [1]: The arithmetic, geometric, and harmonic means of two [...]The post Arithmetic, Geometry, Harmony, and Gold first appeared on John D. Cook.

I keep running into Edward John Routh (1831-1907). He is best known for the Routh-Hurwitz stability criterion but he pops up occasionally elsewhere. The previous post discussed Routh's mnemonic for moments of inertia and his stretch" theorem. This post will discuss his triangle theorem. Before stating Routh's theorem, we need to say what a cevian [...]The post Ceva, cevians, and Routh's theorem first appeared on John D. Cook.

Edward John Routh (1831-1907) came up with a mnemonic for summarizing many formulas for moment of inertia of a solid rotating about an axis through its center of mass. Routh's mnemonic is I = MS / k where M is the mass of an object, S is the sum of the squares of the semi-axes, [...]The post Moments of inertia mnemonic first appeared on John D. Cook.

I recently came across an upper bound I hadn't seen before [1]. Given a binomial coefficient C(r, k), let n = min(k, r - k) and m = r - n. Then for any > 0, C(n + m, n) (1 + )n + m / n. The proof follows quickly from applying [...]The post Binomial bound first appeared on John D. Cook.

I was skimming through the book Mathematical Reflections [1] recently. He was discussing a set of generalizations [2] of the Star of David theorem from combinatorics. The theorem is so named because if you draw a Star of David by connecting points in Pascal's triangle then each side corresponds to the vertices of a triangle. [...]The post Separable functions in different contexts first appeared on John D. Cook.

Body Roundness Index (BRI) is a proposed replacement for Body Mass Index (BMI) [1]. Some studies have found that BRI is a better measure of obesity and a more effective predictor of some of the things BMI is supposed to predict [2]. BMI is based on body mass and height, and so it cannot distinguish [...]The post Body roundness index first appeared on John D. Cook.

I've written a couple posts on the approximation by the Indian astronomer Aryabhata (476-550). The approximation is accurate for x in [-/2, /2]. The first post collected a Twitter thread about the approximation into a post. The second looked at how far the coefficients in Aryabhata's approximation are from the optimal approximation as a ratio [...]The post A couple more variations on an ancient theme first appeared on John D. Cook.

Write the letters of the alphabet around a circle, then strike out the letters that are symmetrical about a vertical line. The remaining letters are grouped in clumps of 3, 1, 4, 1, and 6 letters. I've heard that this observation is due to Martin Gardner, but I don't have a specific reference. In case [...]The post Finding pi in the alphabet first appeared on John D. Cook.

A few days ago I wrote about the approximation for cosine due to the Indian astronomer Aryabhata (476-550) and gave this plot of the error. I said that Aryabhata's approximation is not quite optimal since the ripples in the error function are not of equal height." This was an allusion to the equioscillation theorem. Chebyshev [...]The post Optimal rational approximation first appeared on John D. Cook.

As mentioned in the previous post, the ratio of consecutive Fibonacci numbers converges to the golden ratio. Is there a sequence whose ratios converge to the silver ratio the way ratios of Fibonacci numbers converge to the golden ratio? (If you're not familiar with the silver ratio, you can read more about it here.) The [...]The post Pell is to silver as Fibonacci is to gold first appeared on John D. Cook.

The number of kilometers in a mile is k = 1.609344 which is close to the golden ratio = 1.6180334. The ratio of consecutive Fibonacci numbers converges to , and so you can approximately convert miles to kilometers by multiplying by a Fibonacci number and dividing by the previous Fibonacci number. For example, you [...]The post Miles to kilometers first appeared on John D. Cook.

This post started out as a Twitter thread. The text below is the same as that of the thread after correcting an error in the first part of the thread. I also added a footnote on a theorem the thread alluded to. *** The following approximation for sin(x) is remarkably accurate for 0 < x [...]The post Ancient accurate approximation for sine first appeared on John D. Cook.

This post will give three ways to multiply by taken from [1]. Simplest approach Here's a very simple observation about : 3 + 0.14 + 0.0014. So if you need to multiply by , you need to multiply by 3 and by 14. Once you've multiplied by 14 once, you can [...]The post Mentally multiply by first appeared on John D. Cook.

For a standard normal random variable Z, the probability that Z exceeds some cutoff z is given by If you wanted to compute this probability numerically, you could obviously evaluate its defining integral numerically. But as is often the case in numerical analysis, the most obvious approach is not the best approach. The range of [...]The post A better integral for the normal distribution first appeared on John D. Cook.

Take a compass and draw a circle on a globe. Then take the same compass, opened to the same width, and draw a circle on a flat piece of paper. Which circle has more area? If the circle is small compared to the radius of the globe, then the two circles will be approximately equal [...]The post Drawing with a compass on a globe first appeared on John D. Cook.

The Poisson probability distribution gives a simple, elegant model for count data. You can even derive from certain assumptions that data must have a Poisson distribution. Unfortunately reality doesn't often go along with those assumptions. A Poisson random variable with mean also has variance . But it's often the case that data that would [...]The post The negative binomial distribution and Pascal's triangle first appeared on John D. Cook.

It is well known that the harmonic series 1 + + + 1/4 + ... diverges. But if you take the denominators as numbers in base 11 or higher, the series converges [1]. I wonder what inspired this observation. Maybe Brewster was bored, teaching yet another cohort of students that the harmonic series [...]The post A strange take on the harmonic series first appeared on John D. Cook.

Suppose you have two normal random variables, X and Y, and that the variance of X is less than the variance of Y. Let M be an equal mixture of X and Y. That is, to sample from M, you first chose X or Y with equal probability, then you choose a sample from the [...]The post Variance matters more than mean in the extremes first appeared on John D. Cook.