Professor Halfbrain and the powers of 2016

Question

Yesterday I met professor Halfbrain at the coffee house. The professor told me that he had been spending his time with computing powers of $2016$ and combining them with powers of $32$. The professor was happy to report that after many hours of computing and computing and computing, he had managed to prove the following theorem.

Professor Halfbrain's theorem: For every integer $n\ge1$, the decimal representation of the number $2016^n$ has the same number of digits as the decimal representation of $2016^n+32^n$.

Is Halfbrain's theorem indeed true, or has the professor once again made one of his well-known mathematical blunders?

Answer 1

This answer is an improvement on Milo Brandt's answer, and is based on "Formes linéaires en deux logarithmes et déterminants d′interpolation" (M. Laurent, M. Mignotte, and Y. Nesterenko) (which I got from this MathOverflow answer).

We will prove Professor Halfbrain's theorem by contradiction. Suppose that there is some $n$ for which the theorem does not hold. Then we must have:

$$ 2016^n + 32^n \ge 10^k > 2016^n $$

for some integer $k$. That is, when adding $32^n$ we must have "passed over" a power of ten in order to increase the number of digits. Like Milo, we start by taking logarithms:

$$ \log\left(2016^n + 32^n\right) > k\log 10 \ge n\log 2016 $$

This step is valid since all parts of the inequality are positive, and $\log x$ is strictly increasing for all $x>0$. The logarithm is also strictly concave, which means that it is "bounded above by its first-order Taylor approximation"; that is:

$$ \log(x) < \log(x_0) + \log'(x_0)(x-x_0) = \log(x_0) + \frac{x-x_0}{x_0},\ x \ne x_0 \\ \log(x_0+y) < \log(x_0) + \frac{y}{x_0},\ y \ne 0 $$

Thus, we can write:

$$ \log\left(2016^n + 32^n\right) < n\log 2016 + \frac{32^n}{2016^n} = n \log 2016 + 63^{-n} \\ $$

We can add this to our previous inequality:

$$ n \log 2016 + 63^{-n} > \log\left(2016^n + 32^n\right) > k\log 10 \ge n\log 2016 $$

This means that a counterexample to Professor Halfbrain's theorem, which must satisfy our original inequality, also satisfies the weaker inequality:

$$ n \log 2016 + 63^{-n} > k\log 10 \ge n\log 2016 $$

We can weaken this inequality even further by subtracting $63^{-n}$ from the right-hand side:

$$ n \log 2016 + 63^{-n} > k\log 10 > n\log 2016 - 63^{-n} \\ 63^{-n} > k\log 10 - n \log 2016 > - 63^{-n} \\ 63^{-n} > \left| k\log 10 - n \log 2016\right| $$

A quick aside: this is a weaker inequality than our original one; since has a larger range it could be true for more values of $n$. However, we will eventually use this to prove (by contradiction) a stronger statement than Professor Halfbrain's theorem. Essentially we will say that, not only do $2016^n$ and $2016^n+32^n$ have the same number of digits, but that no power of $2016$ is "close" to a power of ten.

---

The paper mentioned above discusses the so-called linear form:

$$ \Lambda = b_2\log\alpha_2 - b_1\log\alpha_1 $$

Where $\alpha_1$ and $\alpha_2$ are nonzero algebraic numbers, and $b_1$ and $b_2$ are positive integers. In our case we have:

$$ \begin{align} \alpha_1 &= 2016 & b_1 &= n \\ \alpha_2 &= 10 & b_2 &= k \end{align} $$

We have a couple more quantities that we will need later:

$$ D = \frac{[\mathbb{Q}(\alpha_1,\alpha_2) : \mathbb{Q}]}{[\mathbb{R}(\alpha_1,\alpha_2) : \mathbb{R}]} $$

The notation $[E:F]$ is the degree of a field extension. Since our $\alpha_1$ and $\alpha_2$ are integers, they don't actually extend $\mathbb{Q}$ or $\mathbb{R}$, and $D=1$.

Second, we need $h(\alpha_i)$, where $h$ is the logarithmic height. For an algebraic number of degree $d$ whose minimal polynomial over the integers is $a\prod_{i=1}^{d}\left(X-a^{(i)}\right)$ (where the $a^{(i)}$ are the roots of the polynomial) the height is:

$$ h(\alpha) = \frac{1}{d}\left(\log |a|+\sum_{i=1}^{d}\log^+\left|a^{(i)}\right|\right) $$

