16
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ 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. $\endgroup$ – Peter Apr 29 '18 at 7:29
  • 1
    $\begingroup$ 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. $\endgroup$ – Sangchul Lee May 1 '18 at 4:26
  • $\begingroup$ 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. $\endgroup$ – Saudman97 May 2 '18 at 21:24
  • 1
    $\begingroup$ 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 $\endgroup$ – mjqxxxx May 3 '18 at 0:21
  • 2
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen May 5 '18 at 18:29
1
+50
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Kirk Fox May 4 '18 at 18:47
  • 1
    $\begingroup$ 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.$ $\endgroup$ – mjqxxxx May 4 '18 at 23:11
  • $\begingroup$ @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 ... $\endgroup$ – rtybase May 4 '18 at 23:30
  • $\begingroup$ 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. $\endgroup$ – Will Fisher May 7 '18 at 0:53
0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.