John D. Cook

Every condition that all primes satisfy has a corresponding primality test and corresponding class of pseudoprimes. The most famous example is Fermat’s little theorem. That theorem says that for all primes p, a certain congruence holds. The corresponding notion of pseudoprime is a composite number that also satisfies Fermat’s congruence. To make a useful primality […]

Fermat’s little theorem says that if p is a prime number, then for any integer b, bp-1 = 1 (mod p). This gives a necessary but not sufficient test for a number to be prime. A number that satisfies the equation above but is not prime is called a pseudoprime [1] for base b. For example, […]

I ran across an article this morning about the booming market for low-tech tractors. Farmers are buying up old tractors at auction because the older tractors are cheaper to buy, cheaper to operate, and cheaper to repair. The article opens with the story of Kris Folland, a Minnesota farmer who bought a 1979 John Deere […]

A number is said to be “smooth” if all its prime factors are small. To make this precise, a number is said to be y-smooth if it only has prime factors less than or equal to y. So, for example, 1000 is 5-smooth. The de Bruijn function φ(x, y) counts the number of y-smooth positive […]

A sufficient statistic summarizes a set of data. If the data come from a known distribution with an unknown parameter, then the sufficient statistic carries as much information as the full data [0]. For example, given a set of n coin flips, the number of heads and the number of flips are sufficient statistics. More […]

The number of elements in a finite field must be a prime power, and for every prime power there is only one finite field up to isomorphism. The finite field with 256 elements, GF(28), is important in applications. From one perspective, there is only one such field. But there are a lot of different isomorphic […]

Someone left a comment this morning on my blog post on sinc and jinc integrals regarding the area of the lobes. It would be nice to have the values of integrals of each lobe, i.e. integrals between 0 and multiples of pi. Anyone knows of such a table? This post will include Python code to […]

It’s easy to manipulate CSV files with basic command line tools until you need to do a join. When your data is spread over two different files, like two tables in a normalized database, joining the files is more difficult unless the two files have the same keys in the same order. Fortunately, the xsv […]

This post shows how to export an Excel file to a CSV file using in2csv from the csvkit package. You could always use Excel itself to export an Excel file to CSV but there are several reasons you might not want to. First and foremost, you might not have Excel. Another reason is that you […]

Sometimes you’re in the flow using the command line and you’d like to briefly switch over to Python without too much interruption. Or it could be the other way around: you’re in the Python REPL and need to issue a quick shell command. One solution would be to run your shell and Python session in […]

Vitalii Tymchyshyn and Andrii Khlevniuk posted a new paper here entitled “On the average number of birthdays in birthday paradox setup.” This paper gives a different perspective on the birthday problem and a new proof. In the usual formation of the birthday problem, one asks the probability that everyone in a group of size n […]

I’ve playing around with driven Van der Pol oscillators. The cosine term is the driving function. You can see a variety of behavior depending on the interaction between the driving frequency and the natural frequency, along with the other parameters. Sometimes you get periodic solutions and sometimes you get chaotic behavior. Here’s the Python code […]

A few days ago I wrote about how to solve differential equations with SciPy’s ivp_solve function using Van der Pol’s equation as the example. Van der Pol’s equation is The parameter μ controls the amount of nonlinear damping. For any initial condition, the solution approach a periodic solution. The limiting periodic function does not depend […]

Here’s a graph of master / apprentice relationships for Jedi and Sith in the Star Wars movies. It’s not exhaustive, but it covers the main relationships in Episodes I through VI. Here’s what you get if you add a dashed arrow for who killed whom. Here’s the dot (GraphVis) code that created the diagrams. digraph […]

These have been the most popular math posts this year. Queueing theory: The science of waiting in line US Army applying abstract math The license plate game How category theory is applied Progress on the Collatz conjecture Any number can start a factorial

Van der Pol’s differential equation is The equation describes a system with nonlinear damping, the degree of nonlinearity given by μ. If μ = 0 the system is linear and undamped, but as μ increases the strength of the nonlinearity increases. We will plot the phase portrait for the solution to Van der Pol’s equation […]

Today’s exponential sum looks sorta like a Christmas wreath with candles. Let me back up and say what “today’s exponential sum” means. I have a page that plots a graph each day, where the function being graphed takes parameters from the date. It plots the partial sums of where m is the month, d is […]