where $\log^+(x)=\max\{\log x,0\}$. Since both our $\alpha_i$ are integers, their minimal polynomials are simply $X-\alpha_i$ (and $a=d=1$). Therefore:

$$ h(\alpha_i) = \frac{1}{1}\left(\log 1+\log^+\left|\alpha_i\right|\right)=\log\alpha_i $$

Finally, we need the quantity $b'$:

$$ b'=\frac{b_1}{D\log A_2}+\frac{b_2}{D\log A_1}=\frac{b_1}{\log A_2}+\frac{b_2}{\log A_1} $$

Where the $A_i$ are real numbers satisfying $A_i>1$ and:

$$ A_i \ge \max\left\{h(\alpha_i),\frac{|\log \alpha_i|}{D},\frac{1}{D}\right\}=\max\left\{\log\alpha_i,\frac{|\log \alpha_i|}{1},\frac{1}{1}\right\}=\log \alpha_i $$

(In the last step we assume $\alpha_i\ge e$.)

Corollary 2 to Theorem 2 of the paper states that, if $\alpha_1$ and $\alpha_2$ are multiplicatively independent, positive real numbers (which they are), then:

$$ \log|\Lambda| \ge -C_2D^4\left(\max\left\{\log b'+0.14,\frac{h_2}{D},\frac{1}{2}\right\}\right)^2\log A_1\log A_2 $$

($\alpha_1$ and $\alpha_2$ are multiplicatively independent if "no integral-exponent power product of them is equal to 1, unless all exponents are zero" [source]; that is, the only solution to $\alpha_1^{x_1}\alpha_2^{x_2}=1,\ \{x_1,x_2\}\in \mathbb{Z}$ is $x_1=x_2=0$.) Pairs of values for the constants $C_2$ and $h_2$ are given in a table later in the document.

We can simplify Corollary 2 using the values of $D$, etc. that we determined earlier:

$$ \begin{multline} -\log|\Lambda| \le C_2\left(\max\left\{\log\left(\frac{n}{\log\log 10}+\frac{k}{\log\log 2016}\right)+0.14,h_2\right\}\right)^2\cdot \\ (\log\log 2016)(\log\log 10) \end{multline} $$

Note that the signs of both sides have been reversed, in order to make the following argument easier to follow.

We know that $10^k$ is the power of ten just above $2016^n$, that is, $k = \lfloor n\log_{10}2016 \rfloor + 1$. This means $k < n\log_{10}2016 + 1$. We can use the same "weakening" argument from before to write

$$ \log\left(\frac{n}{\log\log 10}+\frac{k}{\log\log 2016}\right) \\ < \log\left(n\left[\frac{1}{\log\log 10}+\frac{\log_{10}2016}{\log\log 2016}\right] + \frac{1}{\log\log 2016}\right) \\ < \log n + \log\left(\frac{1}{\log\log 10}+\frac{\log_{10}2016}{\log\log 2016}\right) + \frac{1}{n\left(\frac{\log\log 2016}{\log\log 10}+\log_{10}2016\right)} \\ < \log(n) + 1.040 + \frac{0.175}{n} $$

Therefore,

$$ -\log|\Lambda| < C_2\left(\max\left\{\log n + 1.28 + \frac{0.175}{n},h_2\right\}\right)^2\cdot 1.693 $$

We reverse the signs again to simplify our reasoning:

$$ \log|\Lambda| > -1.693C_2\left(\max\left\{\log n + 1.28 + \frac{0.175}{n},h_2\right\}\right)^2 $$

Now, we bring back our original equation:

$$ 63^{-n} > \left| k\log 10 - n \log 2016\right| = |\Lambda| $$

Any counterexample to Professor Halfbrain's theorem must satisfy:

$$ -n\log 63 > \log|\Lambda| > -1.693C_2\left(\max\left\{\log n + 1.28 + \frac{0.175}{n},h_2\right\}\right)^2 $$

Therefore we only need to check values of $n$ that satisfy the inequality:

$$ -n\log 63 > -1.693C_2\left(\max\left\{\log n + 1.28 + \frac{0.175}{n},h_2\right\}\right)^2 \\ n < 0.409C_2\left(\max\left\{\log n + 1.28 + \frac{0.175}{n},h_2\right\}\right)^2 $$

At this point we substitute values of $C_2$ and $h_2$ from the table:

$$ h_2 = 10,\quad C_2=32.31 \\ n < \max\left\{13.2\left(\log n + 1.28 + \frac{0.175}{n}\right)^2, 1321\right\} \\ n \le 1320 $$

Thus, there are no large counterexamples to Professor Halfbrain's theorem, and we only need to check the cases $n=1$ to $1320$, which can be done with a short computer program; for example:

#include <stdio.h>
#include <gmp.h>
#define NMAX 1320

int main(int argc, char *argv[]) {
  int n;
  mpz_t pow_2016, pow_32, sum;

  mpz_init(pow_2016);
  mpz_init(pow_32);
  mpz_init(sum);

  for(n = 1; n <= NMAX; n++) {
    mpz_ui_pow_ui(pow_2016, 2016, n);
    mpz_ui_pow_ui(pow_32,   32,   n);
    mpz_add(sum, pow_2016, pow_32);

    size_t len_2016 = mpz_sizeinbase(pow_2016, 10);
    size_t len_sum  = mpz_sizeinbase(sum, 10);
    if(len_2016 < len_sum) {
      printf("failure at n = %d\n", n);
      break;
    }
  }

  if(n > NMAX) {
    printf("success\n");
  }

  mpz_clear(pow_2016);
  mpz_clear(pow_32);
  mpz_clear(sum);

  return 0;
}

The result:

robert@unity:~/c$ gcc -o 2016 2016.c -lgmp -lm && ./2016
success

Therefore, Professor Halfbrain is correct (this time).

Answer 2

I haven't been able to produce a definite proof but nevertheless I'll post my reasoning here in case someone manages to take it further.

We have that the number of digits of $2016^n$ is $$1 +\left \lfloor \log_{10}(2016^n) \right \rfloor = 1 + \left \lfloor n \cdot \log_{10}(2016) \right \rfloor \approx 1 + \left \lfloor 3.3045n \right \rfloor$$

Similarly, the number of digits of $32^n$ is $$1 + \left \lfloor n \cdot \log_{10}(32) \right \rfloor \approx 1 + \left \lfloor 1.5051n \right \rfloor$$

In particular, for large $n$ the number of digits of $2016^n$ is approximately $2.2$ times the number of digits of $32^n$.

Now, when adding up two numbers (in base $10$) using the schoolgrade algorithm, the largest carry-over for any given digit addition is $1$. This means that, if by adding up $32^n$ to $2016^n$ a new digit is obtained, then that digit must be $1$. More importantly, this means that all digits of $2016^n$ which are beyond the leftmost digit of $32^n$ must be $9$’s.

We can check for low values of $n$ that the theorem does hold, and so with the previous observation this means that, if the theorem were untrue for some $n_0$, then over half of the digits of $2016^{n_0}$ must be $9$’s; the leftmost digits of $2016^{n_0}$ would be a long sequence of $9$’s. This seems very, very unlikely. I have tried in many ways to show the impossibility of this, but have not managed thus far.

Answer 3

This isn't quite an answer, but it brings some heavy machinery to bear on the problem and shows that, at least theoretically, the question could be resolved by checking its truth for the first few values (i.e. the first $10^{15}$ values would suffice). Indeed, more strongly, we can say that Professor Halfbrain's theorem holds at least for all but finitely many $n$.

Note that, basically, we are looking for a solution to the following equation: $$2016^n < 10^k\leq 2016^n + 32^n$$ for non-negative integers $k$ and $n$. We can attack this by first taking logarithms: $$\log(2016)\cdot n < \log(10)\cdot k \leq \log(2016^n+32^n)$$ Now, the last term is sort of nasty, but we can deal with it know that the logarithm is concave and has derivative $\frac{1}x$, giving that $\log(x+y)\leq \log(x)+\frac{y}x$. Noting that $\frac{32}{2016}=\frac{1}{63}$, we can weaken the above equation to $$\log(2016)\cdot n < \log(10)\cdot k \leq \log(2016)\cdot n + \frac{1}{63^n}$$ which implies that: $$\left|\log(2016)\cdot n - \log(10)\cdot k \right| < \frac{1}{63^n}.$$ And, if we let $\Lambda=\log(2016)\cdot n -\log(10)\cdot k$ and take logarithms of both sides, we get: $$\log |\Lambda | < -\log(63)\cdot n$$

This is both good news and bad news. The good news is that this is called a linear form in logarithms and is well studied in mathematics (the crucial theorem in the area being Baker's Theorem). The better news is that we only need an exponential bound, whereas Baker's Theorem gives a stronger bound. The bad news is that I'm not well versed in the field, so it's hard to find explicit results that I can use. However in Baker and Wüstholz (1993) they give a form into which it's rather easy to plug constants: $$\log |\Lambda | \geq -(16nd)^{2(n+2)}\log(A_1)\log(A_2)\log(B)$$ where $d=1$ since the things we're taking logarithms of are rational and $n=2$ since there are two logarithms. The $A_1$ and $A_2$ happen to work out to $2016$ and $10$ respectively, since the minimal defining polynomial for an integers $n$ is $x-n$. Finally, $B$ is an upper bound for the coefficients in the linear form. Since it's rather obvious that $k\geq n$, but we're lazy, we'll just take $B$ to be $n$, which weakens the result.

Putting this all in gives: $$\log |\Lambda | \geq -2.31956\cdot 10^{13} \cdot \log(n)$$ and the left hand quantity is greater than $-n\log(63)$ when $n$ gets big, implying that there may only be finitely many exceptions to this statement. In particular, no exception may have $n\geq 1.89\times 10^{14}$. This is infeasible to check with computer, but it's very possible that stronger bounds exist that I'm unaware of that might resolve it, since I used a bound applicable for all algebraic numbers and for all $n$ (and moreover, which is applicable in the non-homogenous case, whereas we are in the homogenous case. I'm not an expert in this field, so I'm using the coarse, but accessible results).

Answer 4

The answer is the theorem is true.

This is my, quite possibly naive, proof:

Rewriting the first expression for the number of digits $ d $, where $ a $ is a real number between 0.1 and 1, then: $$ 2016^n = a \times 10^d \\ d = \log_{10}{\left({\frac{2016^n}{a}}\right)} \\ =\log_{10}{\left(2016^n\right)}-\log_{10}{a} $$ Similarly for the second expression, this time where $ 0.1 <= b <= 1 $: $$ 2016^n + 32^n = b \times 10^d \\ d = \log_{10}{\left({\frac{2016^n+32^n}{b}}\right)} \\ =\log_{10}{\left(2016^n+32^n\right)}-\log_{10}{b} $$ Clearly $ -\log_{10}a $ and $ -\log_{10}b $ will both be real numbers between 0 and 1. Therefore if the number of digits is the same then: $$ \log_{10}{\left(2016^n\right)} + x = \log_{10}{\left(2016^n+32^n\right)} $$ where $ x = \log_{10}b $ - $ \log_{10}a $ and therefore $ -1 <= x <= 1 $.

Continuing on this basis: $$ x = \log_{10}{\left(2016^n+32^n\right)} - \log_{10}{\left(2016^n\right)} \\ = \log_{10}{\left(\frac{2016^n+32^n}{2016^n}\right)} \\ = \log_{10}{\left(1 + 63^{-n}\right)} $$ For any integer $ n \geq 0 $ the second term will be insignificant and this relationship will always be true. In fact for $ n = 0, x \approx 0.3 $ and at $ \lim_{n \rightarrow \infty} x\left(n\right) = 0 \quad\blacksquare $.

Edit: Alas, this is definitely not a proof. If it were a proof then the last line would mean that you could replace 32 with any base for any $ n $ and that is clearly not correct.

Answer 5

I've already posted an answer which is clearly wrong but this is a different approach so I think it warrants another answer. The answer is simpler than some of the others posted but may be incomplete.

The answer is still that the theorem is true.

We start with the observation that for the theorem to be true $ 32^n $ must be smaller than the difference between the next higher power of 10 and $ 2016^n $. The next higher power of 10 is simply $ 10^{\lfloor\log_{10}(2016^n)\rfloor+1} $, so the theorem is true iff (for all $ n $):

$$ 10^{\lfloor\log_{10}(2016^n)\rfloor+1} - 2016^n > 32^n \\ $$

To get rid of the pesky floor function we replace the $+1$ with $ +x $, such that:

$$ \lfloor\log_{10}(2016^n)\rfloor+1 = \log_{10}(2016^n)+x $$

$ x $ is equal to $ 1 $ less the fractional part of $ \log_{10}(2016^n) $, and is always in the range $ 0 < x \leq 1 $.

The previous inequality can be reduced to:

$$ 10^{\log_{10}(2016^n) + x} - 2016^n > 32^n \\ 2016^n10^x-2016^n - 32^n > 0 \\ 32^n\left(-1 - 63^n + 63^n10^x\right) > 0 \\ 63^n\left(10^x-1\right) -1 > 0 \\ 10^x - 1 > 63^{-n} $$

Since $ x $ is in the range $ 0 < x \leq 1 $, the first term is in the range $ 1 < 10^x \le 10 $. A number of observations can be made:

• First, clearly as $ x \to 0 $ the inequality does not hold for any $ n $. This is intuitively what we would expect, i.e. as $ 2016^n $ approaches a power of $ 10 $, the $ 32^n $ comes closer to rolling it over to the next power of $ 10 $.

• Second, as $ n \to\infty $, the inequality is more likely to be true ($ x $ can be smaller and smaller while still producing a positive overall result). This observation is dramatically demonstrated by changing to above inequality to an equality, and solving for the largest value of $ x $ that makes the inequality false:

  $$ x = \log_{10}(1 + 63^{-n}) \approx \frac{63^{-n}}{\log 10} $$

  It is apparent that the critical value of $ x $ rapidly approaches $ 0 $, even for quite small values of $ n $. For example, when $ n = 5 $ the inequality becomes $ x > 4.4 \times 10^{-10} $; again, $ x $ needs to be larger than this tiny value to provide a counterexample to the theorem.

So how small does $ x $ actually get? Remember $ x $ is equal to $ 1 $ less the fractional part of $ \log_{10}(2016^n) = n\log_{10} 2016 $.

Well, $ x $ follows a cycle that hits its minimum where: $$ n = \left\lfloor\frac{10^m}{\log_{10}(2016)}\right\rfloor $$ where $ m $ is a non-zero positive integer.

The first such case is $ n = 3 $, followed by $ n = 30 $, $ n = 302 $... The log function apparently cannot be expressed as a decimal fraction, so $ x $ will never be exactly zero but will get closer as the approximation is improved with each power of 10, but only by one digit with each power of 10. Therefore although the minimum $ x $ approaches $ 0 $ it does so far more slowly than the required $ x $ to break the theorem - by many orders of magnitude - and the gap just keeps on widening.

At $ n = 3 $ the theorem holds and as the disparity between the minimum $ x $ and the required minimum $ x $ only widens with increasing $ n $, we can say conclusively that no value of $ n $ will break the theorem.

This can be taken a step further, because knowing that $ n = 3 $ is the point of vulnerability, we can explore other bases other than $ 32 $. By doing this we can demonstrate that any integer base $ b < 1218 $ will also not break the theorem for any value of $ n $ e.g.:

$$ 2016^3 = 8.19 \times 10^9 \\ 2016^3 + 1217^3 = 9.99 \times 10^9 \\ 2016^3 + 1218^3 = 1.00 \times 10^{10} $$

The weakness of the proof is that $ \frac{1}{\log_{10}\left(2016\right)} $ is assumed to not be representable as a decimal fraction. If it is, then at some point the minimum $ x $ will reach zero but the required minimum will never reach zero so at that point the theorem fails.

Edit: Actually $ \frac{1}{\log_{10}\left(2016\right)} $ can be shown to be not just unrepresentable as a decimal fraction but, in fact, irrational: $$ \log_{10}\left(2016\right) = \frac{a}{b} \\ 2016^b = 10^a $$ which is impossible since $ 6 \cdot 6 = 36 $ and therefore the least significant digit of all powers of $ 2016 $ will be $ 6 $ and never $ 0 $. The reciprocal is obviously also irrational. The proof is therefore complete.

...and just in case anyone is still interested in this (although I am probably just talking to myself), as a corollary of the above proof the original theorem can be generalized as:

For any number with an integer base $ x \geq 1 $, raised to an integer power $ n \geq 1 $, the maximum integer base $ y \geq 1 $, raised to the same power, that can be added such that the result has the same number of digits when represented as a radix $ b $ number is: $$ y = \lfloor{x\left(b^{b-m\log_b{x}} - 1\right)^\frac{1}{m}}\rfloor $$ where $ m = \lfloor{b\log_x{b}}\rfloor $, $ m \neq 0 $ and $ b-m\log_b{x} \leq 1 $

For $ m = 0 $ there is no solution and for $ b-m\log_b{x} > 1 $ the theorem breaks down. This occurs adjacent to the discontinuities that exist in the this expression due to the floor function. It might be possible to modify the theorem to remove, or limit, the second condition.