Gelfands’s question asks whether there is a positive integer *n* such that the first digits of *j*^{n} base 10 are all the same for *j* = 2, 3, 4, …, 9. (Thanks to @republicofmath for pointing out this problem.) This post will explore Gelfand’s question via probability.

The MathWorld article on Gelfand’s question says that the answer is no for values of *n* less than 100,000. That range seemed small to me. My intuition was that you’d need to try larger values of *n* to have a reasonable chance of finding a solution.

So how big a value of *n* should you explore? To answer that question, consider picking *n* at random. If the leading digits of *j*^{n} were randomly distributed, what would the chances be that *n* would satisfy Gelfand’s question? Leading digits are not random, but they do often have regular distributions.

Suppose the leading digits are uniformly distributed among 1 to 9, and that the leading digits for each base are independent. Then the probability of *j*^{n} beginning with 1 (or any other chosen digit) for all *j* from 2 to 9 would be (1/9)^{8}, and the probability of all leading digits matching any digit would be 9 times larger. That would say the probability of all leading digits matching would be on the order of 2 × 10^{-7}, so we should try on the order of 10^{7} or 10^{8} values of *n* to have a decent chance of finding one.

But there’s a problem with the above argument: leading digits are not uniformly distributed. Benford’s law says that leading digits are often distributed very unevenly. When a system follows Benford’s law, the probability of a leading digit being *d* is log_{10}(1 + 1/*d*). An uneven distribution of leading digits raises the probability that all the digits will match. If the leading digits of *j*^{n} follow Benford’s law, and are independent, then the probability of all matching is 6.84 × 10^{-5}, two orders of magnitude higher than assuming a uniform distribution.

Do the leading digits of *j*^{n} follow Benford’s law? Yes, at least approximately, based on testing values of *n* from 1 to 1,000.

Now suppose the probability of a randomly selected value of *n* satisfying Gelfand’s question is *p* = 6.84 × 10^{-5}. If we tried 100,000 random values of *n*, the probability of having no successes would be about 0.00107. So my intuition was wrong. If the random heuristic given here were correct, we’d stand a good chance of seeing a solution if we tried values of *n* up to 100,000.

Where does the probabilistic heuristic go wrong? In the assumption that the distributions of the leading digits are independent.

Let *x*_{j} be the sequence *j*^{n} for *n* running from 1 to 1000. Some of the *x*_{j} are correlated and some are not.

Some of the correlations are easy to see. For example, the sequences for *x*_{2} and *x*_{4} have correlation 0.493. That’s because 4^{n} = (2^{n})^{2}. So if you know the first digit of 2^{n}, you can often guess the first digit of 4^{n}. In light of this, it’s not surprising that *x*_{2} is also correlated with *x*_{8}, and *x*_{3} is correlated with *x*_{9}.

You might speculate that *x*_{j} and *x*_{k} are uncorrelated if and only if *j* and *k* are relatively prime. Some sequences, such as *x*_{2} and *x*_{3} support that guess. But *x*_{4} and *x*_{5} are negatively correlated, *r* = -0.433, for reasons that are not obvious. I suspect that the negative correlations are the key to understanding the question.

* * *

**Update**: I have verified that the answer to Gelfand’s question is no for *n* up to 10^{10}.

I’m not going to give away the answer, but there are some choices of $i, j, k, l$ for which $x_i = j, x_k = l$ is in fact impossible, for “number-theoretic” reasons. I suspect the probabilistic approach would work better in a prime base, just because there’s less of this to worry about.

Small correction: fourth paragraph, the probability should be 2 × 10^-7, not 2 × 10^7, as 2 × 10^7 is *much* bigger than 1!! 😛

Thanks!

I think that there may be some hope of using continued fractions to explore this. It seems certain that the most likely value that each power could have as a leading digit is 1 (indeed, I rather doubt that there would be other possible solutions, but haven’t proved this yet: clearly, though, for example, if 2^n leads with 2, then 4^n leads with a number between 4 and 8: I haven’t yet ruled out 8 and 9 as possibilities, but I think that can be done)

It may be worth noting, lest anyone be tempted to expend trouble and computer time extending John’s calculation to values beyond 10^10, that the sort of number-theoretical reasoning Michael Lugo mentions suffices to resolve the question of whether you can ever have all of 2^n, …, 9^n beginning with the same digit.

Why not search for k such that the kth digit of log 2, …, log9 is the same (or a neighbor) and then find n from that? Given the relationship between the numbers (8 is 2^3, for instance), that digit would have to be 0 or, less likely, 9.

If you think about that, I think it’s clear that searching for k one by one will take a long time. At best I’d expect to find some n with hundreds of thousands of digits, but more likely (I think) in the order of a hundred million digits.