John D. Cook

If p is an odd prime, there is a theorem that says x^2 = -1 mod p has a solution if and only if p = 1 mod 4. When a solutionx exists, how do you find it? The previous two posts have discussed Stan Wagon's algorithm for expressing an odd prime p as a [...]The post Finding a square root of -1 mod p first appeared on John D. Cook.

The previous post briefly mentioned Stan Wagon's algorithm for expressing an odd prime p as a sum of two squares when it is possible (i.e. when p = 1 mod 4). Wagon's algorithm requires first finding a non-square modp, i.e. a number c such that c d^2 mod p for any d in 1, [...]The post Finding a non-square mod p first appeared on John D. Cook.

I saw where Elon Musk posted Grok's answer to the prompt What are the most beautiful theorems." I looked at the list, and there were no surprises, as you'd expect from a program that works by predicting the most likely sequence of words based on analyzing web pages. There's only one theorem on the list [...]The post Expressing a prime as the sum of two squares first appeared on John D. Cook.

Suppose you have twon * n matrices, A and B, and you would like to find a rotation matrix that lines upB withA. That is, you'd like to find such that A = B. This is asking too much, except in the trivial case ofA andB being 1 * 1 matrices. You could [...]The post Aligning one matrix with another first appeared on John D. Cook.

The previous post discussed two ways to compute the nth Fibonacci number. The first is to compute all the Fibonacci numbers up to thenth iteratively using the defining property of Fibonacci numbers Fn + 2 = Fn + Fn + 1 with extended integer arithmetic. The second approach is to use Binet's formula Fn = [...]The post Computing large Fibonacci numbers first appeared on John D. Cook.

A few days ago I wrote about Fibonacci numbers and certificates. As I pointed out in the article, there's no need to certify Fibonacci numbers, but the point of the post was to illustrate the idea of a solution certificate in a simple context. Practical uses of certificates are more complicated. This time I want [...]The post Fibonacci numbers and time-space tradeoffs first appeared on John D. Cook.

Supposef(x) is the sum of terms of the form cos(kx) wherek is an integer from a set A with nelements. Then the maximum value of f isf(0) =n. But what is the minimum value off? The Chowla cosine conjecture says that the minimum should be less than -n for large n. For now the best [...]The post Minimum of cosine sum first appeared on John D. Cook.

Classroom When you take a linear algebra course and get to the chapter on eigenvalues, your homework problems will include a small matrix A and you will be asked to find the eigenvalues. You do this by computing the determinant det(A - I) = P() and getting P(), a polynomial in . The roots of [...]The post Eigenvalue homework problems are backward first appeared on John D. Cook.

Suppose I give you a big numberF and claim thatF is a Fibonacci number. How could you confirm this? Before I go further, let me say what this post is really about. It's not about Fibonacci numbers so much as it is about proofs and certificates. There's no market for large Fibonacci numbers, and certainly [...]The post Fibonacci number certificates first appeared on John D. Cook.

If n is a positive integer, then rounding (1/n) up to the nearest integer givesn. In symbols, We an illustrate this with the following Python code. >>> from scipy.special import gamma >>> from math import ceil >>> for n in range(1, 101): ... assert(ceil(gamma(1/n)) == n) You can find a full proof in [1]. I'll [...]The post (1/n) first appeared on John D. Cook.

Yesterday I ran across the following mashup by Amy Swearer of a Polish proverb and the Serenity Prayer. Lord, grant me the serenity to accept when it's no longer my circus, the courage to control the monkeys that are still mine, and the wisdom to know the difference. The proverb is Nie moj cyrk, nie [...]The post Polish serenity first appeared on John D. Cook.

I saw an animation this morning showing how the space above our planet is dangerously crowded with satellites. That motivated me to do a little back-of-the-envelope math. The vast majority of satellites are in low earth orbit (LEO), which extends from 160 to 2000 km above the earth's surface. The radius of the earth is [...]The post Satellites have a lot of room first appeared on John D. Cook.

