John D. Cook

You can define a topology on the positive integers by choosing as an open basis sets the series of the form an + b where a and b are relatively prime positive integers. Solomon Golumb defines this topology in [1] and proves that it is connected. But that paper doesn’t prove that proposed basis really […]The post A connected topology for the integers first appeared on John D. Cook.

You can sometimes make code more readable by using names for characters rather than the characters themselves or their code points. Python and Perl both, for example, let you refer to a character by using its standard Unicode name inside \N{}. For instance, \N{SNOWMAN} refers to Unicode character U+2603, shown at the top of the […]The post Accessing characters by name first appeared on John D. Cook.

The numbers that make up today’s date—12, 16, and 20—form a Pythagorean triple. That is, 12² + 16² = 20². There won’t be any such dates next year. You could confirm this by brute force since there are only 365 days in 2021, but I hope to do something a little more interesting here. The […]The post Pythagorean dates first appeared on John D. Cook.

The goal this post is to show how to call Perl and Python one-liners from a shell. We want to be able to use bash on Linux, and cmd or PowerShell on Windows, ideally with the same code in all three shells. Bash Bash interprets text inside double quotes but not in single quotes. So […]The post Shells, quoting, and one-liners first appeared on John D. Cook.

Pick a positive integer k and take the product of k consecutive integers greater than k. Then the result is divisible by a prime number greater than k. This theorem was first proved 128 years ago [1]. For example, suppose we pick k = 5. If we take the product 20*21*22*23*24 then it’s obviously divisible […]The post Factors of consecutive products first appeared on John D. Cook.

Logic vs C I recently made a mistake because I interpreted the symbol ^ in the wrong context. I saw an expression of the form a ^ b and thought of the ^ as AND, as in logic, but the author’s intent was XOR, as in C. How else might someone misinterpret the ^ operator? […]The post Four meanings of ^ first appeared on John D. Cook.

I first heard the hymn “I Vow to Thee, My Country” while watching the first season of The Crown [1]. I assume the hymn is familiar in the UK, but it is not in America as far as I know. When I say I first heard the hymn, I mean that I first heard it […]The post \The Crown and The Planets\ first appeared on \John D\. Cook\.

Suppose you want to estimate the number of patients who respond to some treatment in a large population of size N and what you have is data on a small sample of size n. The usual way of going about this calculates the proportion of responses in the small sample, then pretends that this is […]The post Predictive probability for large populations first appeared on John D. Cook.

Applications of statistics often require working with for large x and fixed α and β. The simplest approximation to this ratio of gamma functions is You can do a little better [1] with where c = (α + β – 1)/2. To get more accuracy we’ll need more terms. Tricomi and Erdélyi worked out the […]The post Asymptotic series for gamma function ratios first appeared on John D. Cook.

You can uniquely represent a large number by its remainders when divided by smaller numbers, provided the smaller numbers have no factors in common, and carry out arithmetic in this representation. Such a representation is called a Residue Number System (RNS). In the 1960’s people realized RNSs could be useful in computer arithmetic. The original […]The post Redundant Residue Number Systems first appeared on John D. Cook.

The largest known primes are Mersenne primes, in part because the Lucas-Lehmer algorithm makes it more efficient to test Mersenne numbers for primality than to test arbitrary numbers. These numbers have the form 2n – 1. The Great Internet Mersenne Prime Search (GIMPS) announced today that they have tested whether 2n – 1 is prime […]The post Ruling out gaps in the list of Mersenne primes first appeared on John D. Cook.

Formal verification of theorems takes a lot of work. And it takes more work where it is least needed. But the good news is that it takes less effort in contexts where it is needed most. Years of effort have gone into formally verifying the proofs of theorems that no one doubted were correct. For […]The post When are formal proofs worth the effort? first appeared on John D. Cook.

Can you define something like cross product of three-dimensional vectors in other dimensions? That depends on what you mean by a product being “like” the familiar cross product. In [1] Walsh lists several properties of the cross product, and proves that there exists a product with these properties only in dimensions 1, 3, and 7. […]The post A cross product in 7 dimensions first appeared on John D. Cook.

