An integral theorem of Gauss

Posted on 31 August 2025 by John

Gauss proved in 1818 that the value of integral

$\int_0^{\pi/2} \left( x^2 \sin^2\theta + y^2 \cos^2 \theta \right)^{-1/2} \, d\theta$

is unchanged if x and y are replaced by (x + y)/2 and √(xy), i.e. if you replaced x and y with their arithmetic mean and geometric mean [1].

So, for example, if you wanted to compute

$\int_0^{\pi/2} \left( 9 \sin^2\theta + 49 \cos^2 \theta \right)^{-1/2} \, d\theta$

you could instead compute

$\int_0^{\pi/2} \left( 25 \sin^2\theta + 21 \cos^2 \theta \right)^{-1/2} \, d\theta$

Notice that the coefficients of sin² θ and cos² θ are more similar in the second integral. It would be nice if the two coefficients were equal because then the integrand would be a constant, independent of θ, and we could evaluate the integral. Maybe if we apply Gauss’ theorem again and again, the coefficients will become more nearly equal.

We started with x = 3 and y = 7. Then we had x = 5 and y = √21 = 4.5826. If we compute the arithmetic and geometric means again, we get x = 4.7913 and y = 4.7874. If we do this one more time we get x = y = 4.789013. The values of x and y still differ, but only after the sixth decimal place.

It would seem that if we keep replacing x and y by their arithmetic and geometric means, we will converge to a constant. And indeed we do. This constant is called the arithmetic-geometric mean of x and y, denoted AGM(x, y). This means that the value of the integral above is π/ (2 AGM(x, y)). Because the iteration leading to the AGM converges quickly, this provides an efficient numerical algorithm for computing the integral at the top of the post.

This is something I’ve written about several times, though in less concrete terms. See, for example, here. Using more advanced terminology, the AGM gives an efficient way to evaluate elliptic integrals.

[1] B. C. Carlson, Invariance of an Integral Average of a Logarithm. The American Mathematical Monthly, Vol. 82, No. 4 (April 1975), pp. 379–382.

An uncrossed knight’s tour

Posted on 29 August 2025 by John

I’ve written several times about knight’s tours of a chessboard. The paths in these tours cross each other many times. What if you wanted to look tours that do not cross themselves? You can’t reach every square this way. You can reach half of them, but no more than half.

The following tour is part of the article Uncrossed Knight’s Tours in Donald Knuth’s book Selected Papers on Fun & Games.

Probability of typing a wrong Bitcoin address

Posted on 28 August 2025 by John

I heard someone say that Bitcoin is dangerous because you could easily make a typo when entering an address, sending money to the wrong person, and have no recourse. There are dangers associated with Bitcoin, such as losing a private key, but address typos are not a major concern.

Checksums

There are several kinds of Bitcoin addresses. Each is at least 20 bytes (160 bits) long, with at least 4 bytes (32 bits) of checksum. The chances of a typo resulting in a valid checksum are about 1 in 2³².

Used addresses

Let’s ignore the checksum for this section.

Because addresses are formed by cryptographic hash functions, we can assume the values are essentially randomly distributed in the space of possible addresses. The addresses are deterministic, but for modeling purposes, random is as random does.

This means a typo of an actual address is no more or less likely to be another actual address than an address typed at random. This is unlike, say, English words: a mistyped English word is more likely to be another English word than random keystrokes would be.

There have been on the order of a billion Bitcoin addresses used, in a space of 2¹⁶⁰ possibilities. (Actually more since some addresses have more than 160 bits.) There’s about a 1 in 10³⁹ chance that a random 160-bit sequence corresponds to an address somewhere on the Bitcoin blockchain.

If you sent money to a non-existent address, you still lose your money, but it’s extremely unlikely that you would accidentally send money to a real address that you didn’t intend.

Addresses close in edit distance

Someone with the Caesarean handle Veni Vidi Vici on X asked

What about the odds that out of those 1B addresses, two of them are one character swap away from each other?

That’s an interesting question. Let’s assume the addresses are Base58-encoded strings of length 26. Addresses could be longer, but assuming the minimum length increases the probability of addresses being close.