Consider a random walk on the integers mod p. At each step, you either take a step forward or a step back, with equal probability. After just a few steps, you’ll have to be near where you started. After a few more steps, you could be far from your starting point, but you’re probably not. […]

These have been the most popular privacy-related posts here this year. Hashing PII does not protect privacy Rare and strange IDC-10 codes Font fingerprinting Computed IDs and privacy Supercookies

A continuous linear system is stable if and only if all its eigenvalues have negative real parts. There are various other stability criteria, but they boil down to the statement above. For example, there is the Routh stability criterion and the Hurwitz stability criterion. There’s also a continued fraction criterion. But these criteria are just […]

Here’s a simple probability problem with an answer you may find surprising. (The statement of the problem and solution are simple. The proof is not as simple.) Suppose you draw 1,000 serial numbers at random from a set of 1,000,000. Then you make another random sample of 1,000. How likely is it that no numbers […]

Since you can describe a point in the plane with two numbers, why would you choose to use three numbers? Why would you ever want to use a coordinate system with more coordinates than necessary? Barycentric coordinates One way to indicate the location of a point inside a triangle is to give the distance to […]

My daughter had a homework problem the other day that gave the frequencies of several Fourier components and asked her to find the fundamental frequency. The numbers were nice enough that brute force worked, and I’m sure that’s what students were expected to do. But this could easily be a much more sophisticated problem. If […]

Top blog posts this year about command line tools. The hard part in becoming a command line wizard Computational survivalist Computing π with bc Set theory at the command line Working with wide text files Random sampling from a file

If you take a square matrix M, subtract x from the elements on the diagonal, and take the determinant, you get a polynomial in x called the characteristic polynomial of M. For example, let Then The characteristic equation is the equation that sets the characteristic polynomial to zero. The roots of this polynomial are eigenvalues […]

Suppose you’re looking for instances of -42 in a file foo.txt. The command grep -42 foo.txt won’t work. Instead you’ll get a warning message like the following. Usage: grep [OPTION]... PATTERN [FILE]... Try 'grep --help' for more information. Putting single or double quotes around -42 won’t help. The problem is that grep interprets 42 as […]

If you learned regular expressions by using a programming language like Perl or Python, you may be surprised when tools like grep seem broken. That’s because what you think of as simply regular expressions, these tools consider extended regular expressions. Tell them to search on extended regular expressions and some of your frustration will go […]

Toward the end of each year I write a post or two listing the most popular posts by category. This year the categories will be a little different. I’ll start by listing my most popular posts about cryptography this year. Reversing an MD5 hash Naming elliptic curves Inside the AES S-box What is an elliptic […]

How hard is it to factor large numbers? And how secure are encryption methods based on the difficulty of factoring large numbers? The RSA factoring challenges were set up to address these questions. Last year RSA-230 was factored, and this week RSA-240 was factored. This is a 240 digit (795 bit) number, the product of […]

Last night I was helping my daughter with calculus homework. I told her that a common mistake was to forget what the original problem was after getting absorbed in sub-problems that have to be solved. I saw this over and over when I taught college. Then a few minutes later, we both did exactly what […]

I recently got a review copy of Statistics, Data Mining, and Machine Learning in Astronomy. I’m sure the book is especially useful to astronomers, but those of us who are not astronomers could use it as a survey of data analysis techniques, especially using Python tools, where all the examples happen to come from astronomy. […]

Alex Kontorovich had an interesting tweet about the Riemann hypothesis a few days ago. Why is the Riemann Hypothesis hard? Just one reason (of very many): it’s not an analytic question. Here are the values of zeta on the 1/2-line (where at least 40% of the zeros are, all should be) and the 4/5-line, where […]

The Sierpinski triangle has come up several times on this blog. Here’s yet another way to produce a Sierpinski triangle, this time by taking the bitwise-and of two integers. The ith bit of x&y is 1 if and only if the ith bit of x and the ith bit of y are both 1. The […]

Suppose ages in some database are reported in decades: 0, 10, 20, etc. You need to add a 27 year old woman to the data set. How do you record her age? A reasonable approach would to round-to-nearest. In this case, 27 would be rounded up to 30. Another approach would be stochastic rounding. In […]

