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.
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.
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½.
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.
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 perimeter, 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.
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
where the “digits” ak 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
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 few days ago I wrote about what’s in a crypto wallet. In that post I said that most crypto wallets now are hierarchical deterministic (HD) wallets. And I said that HD wallets are deterministic in the sense that they derive all their keys from a seed phrase. But in what sense are HD wallets hierarchical? That’s the topic of this post.
In the game of 20 questions, one person thinks of something and another tries to guess what it is by asking up to 20 yes-no questions. I once heard the physicist John Wheeler tell of a variation of this game in which the first person did not have a definite object in mind, but decided after each question what the answer should be. For example, if someone asks “Is this person a man?” the person would commit to the person being a man or woman, but would not decide on a particular man or woman yet.
Wheeler’s point was that quantum mechanics is like this variation on 20 questions in that the answers to questions don’t exist until the question is asked. What does this have to do with hierarchical deterministic wallets? Your private keys do not exist until you ask for them. But once you have created and used a key, a wallet will behave consistently with that creation.
The hierarchy referred to in a hierarchical deterministic wallet is a set of five variables, as described in BIP-44:
The meaning of the variables is explained in BIP-44. The lowest level, address index, is a sequential counter. So you can have separate sequential counters for each value of the four-tuple (purpose, coin type, account, change).
Your master key and the five variables above are inputs to a key derivation function used to create new keys as needed. Once you use a private key, a hash of its corresponding public key is memorialized on the blockchain. If it’s a Bitcoin transaction, it’s on the Bitcoin blockchain. If it’s an Ethereum transaction, it’s on the Ethereum blockchain, etc. (You can find a list of supported coin types here.)
You wallet does not (or at least logically need not) store all your keys. It can reason as follows. “If the master key and these hierarchical values were used, this would be the private key. And given this private key, this would be the public key, and this would be the corresponding address. Let me consult the blockchain to see whether in fact it was used.”
How would a wallet know how many transactions you’ve made under a particular branch of the hierarchy? It searches the corresponding blockchain. It first looks whether there is a ledger entry corresponding to address index 0. Then address index 1, etc. The algorithm allows for the possibility of gaps. If it cannot find a ledger entry corresponding to index 2, it looks for index 3, etc. up to a gap of 20. After looking ahead 20 index values and finding nothing, it concludes there is nothing else to be found.
Because everything is derived deterministically from the seed phrase and the hierarchical variables, you can back up a wallet by simply backing up the seed phrase.
In theory, you could carry out transactions using one brand of wallet, back it up by writing down the seed phrase, then restore the information to a different brand of wallet. In practice you may run into difficulty doing this.
Today I learned that the size and shape of a punch card
was chosen to be the same as US paper money at the time.
At the time a US bank note had dimensions 3.25″ by 7.375″. This was sometime prior to 1929 [1] when the size of a bank note changed to 2.61″ by 6.14″. Here’s a current US dollar to scale.
Thinking about how US bank notes shrank in size made me think about how they shrank in purchasing power as measured by the Consumer Price Index. I chose 1861 as my baseline because that’s when the US chose the bank note dimensions above.
Here’s a plot.
Curiously, the ratio of purchasing power to area in 1940 almost returned to what it had been in the 1800s.
In 2025, $1 has about 3% of the purchasing power of $1 in 1861. To maintain the same purchasing power per square inch, a $1 note in 2025 should have an area of 0.72 square inches. To maintain the current aspect ratio, this would be 0.55″ by 1.3″.
[1] Punch cards have been around longer than electronic computers. Their first large-scale application was tabulating the 1890 US census.
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 ri 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−1 v + ri
where i is chosen at random on each iterations.
Here’s an example suggested as an exercise in [2]. We start with
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.
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
log10 x = 10k x
for integer k.
For a given k, how many solutions are there?
We could rephrase the question by looking for solutions to
log10(log10 x) − log10 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.
Would it make much difference if you were to generalize the problem to solving
logb x = bk x
for an arbitrary base b > 1?
Using the fact that
logb 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.
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
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.
A couple days ago I wrote about how you might go about trying to recover a seed phrase that you had remembered out of order. I said that the list of seed phrase words had been designed to be distinct. Just out of curiosity I computed how similar the words are using Levenshtein distance, also known as edit distance, the number of single character edits it takes to turn one word into another.
A lot of the words—484 out of 2048—on the BIP39 list differ from one or more other words by only a single character, such as angle & ankle, or loud & cloud. The word wine is one character away from each of wing, wink, wire, and wise.
Edit distance may not the best metric to use because it measures differences in text representation. It’s more important for words to be conceptually or phonetically distinct than to be distinct in their spelling. For example, the pair donkey & monkey differ by one letter but are phonetically and conceptually distinct, as are the words live & olive.
Some pairs of words are very similar phonetically. For example, I wouldn’t want to have to distinguish or cannon & canyon over a phone call. The list is not good for phonetic distinction, unlike say the NATO alphabet.
For ease of memorization, you want words that are vivid and concrete, preferably nouns. That would rule out pairs like either & neither.
The BIP39 list of words is standard. But other approaches, such as Major system encoding, are more optimized for memorability.
It’s hard to make a long list of words distinct by any criteria, and 2048 is a lot of words. And the words on the list are intended to be familiar to everyone. Adding more vivid or distinct words would risk including words that not everyone would know. But still, it seems like it might have been possible to create a better word list.
The earlier post discussed how to recover a seed phrase assuming that all the words are correct but in the wrong order. It would make sense to explore sequences in order of permutation distance, assuming that small changes to the order are more likely than large changes.
But if it’s possible that the words are not correct, you might try looking at words in edit distance order. For example, “You said one of the words was race. Could it have been rice?”
I recently ran across an article by Katherine Stange [1] on Lehmer’s factoring stencils [2]. These stencils were the basis of an effective method for factoring moderately large numbers before the advent of electronic computers.
This post will describe the stencils and simulate their use with a Python script.
When I started reading [1] I had three misconceptions that slowed down my understanding of the article. I’ll address these first in case any of you come to this article with the same unhelpful expectations.
First, when I saw something about using stencils for factoring I thought they would be something like a Sieve of Eratosthenes, stencils with multiples of 2, 3, 5, etc. cut out. That is not what’s going on; Lehmer’s method is more sophisticated than that.
Second, related to the first, I thought that the factoring method would involve placing stencils on top of a large grid of numbers that included the number you wanted to factor. That is also not the case. The stencils can be used to factor nine-digit numbers, and a sheet of over a billion numbers would not be practical.
Third, I thought there might be some geometric significance to the position of the holes in the circular stencils. There isn’t. The stencils were circular for convenience.
Lehmer made a set of 295 stencils. Katherine Stange has put a set of SVG files for such stencils on her Github repo. The image below is the stencil corresponding to the number 42.
I want focus on how the stencils work, not why they work.
To factor a number N, you would first find a handful of numbers X1, X2, X3, … Xk, related to N, numbers that are fairly easy to compute by hand. Then you would stack the stencils corresponding to the Xi and hold the stack up to the light.
If y is a quadratic residue mod N, then y is a quadratic residue mod each of the prime factors of N. Each stencil cuts the number of potential prime factors by about a half.
Once you found a probable prime factor, you would test it by long division, and then you know with certainty whether the number is a factor.
So what are these Xi and what are the holes in them?
The Xi are quadratic residues mod N, i.e. numbers such that
Xi = x² mod N
has a solution. This would have required some hand calculation, but not nearly as much calculation as trying to factor N unaided. A couple algorithms for finding quadratic residues are described in this video and in this PDF by Katherine Stange.
NB: The hard part isn’t finding quadratic residues mod N; you could do that by squaring random integers mod N. The hard part is finding quadratic residues that correspond to your set of available stencils.
The holes in the stencil correspond to the prime numbers up to 48593. Disk X has a hole for prime p if X is a quadratic residue mod X. If X is a quadratic residue mod p and mod N, there’s a 50-50 chance p divides N.
The number 48593 is the 4999th prime, so there are locations on each disk corresponding to 4999 primes. Lehmer arranged these locations in a spiral, but they could have been laid out in a grid or any other pattern.
See the Github repo referenced above for Python code to make the SVG files for the physical stencils. The Python code below simulates the operation of the stencils, not their geometry. I wrote the code to be illustrative, not to be practical efficient code for factoring integers.
First, here’s code to make our stencils. Here a 1 corresponds to a hole.
from sympy import primerange, legendre_symbol
from numpy import array
primes = array([p for p in primerange(3, 48594)])
def stencil(x):
# stencil has a 1 in position k if x is a quadratic residue
# modulo the kth odd prime and a 0 otherwise
return array([1 if legendre_symbol(x, p) >= 0 else 0 for p in primes])
Next we pick an N and a few small quadratic residues mod N.
N = 19972009 x = [2, 61, 79, 185, 238, 255, 313, 421, 491]
Multiplying the stencils together produces a 1 where every stencil has a hole.
mask = stencil(x[0])
for i in range(1, len(x)):
mask *= stencil(x[i])
ps = mask*primes
print(ps[ps != 0])
This prints the following:
[ 97 103 1367 1999 15241 28351 35353 36847 44953]
We then test whether each of these primes is a factor of N, and in fact
19972009 = 97 × 103 × 1999.
Each stencil has 4999 primes, and if each of the 9 stencils eliminates about half the potential prime factors, we’d expect around 4999/29 ≈ 10 candidate primes, which is very close to what we got.
[1] The Ingenious Physical Factoring Devices of D. N. Lehmer. Math Horizons. Volume 30 Issue 2. November 2022.
[2] D. N. Lehmer and his son D. H. Lehmer were both number theorists. I’ve referred to the later several times on the blog, most recently here. I also cited Katherine Stange a couple weeks ago.