John D. Cook

The previous post explained why the number of trailing zeros in n! is and that the sum is not really infinite because all the terms with index i larger than log5 n are zero. Here ⌊x⌋ is the floor of x, the largest integer no greater than x. The post gave the example of n […]The post Floor exercises first appeared on John D. Cook.

Here’s a strange pseudorandom number generator I ran across recently in [1]. Starting with a positive integer n, create a sequence of bits as follows. Compute n! as a base 10 number. Cut off the trailing zeros. Replace digits 0 through 4 with 0, and the rest with 1. You’d want to use a fairly […]The post Factorial random number generator first appeared on John D. Cook.

Much of what you’ll read about power laws in popular literature is not mathematically accurate, but still useful. A lot of probability distributions besides power laws look approximately linear on a log-log plot, particularly over part of their range. The usual conclusion from this observation is that much of the talk about power laws is […]The post Power law principles are not about power laws first appeared on John D. Cook.

I ran across a GitHub repo today that features an amusing hack using the sign bit of NaNs for unintended purposes. This is an example of how IEEE floating point numbers have a lot of leftover space devoted to NaNs and infinities. However, relative to the enormous number of valid 64-bit floating point numbers, this […]The post Much ado about NaN first appeared on John D. Cook.

It’s not obvious when a nonlinear differential equation will have a periodic solution, or asymptotically approach a periodic solution. But there are theorems that give sufficient conditions. This post is about one such theorem. Consider the equation x” + f(x) x‘ + g(x) x = 0 where f and g are analytic and define F(x) […]The post Nonlinear ODEs with stable limit cycles first appeared on John D. Cook.

Suppose we have a differential equation of the form x” + b(t) x‘ + c(t) x = f(t) where the functions b and c are periodic with the same period T. When does the equation above have a solution with period T? It turns out [1] the equation above will have a T-periodic solution for […]The post Linear ODEs with periodic solutions first appeared on John D. Cook.

Let p be a prime number. This post explores a relationship between the number of digits in the reciprocal of p and in the reciprocal of powers of p. By the number of digits in a fraction we mean the period of the decimal representation as a repeating sequence. So, for example, we say there […]The post Reciprocals of prime powers first appeared on John D. Cook.

There are two techniques in software development that have an almost gnostic mystique about them: monads and macros. The photo is a pun [1]. Pride and pragmatism As with everything people do, monads and macros are used with mixed motives, for pride and for pragmatism. As for pride, monads and macros have just the right […]The post Monads and Macros first appeared on John D. Cook.

I seem to run into Catalan numbers fairly regularly. This evening I ran into Catalan numbers while reading Stephen Wolfram’s book Combinators: A Centennial View [1]. Here’s the passage. The number of combinator expressions of size n grows like {2, 4, 16, 80, 448, 2688, 16896, 109824, 732160, 4978688} or in general 2n CatalanNumber[n-1] = […]The post Combinators and Catalan numbers first appeared on John D. Cook.

Suppose you’re asked to write a function that takes a number and returns a planet. We’ll number the planets in order from the sun, starting at 1, and for our purposes Pluto is the 9th planet. Here’s an obvious solution: def planet(n): planets = [ "Mercury", "Venus", "Earth", "Mars", "Jupiter", "Saturn", "Uranus", "Neptune", "Pluto" ] […]The post Planetary code golf first appeared on John D. Cook.

Suppose X is a beta(a, b) random variable and Y is a beta(c, d) random variable. Define the function g(a, b, c, d) = Prob(X > Y). At one point I spent a lot of time developing accurate and efficient ways to compute g under various circumstances. I did this because when I worked at MD […]The post Beta inequalities with integer parameters first appeared on John D. Cook.

There are similarities across Unix tools that I’ve seldom seen explicitly pointed out. For example, the dollar sign $ refers to the end of things in multiple contexts. In regular expressions, it marks the end of a string. In sed, it refers to last line of a file. In vi it is the command to […]The post Unix via etymology first appeared on John D. Cook.

