Gelfand’s question

Gelfands’s question asks whether there is a positive integer n such that the first digits of jn 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 jn 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 jn 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 107 or 108 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 log10(1 + 1/d). An uneven distribution of leading digits raises the probability that all the digits will match. If the leading digits of jn 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 jn 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 xj be the sequence jn for n running from 1 to 1000. Some of the xj are correlated and some are not.

Some of the correlations are easy to see. For example, the sequences for x2 and x4 have correlation 0.493. That’s because 4n = (2n)2. So if you know the first digit of 2n, you can often guess the first digit of 4n. In light of this, it’s not surprising that x2 is also correlated with x8, and x3 is correlated with x9.

You might speculate that xj and xk are uncorrelated if and only if j and k are relatively prime. Some sequences, such as x2 and x3 support that guess. But x4 and x5 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 1010.

Tagged with: ,
Posted in Math
6 comments on “Gelfand’s question
  1. Michael Lugo says:

    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.

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

  3. John says:

    Thanks!

  4. Neil says:

    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)

  5. g says:

    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.

  6. Andre U. Manoel says:

    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.