Gelfand’s Question
by David Radcliffe
Gary Davis (@republicofmath) has brought my attention to a question that has been attributed to Israel Gelfand: What are the possible sequences of leftmost digits of 2n, 3n, 4n, 5n, 6n, 7n, 8n, 9n?
For example, when n = 2 the sequence of powers is 4, 9, 16, 25, 36, 49, 64, 81
and the sequence of leftmost digits is 4, 9, 1, 2, 3, 4, 6, 8.
The leading digit of kn is determined by the fractional part of n*log(k), where log denotes the base 10 logarithm. There are dependencies between the columns, resulting from the following identities.
log(4) = 2 * log(2)
log(5) = 1 – log(2)
log(6) = log(2) + log(3)
log(8) = 3 * log(2)
log(9) = 2 * log(3)
Therefore, the pattern of leftmost digits is completely determined by
the fractional parts of n*log(2), n*log(3), and n*log(7).
I claim that the set {1, log(2), log(3), log(7)} is linearly independent over the rational numbers. This means that if a, b, c, d are rational numbers such that
a + b log(2) + c log(3) + d log(7) = 0,
then a = b = c = d = 0.
This is easy to prove. By clearing fractions, we can assume that a, b, c, and d are integers. Exponentiating both sides with a base of 10 yields
By unique factorization, we conclude that a = b = c = d = 0.
Since {1, log(2), log(3), log(7)} are linearly independent over the rational numbers, Kronecker’s theorem implies that the set of points
is dense modulo 1. (This theorem is proved in Hardy & Wright.)
Therefore, it suffices to find the patterns of leading digits as the fractional parts of n*log(2), n*log(3), and n*log(7) range independently over the interval [0,1). We can reduce this to a finite computation by subdividing the unit cube into appropriate regions. The result of this computation is that there are 18,226 distinct patterns of leading digits (see attached file).
The MathWorld article lists four specific questions about these patterns of digits.
1. Will the digit 9 ever occur in the 2^n column? [Yes, as explained in the article.]
2. Will the row “23456789” ever appear for n > 1? [No. If the leading digit of 2^n is 2, then the leading digit of 5^n must be 3 or 4, since 2^n * 5^n = 10^n.]
3. Will a row of all the same digit occur? [No. If 2^n and 5^n have the same leading digit, then this digit must be 3, but then the leading digit of 4^n will be 9 or 1.]
4. Will the decimal expansion of an 8-digit prime ever occur? [Yes. In fact, 1179 distinct primes will occur. The smallest prime that occurs is 11171621 and the largest prime is 99919399.]
[…] a short and lovely mathematical argument, Dave Radcliffe (@daveinstpaul) proves that there are exactly 18266 distinct ordered lists of […]
I have been informed that my list contains numerous errors, but I haven’t confirmed this. I will post an update when I am able to resolve this issue.
The March 2015 issue of the American Mathematical Monthly contains an article about this problem coauthored by David. According to the article, there are actually 17,596 patterns of leading digits of which 1127 are prime.