A few days ago I wrote a brief post showing an interesting pattern that comes from plotting sin(1), sin(2), sin(3), etc. That post uses a logarithmic scale on the horizontal axis. You get a different, but also interesting, pattern when you use a linear scale. Someone commented that this looks like a projection of a […]The post Carbon nanotube-like plots first appeared on John D. Cook.

This post is about the word problem. When mathematicians talk about “the word problem” we’re not talking about elementary math problems expressed in prose, such as “If Johnny has three apples, ….” The word problem in algebra is to decide whether two strings of symbols are equivalent given a set of algebraic rules. I go […]The post Why is the word problem hard? first appeared on John D. Cook.

The symbols ≪ and ≫ may be confusing the first time you see them, but they’re very handy. The symbol ≪ means “much less than, and its counterpart ≫ means “much greater than”. Here’s a little table showing how to produce the symbols. |-------------------+---------+-------+------| | | Unicode | LaTeX | HTML | |-------------------+---------+-------+------| | Much […]The post Much less than, Much greater than first appeared on John D. Cook.

The following graph plots sin(1), sin(2), sin(3), etc. It is based on a graph I found on page 42 of Analysis by its History by Hairer and Wainer. Here’s the Python code that produced the plot. import matplotlib.pyplot as plt from numpy import arange, sin x = arange(1, 3000) plt.scatter(x, sin(x), s=1) plt.xscale("log") plt.savefig("int_sin.png")The post Integer sines first appeared on John D. Cook.

I recently needed a word for “multiply by 13” that was parallel to quadruple for “multiply by 4”, so I made up triskadekaduple by analogy with triskadecaphobia. That got me to wondering how you make words for multiples higher than four. The best answer is probably “don’t.” Your chances of being understood drop sharply after […]The post Double, triple, quadruple, … first appeared on John D. Cook.

The previous post discussed how you would plan an attempt to set a record in computing ζ(3), also known as Apéry’s constant. Specifically that post looked at how to choose your algorithm and how to anticipate the number of terms to use. Now suppose you wanted to actually do the calculation. This post will carry […]The post Functions in bc first appeared on John D. Cook.

Before carrying out a big calculation, you want to have an idea how long various approaches would take. This post will illustrate this by planning an attempt to calculate Apéry’s constant to enormous precision. This constant has been computed to many decimal places, in part because it’s an open question whether the number has a […]The post Planning a world record calculation first appeared on John D. Cook.

Robin Dunbar proposed that humans are capable of maintaining social relationships with about 150 people. At first this number may seem too small, especially for someone with a thousand “friends” on social media. But if you raise the bar a little on who you consider a friend, 150 may seem too large. A couple examples […]The post Dunbar’s number and C. S. Lewis first appeared on John D. Cook.

Define These binomial coefficients come up frequently in application. In particular, they came up in the previous post. I wanted to give an asymptotic approximation for f(n, k), and I thought it might be generally useful, so I pulled it out into its own post. I used Mathematica to calculate an approximation. First, I used […]The post kn choose n first appeared on John D. Cook.

A few days ago I wrote about computing ζ(3). I spent most of that post discussing simple but inefficient methods of computing ζ(3), then mentioned that there were more efficient methods. I recently ran across a paper [1] that not only gives more efficient methods for computing ζ(3), it gives a method for generating methods. […]The post Calculating ζ(3) faster first appeared on John D. Cook.

Is there a function whose derivative is its inverse? In other words, is there a function f that satisfies f ‘(x) = f-1(x) for positive x? Indeed there is one given here. Let φ be the golden ratio (√5 + 1)/2. Then for x > 0 the function f(x) = φ (x/φ)φ satisfies our equation. […]The post When derivative equals inverse first appeared on John D. Cook.

If someone tells you they want to replace A’s with B’s and B’s with A’s, they are implicitly talking about parallel assignment. They almost certainly don’t mean “Replace all A’s with B’s. Then replace all B’s with A’s.” They expect the name of the Swedish pop group ABBA to be turned into “BAAB”, but if […]The post Parallel versus sequential binding first appeared on John D. Cook.

A palindrome is a word or sentence that remains the same when its characters are reversed. For example, the word “radar” is a palindrome, as is the sentence “Madam, I’m Adam.” I was thinking today about Morse code palindromes, sequences of Morse code that remain the same when reversed. This post will look at what […]The post Morse code palindromes first appeared on John D. Cook.

