# Is the sum of digits of $\left(16^k - 1\right)$ less than $6k$ for $k > 223$?

I had been researching the OEIS sequence A165722, which is the sequence of positive integers $k$ such that the sum of digits of $\left(16^k - 1\right)$ is equal to $6k$. I used computational power to determine that the sum of digits is less than $6k$ for $223 < k < 10^6$. I made a conjecture that $6k$ would continue to grow at a faster rate than the digit sum, and thus the sequence is finite. I and several others, however, were unsure how one would go about proving this. I thought that perhaps there would be some way to show a regularity in the digits of $16^k - 1$, but I would not know how to go about finding or proving this regularity.

• I don't think that there is hope to find such a regularity. Besides the few last digits, the digits will probably behave like a random sequence. We can expect that the average digit does not exceed $4.5$ significant, but we would need an average digit of about $4.98$ to have $6k$ digits or more. So, the digitsum should always be less than $6k$ for $k>223$. I would be very surprised if someone can prove this. – Peter Apr 29 '18 at 7:29
• Legendre's formula might be a good starting: if $\nu_q(n)$ denotes the sum of digits in the $q$-ary expansion of $n$, then $$\nu_q(n) = n - (q-1)\sum_{j=1}^{\infty} \left\lfloor \frac{n}{q^j} \right\rfloor = (q-1)\sum_{j=1}^{\infty} \frac{n\text{ mod }q^j}{q^j}.$$ But again, this leads us to an intricate world of multiplicative groups and I have no idea. I would also be very surprised if someone can prove this. – Sangchul Lee May 1 '18 at 4:26
• I don't know if this applies, but perhaps you could use Benfords law to do a statistical/probabilistic analysis of the digits of $16^k-1$ and then show that the probability of getting a number whose digit sum is equally to 6k is greater than 0. Once again though, I'm not sure if Benford's law applies. Perhaps you could find a distribution for the digits in base 16. – Saudman97 May 2 '18 at 21:24
• Here's a proof of a very weak lower bound, showing that the sum of the base-$10$ digits of $2^n$ is $\Omega(\log n)$: oeis.org/A001370/a001370_1.pdf – mjqxxxx May 3 '18 at 0:21
• This somewhat related question may be of interest. I hastily misread it, and thought it came close to proving yours. It doesn't, but it may be of interest anyway. – Jyrki Lahtonen May 5 '18 at 18:29

Some preliminary estimates. From this book, page 79 (accessible in preview mode) $$S(16^n-1)=16^n-1 - 9\sum\limits_{k\geq1} \left \lfloor \frac{16^n-1}{10^k} \right \rfloor \tag{1}$$

Further $$S(16^n-1)= 16^n-1 - 9\sum\limits_{k\geq1} \left(\frac{16^n-1}{10^k}-\left\{\frac{16^n-1}{10^k}\right\}\right)=\\ 16^n-1 - 9\sum\limits_{k\geq1} \frac{16^n-1}{10^k}+9\sum\limits_{k\geq1}\left\{\frac{16^n-1}{10^k}\right\}=\\ (16^n-1)\left(1 - 9\sum\limits_{k\geq1} \frac{1}{10^k}\right)+9\sum\limits_{k\geq1}\left\{\frac{16^n-1}{10^k}\right\}=\\ (16^n-1)\left(1 - 9\left(\frac{10}{9}-1\right)\right)+9\sum\limits_{k\geq1}\left\{\frac{16^n-1}{10^k}\right\}= 9\sum\limits_{k\geq1}\left\{\frac{16^n-1}{10^k}\right\}$$ Or $$S(16^n-1)=9\sum\limits_{k\geq1}\left\{\frac{16^n-1}{10^k}\right\}\tag{2}$$

The last digit of $16^n-1$ is always $5$ and $$\left\{\frac{16^n-1}{10^k}\right\}=0.\overline{a_1a_2...a_{k-1}5} \leq 0.99..95<1$$ $9$ repeated $k-1$ times. But only for the first $n\log_{10}16$ terms. For all $k>n\log_{10}16$ $$\left\{\frac{16^n-1}{10^k}\right\}\leq 0.00..099..95$$ where $00..099..9$ is of length $k-1$. Basically, starting with $k\geq \left \lfloor n\log_{10}16 \right \rfloor+1$ this tail forms an infinite geometric progression with ratio $\frac{1}{10}$ which sums to a constant. So we can conclude $$S(16^n-1) < 9n\log_{10}16 + C$$ We also have that $9\log_{10}16<11$, thus $$S(16^n-1) < 11n+ C \tag{3}$$ Probably, with more accurate calculations, a better estimate may be obtained ... work in progress.

• This is very nice. I do know that for some values, $S(16^n - 1) \geq 6n$, but the last apparent occurrence of this is when $n=223$. I am concerned about values above this. This is a great start though. – Kirk Fox May 4 '18 at 18:47
• This bound is fairly trivial... the number $16^k-1$ has no more than $1 + \log_{10}(16^k-1) < 1 + k \log_{10}16$ digits, each of which is no greater than $9$, so the digit sum is no greater than $9 + 9k\log_{10}16 < 10.85k + 9.$ – mjqxxxx May 4 '18 at 23:11
• @mjqxxxx 1st of all to reveal a formula and secondly to engage more people in finding a better estimate. The weak part in the subsequent calculations is of course the gross estimate of $0.\overline{a_1a_2...a_{k-1}5} \leq 0.99..95<1$, maybe somebody could find a finer pattern? It matches your calculations, but it has, imo, more potential ... – rtybase May 4 '18 at 23:30
• Knowing the fractional part of $16^n-1$ over $10^k$ is the same as knowing the digits of $16^n-1$ since dividing by $10^k$ just shifts it, preserving the significant digits. This work can also be skipped using the trivial bound: $16^n-1$ has $\log_{10}(16^n-1)\approx n\log_{10}(16)$ digits in decimal, and each digit can be at most $9$ giving the bound $9n\log_{10}(16)$ as you have. – Will Fisher May 7 '18 at 0:53

Let $S\left(n\right)$ be the sum of the digits of $n$. Since $16^k-1$ is divisible by 5 but not 2, the last digit is five, and hence $$S\left(16^k-1\right)=S\left(16^k\right)-1$$ Essentially we want to say that $16^k=2^{4k}$ typically has digits less than 5 rather than digits more than five, or at least it doesn't mostly have digits more than five. One thought that pops out is that the map $k\mapsto2k\textrm{ mod }10$ is periodic for even $k$ with period 4 (we have the cycle $2\mapsto4\mapsto8\mapsto6\mapsto2$), and for odd $k$ of course the next term is even. Except for when there is carrying, this map is the map taking digits of $2^k$ to $2^{k+1}$. Could this periodicity which matches $2^{4k}$ explain it?