2025-08-22 22:13:36
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.
The post Punch Cards and Dollar Bills first appeared on John D. Cook.2025-08-21 21:55:33
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.
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, 1, 1, 0],
[1, 2, 0, -1, -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.
The post A recipe for creating random fractals first appeared on John D. Cook.2025-08-20 19:54:37
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
log10x = 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(log10x) − log10x = 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.
The post When log(x) has the same digits as x first appeared on John D. Cook.2025-08-19 19:22:03
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.
The post Connecting partial sums first appeared on John D. Cook.2025-08-19 04:31:43
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?”
2025-08-18 02:58:17
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.
The post Factoring Stencils first appeared on John D. Cook.