How many addresses are within one or two character swaps of another? I addressed a similar question here a couple weeks ago. If all the characters were unique, the number of strings within k swaps of each other would be

|S₁(26, 26 − k)|

where S₁ denotes Stirling numbers of the first kind. For k = 1 this would be 325 and for k = 2 this would be 50,050. This assumes all the characters are unique; I haven’t thought through the case where characters are repeated.

For round numbers, let’s say there are a billion addresses, and for each address there are a million other addresses that are close in some sense, plausible typos of the address. That would be 10¹² addresses and typos, spread out in a space of ≈10⁴⁵ (i.e. 58²⁶) possible addresses.

Now there’s an implicit Birthday Problem here. No particular address is likely to collide with another, even when you allow typos, but what about the likelihood that some address collides?

Say we partition our space of 10⁴⁵ addresses into N = 10²⁹ addresses with a million possible typos for each address. Then as a rule of thumb, you’d need around √N random draws before you have a 50-50 chance of seeing a collision. Since 10⁹ is a lot less than 10^14.5, it’s unlikely that any two addresses collide, even when you consider each address along with a million associated typos.

The biggest math symbol

Posted on 27 August 2025 by John

The biggest math symbol that I can think of is the Riemann P-symbol

$w(z)=P \left\{ \begin{matrix} a & b & c & \; \\ \alpha & \beta & \gamma & z \\ \alpha^\prime & \beta^\prime & \gamma^\prime & \; \end{matrix} \right\}$

The symbol is also known as the Papperitz symbol because Erwin Papperitz invented the symbol for expressing solutions to Bernard Riemann’s differential equation.

Before writing out Riemann’s differential equation, we note that the equation has regular singular points at a, b, and c. In fact, that is its defining feature: it is the most general linear second order differential equation with three regular singular points. The parameters a, b, and c enter the equation in the as roots of an expression in denominators; that’s as it has to be if these are the singular points.

The way the Greek letter parameters enter Riemann’s equation is more complicated, but there is a good reason for the complication: the notation makes solutions transform as simply as possible under a bilinear transformation. This is important because Möbius transformations are the conformal automorphisms of the Riemann sphere.

To be specific, let

$m(z) = \frac{Az + B}{Cz + D}$

be a Möbius transformation. Then

$P \left\{ \begin{matrix} a & b & c & \; \\ \alpha & \beta & \gamma & z \\ \alpha^\prime & \beta^\prime & \gamma^\prime & \; \end{matrix} \right\} = P \left\{ \begin{matrix} m(a) & m(b) & m(c) & \; \\ \alpha & \beta & \gamma & m(z) \\ \alpha^\prime & \beta^\prime & \gamma^\prime & \; \end{matrix} \right\}$

Since the parameters on the top row of the P-symbol are the locations of singularities, when you transform a solution, moving the singularities, the new parameters have to be the new locations of the singularities. And importantly the rest of the parameters do not change.

Now with the motivation aside, we’ll write out Riemann’s differential equation in all its glory.

$\frac{d^2w}{dz^2} + p(z) \frac{dw}{dz} + q(z) \frac{w}{(z-a)(z-b)(z-c)} = 0$

where

$p(z) = \frac{1-\alpha-\alpha^\prime}{z-a} + \frac{1-\beta-\beta^\prime}{z-b} + \frac{1-\gamma-\gamma^\prime}{z-c}$

and

$q(z) = \frac{\alpha\alpha^\prime (a-b)(a-c)} {z-a} +\frac{\beta\beta^\prime (b-c)(b-a)} {z-b} +\frac{\gamma\gamma^\prime (c-a)(c-b)} {z-c}$

Variations on Knuth’s Twindragon

Posted on 25 August 2025 by John

A couple days ago I wrote about Donald Knuth’s expression for the twindragon fractal as a sum of powers of b = 1 − i.

Simone Conradi made a nice animation replacing (1 − i) with exp(2πit) (1 − i). The animation loops over values of t.

Here’s what you get when t = 0.3.

And here’s what you get when t = 0.4.