There is an apocryphal story that someone from the Manhattan Project asked a mathematician how to uniformly distribute 100 points on a sphere. The mathematician replied that it couldn’t be done, and the project leader thought the mathematician was being uncooperative. If this story is true, the mathematician’s response was correct but unhelpful. He took […]The post Spreading out points on a sphere first appeared on John D. Cook.

Monte Carlo integration, or “integration by darts,” is a general method for evaluating high-dimensional integrals. Unfortunately it’s slow. This motivated the search for methods that are like Monte Carlo integration but that converge faster. Quasi-Monte Carlo (QMC) methods use low discrepancy sequences that explore a space more efficiently than random samples. These sequences are deterministic […]The post Quasi-Monte Carlo integration: periodic and nonperiodic first appeared on John D. Cook.

Howard Aiken on the uses of computers, 1955: If it should turn out that the basic logics of a machine designed for the numerical solution of differential equations coincide with the basic logics of a machine intended to make bills for a department store, I would regard this as the most amazing coincidence I have […]The post Differential Equations and Department Stores first appeared on John D. Cook.

A while back I wrote about a simple equation for the shape of an egg. That equation is useful for producing egg-like images, but it’s not based on extensive research into actual eggs. I recently ran across a more realistic, but also more complicated, equation for modeling the shape of real eggs [1]. The equation […]The post Empirical formula for the shape of an egg first appeared on John D. Cook.

I’ve started reading Paul Nahin’s new book “In Pursuit of ζ(3).” The actual title is “In Pursuit of Zeta-3.” I can understand why a publisher would go with such a title, but I assume most people who read this blog are not afraid of Greek letters. I’ve enjoyed reading several of Nahin’s books, so I […]The post Computing ζ(3) first appeared on John D. Cook.

The previous post looked at the multiplicative group of integers modulo a number of the form n = pq where p and q are prime. This post looks at general n. The multiplicative group mod n consists of the integers from 1 to n-1 that are relative prime to n. So the size of this group […]The post How small can a multiplicative group be? first appeared on John D. Cook.

One way of looking at RSA encryption, a way that generalizes to new methods, is that the method is based on group operations inside a group of unknown order, i.e. unknown to most people. Another way of putting it is that RSA encryption takes place in a group where everybody knows how to multiply but […]The post Encryption in groups of unknown order first appeared on John D. Cook.

I got an email from Fr. John Rickert today, and with his permission I’ll share part of it here. A sin of commission occurs when we do something we should not do. A system is consistent (or maybe I should say “sound”) if the results of proofs really are true. Gödel’s 2nd Incompleteness Theorem says […]The post Logic in moral terminology first appeared on John D. Cook.

Missing data throws a monkey wrench into otherwise elegant plans. Yesterday’s post on genetic sequence data illustrates this point. DNA sequences consist of four bases, but we need to make provision for storing a fifth value for unknowns. If you know there’s a base in a particular position, but you don’t know what its value […]The post Missing data first appeared on John D. Cook.