An integer n is said to be square-free if no perfect square (other than 1) divides n. Similarly, n is said to be cube-free if no perfect cube (other than 1) divides n. In general, n is said to be k-free if it has no divisor d > 1 where d is a kth power […]The post Density of square-free numbers, cube-free numbers, etc. first appeared on John D. Cook.

A digitally delicate prime is a prime number such that if any of its digits are changed by any amount, the result is not prime. The smallest such number is 294001. This means that variations on this number such as 394001 or 291001 or 294081 are all composite. A paper [1] posted last week gives […]The post Digitally delicate primes first appeared on John D. Cook.

Suppose you’re tasked with designing a Christmas countdown figure that uses numbered cube faces. How would you put the numbers on the cubes? Suppose you want the calendar to say “00” on Christmas Day. If we were accustomed to counting in base six, you could label the sides of each cube 0 through 5, and […]The post Cubic calendars first appeared on John D. Cook.

I recently discovered quiver, a tool for drawing commutative diagrams. It looks like a nice tool for drawing diagrams more generally, but it’s designed particularly to include the features you need when drawing the kinds of diagrams that are ubiquitous in category theory. You can draw diagrams using the online app and export the result […]The post Drawing commutative diagrams with Quiver first appeared on John D. Cook.

Let π(x) be the number of primes less than x. The simplest form of the prime number theorem says that π(x) is asymptotically equal to x/log(x), where log means natural logarithm. That is, This means that in the limit as x goes to infinity, the relative error in approximating π(x) with x/log(x) goes to 0. […]The post Refinements to the prime number theorem first appeared on John D. Cook.

The previous post looked at all Boolean expressions on three or four variables and how much they can be simplified. The number of Boolean expressions on n variables is and so the possibilities explode as n increases. We could do n = 3 and 4, but 5 would be a lot of work, and 6 […]The post Minimizing random Boolean expressions first appeared on John D. Cook.

In the previous post we looked at how to minimize Boolean expressions using a Python module qm. In this post we’d like to look at how much the minimization process shortens expressions. Witn n Boolean variables, you can create 2^n terms that are a product of distinct variables. You can specify a Boolean function by […]The post How much can Boolean expressions be simplified? first appeared on John D. Cook.

This post will look at how to take an expression for a Boolean function and look for a simpler expression that corresponds to the same function. We’ll show how to use a Python implementation of the Quine-McCluskey algorithm. Notation We will write AND like multiplication, OR like addition, and use primes for negation. For example, […]The post Minimizing boolean expressions first appeared on John D. Cook.

Linear logic uses an unusual symbol, an ampersand rotated 180 degrees, for multiplicative disjunction. The symbol is U+214B in Unicode. I was looking into how to produce this character in LaTeX when I found that the package cmll has two commands that produce this character, one semantic and one descriptive: \parr and \invamp [1]. This […]The post Rotating symbols in LaTeX first appeared on John D. Cook.

Suppose you want to find the smallest number with 5 divisors. After thinking about it a little you might come up with 16, because 16 = 24 and the divisors of 16 are 2k where k = 0, 1, 2, 3, or 4. This approach generalizes: For any prime q, the smallest number with q divisors […]The post The smallest number with a given number of divisors first appeared on John D. Cook.

Both Pfizer and Moderna have announced recently that their SARS-COV2 vaccine candidates reduce the rate of infection by over 90% in the active group compared to the control (placebo) group. That’s great news. The vaccines may turn out to be less than 90% effective when all is said and done, but even so they’re likely […]The post Good news from Pfizer and Moderna first appeared on John D. Cook.

The other day I saw an article about some math test and thought “I bet I’d blow that away now.” Anyone who has spent a career using some skill ought to blow away an exam intended for people who have been learning that skill for a semester. However, after thinking about it more, I’m pretty […]The post I think I'll pass first appeared on John D. Cook.

A couple years ago I wrote a blog post looking at how close the quaternions come to commuting. That is, the post looked at the average norm of xy – yx. A related question would be to ask how often quaternions do commute, i.e. the probability that xy – yx = 0 for randomly chosen […]The post Probability of commuting first appeared on John D. Cook.