Intuition for Pick’s Theorem

Posted on 24 August 2025 by John

Pick’s theorem is a surprising and useful to find the area of a region formed by connecting dots on a grid. The area is simply

A = i + p/2 − 1

where i is the number of dots in the interior and p is the number of dots on the perimeter.

Example

For example, the in the figure below there are 11 black dots on the perimeter and 17 blue dots in the interior.

Therefore Pick’s theorem says the area of the figure is 17 + 11/2 − 1 = 21½.

Intuition

It makes sense that the area would be approximately i if the figure is very large. But why do you need to add half the dots on the perimeter and why do you subtract 1?

Pick’s theorem is simple, but it isn’t obvious. If it were obvious, someone closer to the time of Descartes (1596–1650) would have discovered it. Instead, the theorem was discovered by Georg Alexander Pick in 1899. However, the theorem is fairly obvious for a rectangle, and this post will illustrate that case. For a rectangle, you can easily see why you need to add half the perimeter dots and subtract 1.

Rectangular case

Imagine an m by n rectangular array of dots. If you were to draw a frame around those dots with the corners of the rectangle being exactly between dots, the area would be mn, the number of dots inside the frame.

Pick’s theorem does not apply here because the corners of our frame do not lie on the grid. So let’s shift our grid down and to the left so that its corners do lie on the grid.

Now some of our original dots, marked in blue, are on the perimeter of the frame. We could add the number of dots on the perimeter to correct for this, but that would be too much because the blue dots on the perimeter are only on the left and top sides. Each has a reflection on the right and bottom, marked with red dots. So we shouldn’t add all the dots on the perimenter, but only half the dots on the perimeter.

But that still overcounts slightly. There are two dots on the perimeter that do not correspond to a blue dot or to the reflection of a blue dot. These are the hollow circles in the top right and bottom left corners. So when we take half the perimeter, we need to subtract 1 to account for half of this pair of dots.

This doesn’t prove Pick’s theorem in general, but it does prove it for rectangular regions. Even if we can’t see why the formula generalizes to more complicated regions, we can be grateful that it does.

Knuth’s Twindragon

Posted on 23 August 2025 by John

A few days ago I wrote about a random process that creates a fractal known as the Twin Dragon. This post gives a deterministic approach to create the same figure.

As far as I can tell, the first reference to this fractal is in a paper by Davis and Knuth in the Journal of Recreational Mathematics from 1970. Unfortunately this journal is out of print and hard or impossible to find online [1]. Knuth presents the twindragon (one word, lowercase) fractal in TAOCP Vol 2, page 206.

Knuth defines the twindragon via numbers base b = 1 − i. Every complex number can be written in the form

$z = \sum_{k=-\infty}^\infty a_k (1 - i)^k$

where the “digits” a_k are either 0 or 1.

The twindragon fractal is the set of numbers that only have non-zero digits to the right of the decimal point, i.e. numbers of the form

$z = \sum_{k=1}^\infty a_k (1 - i)^{-k}$

I implemented this in Python as follows.

import matplotlib.pyplot as plt
from itertools import product

for bits in product([0, 1], repeat=15):
    z = sum(a*(1-1j)**(-k) for k, a in enumerate(bits))
    plt.plot(z.real, z.imag, 'bo', markersize=1)
plt.show()

This produced the image below.

[1] If you can find an archive of Journal of Recreational Mathematics, please let me know.

A recipe for creating random fractals

Posted on 21 August 2025 by John

Last week I gave an example of a randomly generated fractal and mentioned that it was “a particularly special case of a more general algorithm for generating similar fractals found in [1].”

Here’s the general pattern. First, create a non-singular matrix M with integer entries and let k be the determinant of M.

Let P be the parallelogram spanned by the columns of M. Choose a set of column vectors r_i for i = 1, 2, 3, …, k from the two columns of M and from the interior of P.

Pick a random starting vector v then iterate

v = M⁻¹ v + r_i

where i is chosen at random on each iterations.

Here’s an example suggested as an exercise in [2]. We start with