The home page for the OpenSSL project says OpenSSL is a robust, commercial-grade, and full-featured toolkit for the Transport Layer Security (TLS) and Secure Sockets Layer (SSL) protocols. It is also a general-purpose cryptography library. … If you’ve never heard of the project before, you would rightly suppose that OpenSSL implements SSL (and its successor […]The post Also a crypto library first appeared on John D. Cook.

There are special compression algorithms for genetic sequence data, but I was curious how well simply zipping a text file would work. I downloaded a 14 MB text file containing DNA sequence data from a fruit fly and compressed it as a zip file and as a 7z file. The result was about 3.5 MB, […]The post Naive compression of genetic data first appeared on John D. Cook.

FM radio transmits a signal by perturbing (modulating) the frequency of a carrier wave. If the carrier has frequency ω and the signal has frequency q, then the FM signal is cos(ωt + β cos(qt)). To understand the modulated signal, it’s useful to write it as a sum of simple sines and cosines with no […]The post FM signal approximation first appeared on John D. Cook.

Psychologists say that random rewards are more addictive than steady, predictable rewards. But I believe this only applies to relatively frequent feedback. If rewards are too infrequent, there’s no emotional connection between behavior and reward. The connection becomes more intellectual and less visceral as feedback becomes less frequent and less predictable. Nassim Taleb distinguishes between […]The post Black Swan Gratification first appeared on John D. Cook.

Old cryptography never dies. After a method is broken, its use declines, but never goes to zero. And when I say “broken,” I do not mean no longer recommended, but broken to the point of being trivial to decrypt. I recently ran across an anecdote from World War I showing this is nothing new. The […]The post Using cryptography broken 50 years ago first appeared on John D. Cook.

I generally despise emoji, but I reluctantly learned a few things about them this morning. My latest couple blog posts involved chess, and I sent out a couple tweets using chess symbols. Along the way I ran into a mystery: sometimes the black pawn is much larger than other chess symbols. I first noticed this […]The post Unicode and Emoji, or The Giant Pawn Mystery first appeared on John D. Cook.

The eight queens problem is to place eight queens on a chessboard so that no queen attacks another. Because queens are allowed to move any number of spaces horizontally, vertically, or diagonally, this means no queen can be on the same row, column, or diagonal as any other queen. For example, the following image gives […]The post Queens on a donut first appeared on John D. Cook.

I needed to make an image of a chessboard for the next blog post, and I’m not very good at image editing, so I make one using Excel. There are Unicode characters for chess pieces— white king is U+2654, etc.—and so you can make a chessboard out of (Unicode) text. ♔♕♖♗♘♙♚♛♜♝♞♟ I placed the character […]The post How to make a chessboard in Excel first appeared on John D. Cook.

I needed to know the frequencies of letters at the beginning of words for a project. The overall frequency of letters, wherever they appear in a word, is well known. Initial frequencies are not so common, so I did a little experiment. I downloaded the Canterbury Corpus and looked at the frequency of initial letters […]The post Initial letter frequency first appeared on John D. Cook.

Garrison Keillor’s fictional Lake Wobegon is a place “where all the children are above average.” Donald Knuth alluded to this in his exercise regarding “Lake Wobegon Dice,” a set of dice where the roll of each die is (probably) above average. Let A be a six-sided die with a 5 on one side and 3’s […]The post Lake Wobegon Dice first appeared on John D. Cook.

Index of coincidence is a statistic developed by William Friedman for use in cryptanalysis. It measures how unevenly symbols are distributed in a message. It’s a kind of signature that could be used, for example, to infer the language of a text, even if the text has been encrypted with a simple substitution cipher. It […]The post Index of coincidence first appeared on John D. Cook.

I was reading a book on orbital mechanics recently [1], and one of the things that stood out was the use of two variations on sine and cosine, functions the book denotes by S and C. Strictly speaking, the functions are defined to be the analytic continuation of the middle expressions to the full complex […]The post S and C functions first appeared on John D. Cook.

It’s simpler to search the web than to search software-specific documentation. You can just type your query into a search engine and not have to be bothered by the differences in offline documentation systems for different software. But there are a couple disadvantages. First, the result may not be that relevant. For example, maybe you […]The post Offline documentation first appeared on John D. Cook.

Carver Mead on engineering: Engineering isn’t something you study and learny, and memorize, and know where to look up. Engineering is understanding things all the way to the bottom, no matter what field they are called, and being able use that to build stuff and make it work. I edited the quote slightly. Mead was […]The post Engineering attitude first appeared on John D. Cook.

I was reading a book on computer algebra and ran across an interesting theorem about Carmichael numbers in the one of the exercises. I’ll present that theorem below, but first I’ll back up and say what a pseudoprime is and what a Carmichael number is. Fermat’s theorem If p is a prime number, then for […]The post Searching for pseudoprimes first appeared on John D. Cook.

I ran across an interesting footnote in Wolfram Koepf’s book Computer Algebra. Gosper’s algorithm [1] was probably the first algorithm which would not have been found without computer algebra. Gosper writes in his paper: “Without the support of MACSYMA and its developer, I could not have collected the experiences necessary to provoke the conjectures that […]The post Finding computer algebra algorithms with computer algebra first appeared on John D. Cook.