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

2^b 3^c 7^d = 10^{-a}.

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

\{ (n \log 2, n \log 3, n \log 7) \}

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).

Data on Gelfand’s question