$M = \begin{bmatrix} 2 & -1 \\ 1 & \phantom{-}2 \end{bmatrix}$

and look at the parallelogram spanned by the columns of M.

NB: The initial version of this post had an error in the grid, which led to an error in the code, and produced a different fractal.

Then the algorithm described above is implemented in the following Python code.

import numpy as np
import matplotlib.pyplot as plt

A = np.linalg.inv(np.array([[2,  -1], [1, 2]]))
R = np.array([[2, -1, 0,  1, 1],
              [1,  2, 2,  2, 1]])

v = np.random.random(size=2)
for _ in range(100000):
    i = np.random.choice([0, 1, 2, 3, 4])
    v = np.dot(A, v) + R[:, i]
    plt.plot(v[0], v[1], 'bo', markersize=1)
plt.gca().set_aspect("equal")
plt.show()

This produces the following fractal.

[1] Darst, Palagallo, and Price. Fractal Tilings in the Plane. Mathematics Magazine [71]:1, 1998.

[2] Lorelei Koss, Fractal Rep-tiles and Geometric Series. Math Horizons. Vol 30, Issue 1, September 2022.

When log(x) has the same digits as x

Posted on 20 August 2025 by John

I was skimming through a book [1] the other day and saw the following three equations:

log 1.3712885742 = 0.13712885742
log 237.5812087593 = 2.375812087593
log 3550.2601815865 = 3.5502601815865

The sequence of digits is the same on both sides of each equation, except for the position of the decimal point.

The book said “The determination of such numbers has been discussed by Euler and by Professor Tait.” I don’t know who Professor Tait was, but I’ve heard of Euler. I’m curious why Euler was interested in this problem, whether it was idle curiosity inspired by looking up logarithms for some calculation or whether it was part of some larger exploration.

Evidently the logarithms above are taken base 10, and you could formulate the problem as finding solutions to

log₁₀ x = 10^k x

for integer k.

For a given k, how many solutions are there?

We could rephrase the question by looking for solutions to

log₁₀(log₁₀ x) − log₁₀ x = k.

A plot shows that the left side is always negative and takes on every negative integer value twice, so there are no solutions for non-negative integers and two solutions for each negative integer.

So, for example, when k = −3 there are two solutions. One is given at the top of the post. The other is x = 1.0023105706421267.

General bases

Would it make much difference if you were to generalize the problem to solving

log_b x = b^k x

for an arbitrary base b > 1?

Using the fact that

log_b x = ln x / ln b

and a little algebra we can formulate the question as looking for solutions to

ln (ln x) − ln x = ln (ln b) + k ln b.

The function on the left hand side takes on the value −1 once and it takes on every other negative integer value twice. The function on the right hand side is positive for positive k, which means no solutions exist in any base b > 1 when k = 0. There is one solution when k = −1 and b = e. Otherwise there are two solutions for negative integers k for each base b.

[1] A Scrap-Book of Elementary Mathematics: Notes, Recreations, Essays by William Frank White, 1908. Available on Project Gutenberg.

Connecting partial sums

Posted on 19 August 2025 by John

Today’s exponential sum, like all the exponential sums on the site, is formed by drawing a line between consecutive partial sums of a series involving complex exponentials. The exponential sum page makes an image each day by putting the day’s month, day, and year into a formula.

Here’s today’s image

based on the sum

$\sum_{n=0}^N \exp\left( 2\pi i \left( \frac{n}{8} + \frac{n^2}{19} + \frac{n^3}{25} \right ) \right )$

I use American-style dates—month, day, year—because that increases the day-to-day variety of the images compared to using the day in the first denominator.

Math

An integral theorem of Gauss

Related posts

An uncrossed knight’s tour

Related posts

Probability of typing a wrong Bitcoin address

Checksums

Used addresses

Addresses close in edit distance

The biggest math symbol

Related posts

Variations on Knuth’s Twindragon

Intuition for Pick’s Theorem

Example

Intuition

Rectangular case

Related posts

Knuth’s Twindragon

Related posts

A recipe for creating random fractals

When log(x) has the same digits as x

General bases

Connecting partial sums