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.

When I was a kid, I suppose sometime in my early teens, I was interested in music theory, but I couldn't play piano. One time I asked a lady who played piano at our church to play a piece of sheet music for me so I could hear how it sounded. The music was in [...]The post Just change the key first appeared on John D. Cook.

Say you have a common 6-sided die and need to roll it until the sum of your rolls is at least 6. How many times would you need to roll? If you had a 20-sided die and you need to roll for a sum of at least 20, would that take more rolls or fewer [...]The post Rolling n-sided dice to get at least n first appeared on John D. Cook.

There are numerous memes floating around with the words Being weak is nothing to be ashamed of; staying weak is." Or some variation. I thought about this meme in the context of weak derivatives. The last couple posts have talked about distributions, also called generalized functions. The delta function, for example, is not actually a [...]The post Weak derivatives first appeared on John D. Cook.

The previous post showed how we can take the Fourier transform of functions that don't have a Fourier transform in the classical sense. The classical definition of the Fourier transform of a function f requires the integral of |f| over the real line to be finite. This implies f(x) must approach zero as x goes [...]The post Fourier transform of a Fourier series first appeared on John D. Cook.

Suppose you have a constant function f(x) = c. What is the Fourier transform of f? We will show why the direct approach doesn't work, give two hand-wavy approaches, and a rigorous definition. Direct approach Unfortunately there are multiple conventions for defining the Fourier transform. For this post, we will define the Fourier transform of [...]The post Fourier transform of a flat line first appeared on John D. Cook.

The weakest link in the privacy of cryptocurrency transactions is often outside the blockchain. There are technologies such as stealth addresses and subaddresses to try to thwart attempts to link transactions to individuals. They do a good job of anonymizing transaction data, but the weak link may be metadata, as is often the case. Cryptocurrency [...]The post Obscuring P2P nodes with Dandelion first appeared on John D. Cook.

I'm taking a break from my series on celestial navigation. The previous posts give the basics, but I haven't thought of a way to go further that I'm satisfied with. So now for something completely different: Pedersen commitments. Pedersen commitments are a building block of zero knowledge proofs (ZKP), and they give an opportunity to [...]The post What is a Pedersen commitment? first appeared on John D. Cook.

This post is a side quest in the series on navigating by the stars. It expands on a footnote in the previous post. There are six pieces of information associated with a spherical triangle: three sides and three angles. I said in the previous post that given three out of these six quantities you could [...]The post Solving spherical triangles first appeared on John D. Cook.

The previous post introduced the idea of finding your location by sighting a star. There is some point on Earth that is directly underneath the star at any point in time, and that location is called the star's GP (geographic position). That is one vertex of the navigational triangle. The other two vertices are your [...]The post The Navigational Triangle first appeared on John D. Cook.

The previous post touched on how Lewis and Clark recorded celestial observations so that the data could be turned into coordinates after they returned from their expedition. I intend to write a series of posts about celestial navigation, and this post will discuss one fundamental topic: line of position (LOP). Pick a star that you [...]The post Line of position (LOP) first appeared on John D. Cook.

I read Undaunted Courage, Stephen Ambrose's account of the Lewis and Clark expedition, several years ago [1], and now I'm listening to it as an audio book. The first time I read the book I glossed over the accounts of the expedition's celestial observations. Now I'm more curious about the details. The most common way [...]The post Lewis & Clark geolocation first appeared on John D. Cook.

A zero knowledge proof (ZKP) answers a question without revealing anything more than answer. For example, a digital signature proves your possession of a private key without revealing that key. Here's another example, one that's more concrete than a digital signature. Suppose you have a deck of 52 cards, 13 of each of spades, hearts, [...]The post Zero knowledge proof of compositeness first appeared on John D. Cook.

Monero has a way of generating new addresses analogous to the way HD wallets generate new addresses for Bitcoin. In both cases, the recipient's software can generate new addresses to receive payments that others cannot link back to the recipient. Monero users have two public/private keys pairs: one for viewing and one for spending. Let [...]The post Monero subaddresses first appeared on John D. Cook.