Demis: [to get to AGI] maybe there's one or two big innovations needed" Sam: everything based off what we see today is that it will happen." Ilya: But is the belief really that if you just 100x the scale, everything would be transformed? I don't think that's true." Dario: If you just kind of like [...]The post AGI, ASI, A*I - Do we have all we need to get there? first appeared on John D. Cook.

Cryptocurrency and privacy don't fit together as easily as you might expect. Blockchains give you the illusion of privacy via pseudonymization: you don't put your name on a blockchain, but you do put information on a blockchain that can be used to determine your name. Blockchain analysis can often reveal information that no one intended [...]The post Bridging secrets is hard first appeared on John D. Cook.

I saw a post on X recently that said Bill Gates is closer to you in wealth than he is to Elon Musk. Mind blown. For round numbers, let's say Elon Musk's net worth is 800 billion and Bill Gates' net worth is 100 billion. So if your net worth is less 450 billion, the [...]The post Fortunes and Geometric Means first appeared on John D. Cook.

There is a way to prove that you know two numbersa andb, and their productc =ab, without revealinga,b, orc. This isn't very exciting without more context - maybe you know that 7 * 3 = 21 - but it's a building block of more interesting zero knowledge proofs, such as proving that a cryptocurrency transaction [...]The post Proving you know a product first appeared on John D. Cook.

In a high school math class, the solution to the equation bx =y is the logarithm ofy in baseb. The implicit context of the equation is the real numbers, and the solution is easy to calculate. The same problem in the context of finite groups is called the discrete logarithm problem, and it is difficult [...]The post How to prove you know a discrete logarithm first appeared on John D. Cook.

The Mills ratio [1] is the ratio of the CCDF to the PDF. That is, for a random variable X, the Mills ratio at x is the complementary cumulative distribution function divided by the density function. If the density function of X is f, then The Mills ratio highlights an important difference between the Student [...]The post Mills ratio and tail thickness first appeared on John D. Cook.

I saw something yesterday saying that the Japanese bond market had experienced a six standard deviation move. This brought to mind a post I'd written eight years ago. All probability statements depend on a model. And if you're probability model says an event had a probability six standard deviations from the mean, it's more likely [...]The post Sigmas and Student first appeared on John D. Cook.

I was reading an article this morning that mentioned a styometric analysis of a controversial paragraph written by Roman historian Flavius Josephus. I've written several posts that could be called stylometry or adjacent, but I haven't used that word. Here are some posts that touch on the statistical analysis of a text or of an [...]The post Stylometry first appeared on John D. Cook.

Ugly code may be very valuable, depending on why it's ugly. I'm not saying that it's good for code to be ugly, but that code that is already ugly may be valuable. Some of the ugliest code was started by someone who knew the problem domain well but did not know how to write maintainable [...]The post Two cheers for ugly code first appeared on John D. Cook.

The previous post looked at tightly clustered primes. This post looks at the opposite, large gaps between primes. Riecoin is a cryptocurrency that uses finding prime clusters as its proof of work task. Gapcoin uses finding prime gaps as its proof of work task. There's some nuance to defining prime gaps. It's trivial to produce [...]The post Prime gaps and Gapcoin first appeared on John D. Cook.

Prime clusters are sets of primes that appear as close together as isgenerally possible. There is one pair of consecutive prime numbers, 2 and 3, but there cannot be any more: in any larger pair of consecutive numbers, one of the pair will be even. But there are a lot of twin primes, perhaps infinitely [...]The post Prime clusters and Riecoin first appeared on John D. Cook.

The previous post looked at a technique for inverting multiple integers modm at the same time, using fewer compute cycles than inverting each integer individually. This post will do something analogous for prime chains, revisiting a post from a few days ago about testing prime chains. A prime chain is a sequence of primes in [...]The post Efficiently testing multiple primes at once first appeared on John D. Cook.

The most elementary form of the prime number theorem says that (x), the number of prime numbers less than x, is asymptotically equal to x / log(x). That's true, but a more accurate result says (x) is asymptotically equal to li(x) where Five years ago I wrote about a result that was new at the [...]The post Tighter bounds in the prime number theorem first appeared on John D. Cook.