There are simple rules for telling whether a number is divisible by 2, 3, 4, 5, and 6. A number is divisible by 2 if its last digit is divisible by 2. A number is divisible by 3 if the sum of its digits is divisible by 3. A number is divisible by 4 if […]The post Test for divisibility by 13 first appeared on John D. Cook.

This evening I ran across a paper on an unusual coordinate system that creates interesting graphs based from simple functions. It’s called “circular coordinates,” but this doesn’t mean polar coordinates; it’s more complicated than that. [1] Here’s a plot reproduced from [1], with some color added (the default colors matplotlib uses for multiple plots). The […]The post Some mathematical art first appeared on John D. Cook.

Let T(N) be the number of distinct (non-congruent) triangles with integer sides and perimeter N. For example, T(12) = 3 because there are three distinct triangles with integer sides and perimeter 12. There’s the equilateral triangle with sides 4 : 4 : 4, and the Pythagorean triangle 3 : 4 : 5. With a little […]The post Counting triangles with integer sides first appeared on John D. Cook.

I ran across a paper [1] this morning on the differential equation y‘ = sin(xy). The authors recommend having students explore numerical solutions to this equation and discover theorems about its solutions. Their paper gives numerous theorems relating solutions and the hyperbolas xy = a: how many times a solution crosses a hyperbola, at what […]The post Ripples and hyperbolas first appeared on John D. Cook.

When the rule for stopping an experiment depends on the data in the experiment, the results could be biased if the stopping rule isn’t taken into account in the analysis [1]. For example, suppose Alice wants to convince Bob that π has a greater proportion of even digits than odd digits. Alice: I’ll show you […]The post Informative stopping first appeared on John D. Cook.

California’s CCPA regulation has been amended to say that data considered deidentified under HIPAA is considered deidentified under CCPA. The amendment was proposed last year and was finally signed into law on September 25, 2020. This is good news because it’s relatively clear what deidentification means under HIPAA compared to CCPA. In particular, HIPAA has […]The post Expert determination for CCPA first appeared on John D. Cook.

I imagine most programmers who develop an interest in category theory do so after hearing about monads. They ask someone what a monad is, and they’re told that if they really want to know, they need to learn category theory. Unfortunately, there are couple unnecessary difficulties anyone wanting to understand monads etc. is likely to […]The post Category theory for programmers made easier first appeared on John D. Cook.

The previous post looked at random Fibonacci sequences. These are defined by f1 = f2 = 1, and fn = fn-1 ± fn-2 for n > 2, where the sign is chosen randomly to be +1 or -1. Conjecture: Every integer can appear in a random Fibonacci sequence. Here’s why I believe this might be […]The post Is every number a random Fibonacci number? first appeared on John D. Cook.

The Fibonacci numbers are defined by F1 = F2 = 1, and for n > 2, Fn = Fn-1 + Fn-2. A random Fibonacci sequence f is defined similarly, except the addition above is replaced with a subtraction with probability 1/2. That is, f1 = f2 = 1, and for n > 2, fn = […]The post Random Fibonacci numbers first appeared on John D. Cook.

I’ve been thinking about Edsger Dijkstra lately because I suspect some of the ideas he developed will be useful for a project I’m working on. While searching for some of Dijkstra’s writings I ran across the article Edsger Dijkstra: The Man Who Carried Computer Science on His Shoulders. It occurred while reading this article that […]The post Edsger Dijkstra, blogger first appeared on John D. Cook.

My wife and I were talking this morning and the phrase”less disingenuous” came up. I thought about how sometimes a positive word fades into obscurity while the negative form lives on. The first example that came to mind is gruntled vs disgruntled. Yes, the former is an English word, but a rare one. Here’s a […]The post Gruntled vs disgruntled first appeared on John D. Cook.

The first time I went a few days without blogging, someone sent me a concerned email asking whether I was OK. And in case anyone has had similar thoughts this week, I’m doing well. I’m busy, though my rate of blogging is fairly independent of how busy I am. Sometimes being busy gives me lots […]The post Doing well first appeared on John D. Cook.