Spherical geometry In spherical geometry, the interior angles of a triangle add up to more than . And in fact you can determine the area of a spherical triangle by how much the angle sum exceeds . On a sphere of radius 1, the area equals the triangle excess Area = E = interior angle [...]The post A triangle whose interior angles sum to zero first appeared on John D. Cook.

Let be the upper half plane, the set of complex real numbers with positive imaginary part. When we measure distances the way we've discussed in the last couple posts, the geometry of is hyperbolic. What is a circle of radius r in ? The same as a circle in any geometry: it's the [...]The post A circle in the hyperbolic plane first appeared on John D. Cook.

The previous post described a metric for the Poincare upper half plane. The development is geometrical rather than analytical. There are also analytical formulas for the metric, at least four that I've seen. It's not at all obvious that the four equations are equivalent, or that any of them matches the expression in the previous [...]The post Equal things that don't look equal first appeared on John D. Cook.

One common model of the hyperbolic plane is the Poincare upper half plane . This is the set of points in the complex plane with positive imaginary part. Straight lines are either vertical, a set of points with constant imaginary part, or arcs of circles centered on the real axis. The real axis is not [...]The post Hyperbolic metric first appeared on John D. Cook.

The opening line of William Gibson's novel Neuromancer is famous: The sky above the port was the color of a television, tuned to a dead channel. When I read this line, I knew immediately what he meant, and thought it was a brilliant line. Later I learned that younger readers didn't know what he was [...]The post TV tuned to a dead channel first appeared on John D. Cook.

Suppose Alice runs a confidential restaurant. Alice doesn't want there to be any record of who visited her restaurant but does want to get paid for her food. She accepts Monero, and instead of a cash register there are two QR codes on display, one corresponding to her public view keyA and the other corresponding [...]The post How stealth addresses work in Monero first appeared on John D. Cook.

I was reading about Shackleton's incredible expedition to Antarctica, and the Weddell Sea features prominently. That name sounded familiar, and I was trying to remember where I'd heard of Weddell in math. I figured out that it wasn't Weddell exactly but Weddle I was thinking of. The Weddell Sea is named after James Weddell (1787-1834). [...]The post Weddle integration rule first appeared on John D. Cook.

The previous post includes code for solving the equation Hn = m i.e. finding the value ofn for which thenth harmonic number is the closest tom. It works well for small values ofm. It works for largem in the sense that the solution is very close tom, but it's not necessarily the best solution. For [...]The post Solving H_n = 100 first appeared on John D. Cook.

I mentioned in the previous post that the harmonic numbers Hn are never integers for n > 1. In the spirit of that post, I'd like to find the value of n such that Hn is closest to a given integer m. We have two problems to solve. First, how do we accurately and efficiently [...]The post Closest harmonic number to an integer first appeared on John D. Cook.

Jozsef Kurschak proved in 1908 that the function is never an integer for 0 < m < n. In particular, the harmonic numbers are never integers for n > 1. The function f(m,n) can get arbitrarily close to any integer value by taking m andn large enough, but it can never exactly equal an integer. [...]The post Closest consecutive reciprocal sum to an integer first appeared on John D. Cook.

Five posts on Pythagorean triangles and Pythagorean triples Primitive Pythagorean triangles with the same area Sparse binary Pythagorean triples Matrix Pythagorean triples Approximation by Pythagorean triangles Fibonacci meets PythagorasThe post Pythagorean triples first appeared on John D. Cook.

The last couple posts have been about group pairings, specifically Tate pairings as they're used in cryptography. This post will show that RSA encryption can be seen as a special case of pairing-based cryptography. The idea comes from Ben Lynn's 2007 dissertation. Lynn is the L" in BLS signatures-one of the topics in his dissertations-and [...]The post RSA as a pairing first appeared on John D. Cook.