Suppose you have a large prime numberM and you need to find the inverse of several numbers modM. Montgomery's trick is a way to combine the computation of the inverses to take less time than computing the inverses individually. Peter Montgomery (1947-2020) came up with this trick in 1985. We will illustrate Montgomery's trick by [...]The post Efficiently computing multiple modular inverses at once first appeared on John D. Cook.

The previous post contained an interesting observation: Is it true more generally that for largen? Sorta, but the approximation gets better if we add a correction factor. If we square both sides of the approximation and move the factorials to one side, the question becomes whether Now the task becomes to estimate the middle coefficient [...]The post The middle binomial coefficient first appeared on John D. Cook.

A few days ago I wrote two posts about perfect shuffles. Once you've cut a deck of cards in half, an in-shuffle lets a card from the top half fall first, and an out-shuffle lets a card from the bottom half fall first. Suppose we have a deck of 52 cards. We said in the [...]The post Combining in-shuffles and out-shuffles first appeared on John D. Cook.

When I wrote about how Primecoin uses prime chains for proof of work, I left out a detail. To mine a new Primecoin block, you have to find a prime chain of specified length that starts with a number that is a multiple of the block header hash. According to the Primecoin whitepaper Another important [...]The post Primecoin primality test first appeared on John D. Cook.

I mentioned bi-twin prime chains in the previous post, but didn't say much about them so as not to interrupt the flow of the article. A pair of prime numbers are called twins if they differ by 2. For example, 17 and 19 are twin primes. A bi-twin chain is a sequence of twin primes [...]The post Bi-twin prime chains first appeared on John D. Cook.

The title of this post has a double meaning. We will look at chains in the sense of number theory and in the sense of cryptocurrency, i.e. Cunningham chains and blockchains, that involve prime numbers. Cunningham chains A chain of primes is a sequence of prime numbers in which each is almost double its predecessor. [...]The post Prime chains first appeared on John D. Cook.

Suppose you have a set of k hash values, eachn bits long. Can you compress the set into less thankn bits? It's not possible to compress alist of hashes into less thankn bits, but you can hash aset into fewer bits. Suppose you have a set of 230, roughly a billion, 64-bit hashes. Sort the [...]The post Compressing a set of hash values first appeared on John D. Cook.

Here's something I've wondered about before: are there good mnemonics for chemical element symbols? Some element symbols are based on Latin or German names and seem arbitrary to English speakers, such as K (kalium) for potassium or Fe (ferrum) for iron. However, these elements are very common and so their names and symbols are familiar. [...]The post Memorizing chemical element symbols first appeared on John D. Cook.

I ran across a blog post here that said a new record has been set for the largest compositorial prime. [1] OK, so what is a compositorial prime? It is a prime number of the form n! / n# + 1 where n# denotesn primorial,the product of the prime numbers no greater than n. The [...]The post Largest known compositorial prime first appeared on John D. Cook.

AlmostSure on X pointed out that log2 3 19/12, an approximation that's pretty good relative to the size of the denominator. To get an approximation that's as accurate or better requires a larger denominator for log2 5. log2 5 65/28 This above observations are correct, but are they indicative of a more general [...]The post log2(3) and log2(5) first appeared on John D. Cook.

The previous post talked about doing perfect shuffles: divide a deck in half, and alternately let one card from each half fall. It matters which half lets a card fall first. If the top half's bottom card falls first, this is called an in-shuffle. If the bottom half's bottom card falls first, it's called an [...]The post In-shuffles and out-shuffles first appeared on John D. Cook.

Take a deck of cards and cut it in half, placing the top half of the deck in one hand and the bottom half in the other. Now bend the stack of cards in each hand and let cards alternately fall from each hand. This is called a rifle shuffle. Random shuffles Persi Diaconis proved [...]The post Perfect and imperfect shuffles first appeared on John D. Cook.