In a comment to my previous post on quatrefoils, Jan Van lint suggested a different equation for quatrefoils: r = a + |cos(2θ)| Here are some examples of how these curves look for varying values of a. As a increases, the curves get rounder. We can quantify this by looking at the angle between the […]The post More fun with quatrefoils first appeared on John D. Cook.

Most people have heard of word problems, but not as many have heard of the word problem. If you’re imagining that the word problem is some superlatively awful word problem, I can assure you it’s not. It’s both simpler and weirder than that. The word problem is essentially about whether you can always apply algebraic […]The post The word problem first appeared on John D. Cook.

There’s an ancient saying “Whom the gods would destroy they first make mad.” (Mad as in crazy, not mad as in angry.) I wrote a variation of this on Twitter: Whom the gods would destroy, they first give real-time analytics. Having more up-to-date information is only valuable up to a point. Past that point, you’re […]The post Real-time analytics first appeared on John D. Cook.

In his book The Algorithm Design Manual, Steven Skiena has several sections called “War Stories” where he talks about his experience designing algorithms for clients. Here’s an excerpt of a story about finding the best airline ticket prices. “Look,” I said at the start of the first meeting. “This can’t be so hard. Consider a […]The post Naive modeling first appeared on John D. Cook.

I often work in a sort of amphibious environment, using Unix software on Windows. As you can well imagine, this causes headaches. But I’ve found such headaches are generally more manageable than the headaches from alternatives I’ve tried. On the Windows command line, you can type the name of a file and Windows will open […]The post Opening Windows files from bash and eshell first appeared on John D. Cook.

A Pythagorean triple is a set of positive integers that can be the lengths of sides of a right triangle, i.e. numbers a, b, and c such that a² + b² = c². A primitive Pythagorean triple (PPT) is a Pythagorean triple whose elements are relatively prime. For example, (50, 120, 130) is a Pythagorean […]The post Generating all primitive Pythagorean triples with linear algebra first appeared on John D. Cook.

A “rose” in mathematics is typically a curve with polar equation r = cos(kθ) where k is a positive integer. If k is odd, the resulting graph has k “petals” and if k is even, the plot has 2k petals. Sometimes the term rose is generalized to the case of non-integer k. This is the […]The post Playing around with a rational rose first appeared on John D. Cook.

I was reading The 99% Invisible City this evening, and there was a section on quatrefoils. Here’s an example of a quatrefoil from Wikipedia. There’s no single shape known as a quatrefoil. It’s a family of shapes that look something like the figure above. I wondered how you might write a fairly simple mathematical equation […]The post Quatrefoils first appeared on John D. Cook.

I’m working on a project these days where I’ve used four different kinds of matrix product, which made me wonder if there’s another kind of product out there that I could find some use for. In the process of looking around for other matrix products, I ran across the Kronecker sum. I’ve seen Kronecker products […]The post Kronecker sum first appeared on John D. Cook.

This post is a follow-on to the previous post on perfectly nonlinear functions. In that post we defined a way to measure the degree of nonlinearity of a function between two Abelian groups. We looked at functions that take sequences of four bits to a single bit. In formal terms, our groups were GF(24) and […]The post Nonlinear mod 5 first appeared on John D. Cook.

The other day I heard someone suggest that a good cocktail party definition of cryptography is puzzle making. Cryptographers create puzzles that are easy to solve given the key, but ideally impossible without the key. Linearity is very useful in solving puzzles, and so a puzzle maker would like to create functions that are as […]The post Perfectly nonlinear functions first appeared on John D. Cook.

Here’s an amusing little Python program to convert integers to Roman numerals: def roman(n): print(chr(0x215F + n)) It only works if n is between 1 and 12. That’s because Unicode contains characters for the Roman numerals I through XII. Here are the characters it produces: Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ Ⅵ Ⅶ Ⅷ Ⅸ Ⅹ […]The post Python one-liner to print Roman numerals first appeared on John D. Cook.