Often you have two lists, and you want to know what items belong to both lists, or which things belong to one list but not the other. The command line utility comm was written for this task. Given two files, A and B, comm returns its output in three columns: A – B B – […]

I’ve been reading Avi Wigdenson’s new book Mathematics and Computation. It brings a lot of interesting ideas together in compact but readable form. A couple days ago I quoted Widgerson’s comment about problems in class P often having small exponents. Here I wanted to point out another interesting comment [1]. The chapter on quantum computing […]

A crinkle crankle wall, also called a serpentine wall, is a wavy wall that may seem to sacrifice some efficiency for aesthetics. The curves add visual interest, but they use more material than a straight way. Except they don’t! They use more bricks than a straight wall of the same thickness but they don’t have […]

An m by n rook graph is formed by associating a node with each square of an m by n chess board and connecting two nodes with an edge if a rook can legally move from one to the other. That is, two nodes are connected if they are either in the same row or […]

The P vs NP conjecture has always seemed a little odd to me. Or rather the interpretation of the conjecture that any problem in P is tractable. How reassuring is to to know a problem can be solved in time less than some polynomial function of the size of the input if that polynomial has […]

Programming languages differ in the names they use for inverse trig functions, and in some cases differ in their return values for the same inputs. Choice of range If sin(θ) = x, then θ is the inverse sine of x, right? Maybe. Depends on how you define the inverse sine. If -1 ≤ x ≤ […]

I recently had to work with the function f(x; k) = arctan( k tan(x) ) The semicolon between x and k is meant to imply that we’re thinking of x as the argument and k as a parameter. This function is an example of the coming full circle theme I’ve written about several times. Here’s […]

Phys.com published an article a couple days ago NASA finds Neptune moons locked in ‘dance of avoidance’. The article is based on the scholarly paper Orbits and resonances of the regular moons of Neptune. The two moons closest to Neptune, named Naiad and Thalassa, orbit at nearly the same distance, 48,224 km for Naiad and […]

Suppose you want to compute the natural logarithms of every floating point number, correctly truncated to a floating point result. Here by floating point number we mean an IEEE standard 64-bit float, what C calls a double. Which logarithm is hardest to compute? We’ll get to the hardest logarithm shortly, but we’ll first start with […]

The Sketchviz site lets you enter GraphViz code and get out something that looks hand-drawn. I decided to try it on some of the GraphViz diagrams I’ve made for this blog. Here’s a diagram from my post on Rock, Paper, Scissors, Lizard, Spock. The Sketchviz site defaults to Tinos font, which does not look hand-drawn. […]

If you have two sequences, and one is a permutation of the other, how do you measure how far apart the two sequences are? This post was motivated by the previous post on anagram statistics. For a certain dictionary, the code used in that post found that the longest anagram pairs were the following: certifications, […]

An anagram of a word is another word formed by rearranging its letters. For example, “restful” and “fluster” are anagrams. How common are anagrams? What is the largest set of words that are anagrams of each other? What are the longest words which have anagrams? You’ll get different answers to these questions depending on what […]

Many of you have been following my blog for years. Thank you for your time and your feedback. But there are always newcomers, and so periodically I like to write a sort of orientation post. You can subscribe to this blog by RSS or email. I also have a monthly newsletter where I highlight the […]

The previous post looked at an example of strange floating point behavior taking from book End of Error. This post looks at another example. This example, by Siegfried Rump, asks us to evaluate 333.75 y6 + x2 (11 x2 y2 – y6 – 121 y4 – 2) + 5.5 y8 + x/(2y) at x = […]

Here is an example fiendishly designed to point out what could go wrong with floating point arithmetic, even with high precision. I found the following example by Jean-Michel Muller in John Gustafson’s book End of Error. The task is to evaluate the following function at 15, 16, 17, and 9999. Here e(0) is defined by […]

A killer app is an program so useful that people will buy a larger system just to use it. For example, the VisiCalc spreadsheet was a killer app for the Apple II, maybe the first program to be called a “killer app.” People would buy an Apple II just so they could run VisiCalc. Microsoft […]