Donald Knuth gives a public lecture each year around Christmas. This year was his 29th Christmas lecture, Adventures with Knight's Tours. I reproduced one of the images from his lecture. This is the knight's tour with the minimum number of obtuse angles, marked with red dots. The solution is unique, up to rotations and reflections. [...]The post Knight's tour with fewest obtuse angles first appeared on John D. Cook.

If the earth were a perfect sphere, down" would be the direction to the center of the earth, wherever you stand. But because our planet is a bit flattened at the poles, a line perpendicular to the surface and a line to the center of the earth are not the same. They're nearly the same [...]The post The center of the earth is not straight down first appeared on John D. Cook.

One of the things I found off-putting about category theory when I was first exposed to it was its reliance on the notion of collections" that are not sets. That seemed to place the entire theory on dubious foundations with paradoxes looming around every corner. It turns out you can mostly ignore such issues in [...]The post Interesting categories are big first appeared on John D. Cook.

One of my daughters gave me a Klein bottle for Christmas. Imagine starting with a cylinder and joining the two ends together. This makes a torus (doughnut). But if you twist the ends before joining them, much like you twist the ends of a rectangular strip to make a Mobius strip, you get a Klein [...]The post Klein bottle first appeared on John D. Cook.

It's been said whatever you can validate, you can automate. An AI that produces correct work 90% of the time could be very valuable, provided you have a way to identify the 10% of the cases where it is wrong. Often verifying a solution takes far less computation than finding a solution. Examples here. Validating [...]The post Automation and Validation first appeared on John D. Cook.

Newton's birthday was on Christmas when he was born, but now his birthday is not. When Newton was born, England was still using the Julian calendar, and would continue to use the Julian calendar until 25 years after his death. On the day of Newton's birth, his parents would have said the date was December [...]The post When was Newton born? first appeared on John D. Cook.

A few weeks ago I mentioned that I was reading Stephen Ambrose's account of the Lewis & Clark expedition and wrote a post about their astronomical measurements. James Campbell left a comment recommending Edwin Danson's book [1] on the history of the Mason-Dixon line. I ordered the book, and now that work has slowed down [...]The post Mason, Dixon, and Latitude first appeared on John D. Cook.

I recently learned of Bowie's numerical method for solving ordinary differential equations of the form y'' = f(y) via Alex Scarazzini's masters thesis [1]. The only reference I've been able to find for the method, other than [1], is the NASA Orbital Flight Handbook from 1963. The handbook describes the method as a method employed [...]The post Bowie integrator and the nonlinear pendulum first appeared on John D. Cook.

The first difficulty in trying to fit an exponential distribution to data is that the data may not follow an exponential distribution. Nothing grows exponentially forever. Eventually growth slows down. The simplest way growth can slow down is to follow a logistic curve, but fitting a logistic curve has its own problems, as detailed in [...]The post Trying to fit exponential data first appeared on John D. Cook.

A logistic curve, sometimes called an S curve, looks different in different regions. Like the proverbial blind men feeling different parts of an elephant, people looking at different segments of the curve could come to very different impressions of the full picture. It's naive to look at the left end and assume the curve will [...]The post Trying to fit a logistic curve first appeared on John D. Cook.

One of the fiddly parts of regular expressions is how to handle line breaks. Should regular expression searches be applied one line at a time, or should an entire file be treated as a single line? This morning I was trying to track down a LaTeX file that said discussed in the Section" rather than [...]The post Regular expressions that cross lines first appeared on John D. Cook.

Here's a curious theorem I stumbled across recently [1]. Take an integerN which is not a multiple of 10. Then there is some multiple ofN which only contains the digits 1, 2, 3, 4, and 5. For example, my business phone number 8324228646 has a couple 8s and a couple 6s. But 6312 * 8324228646 [...]The post Multiples with no large digits first appeared on John D. Cook.

The expression converges to the golden ratio . Another way to say this is that the sequence defined by x0 = 1 and for n > 0 converges to . This post will be about how it converges. I wrote a little script to look at the error in approximating by xn and noticed [...]The post Golden iteration first appeared on John D. Cook.