An Equation Involving the Total Number of Digits

Bùi Quang Tuân has posted the following problem at the CutTheKnot facebook page:

Given $n\in\mathbb{N},$ find the largest positive integer $k$ such that the sequence $1, 2, 3, 4, \ldots, k-1, k$ has a total of $n\cdot k$ digits.

Bùi gave an example: for $n=1,$ $k=9,$ and suggested that for every $n$ a $k$ exists and is in fact unique.

Solution

Let $n=2.$ First observe that $k$ can't have fewer that $3$ digits. We skip the possibility of its being a single digit number. But, assuming it has two digits, we get an impossible equation $2k=9+2(k-9).$ Assuming $k$ has three digits, we obtain an analogous equation:

$2k=9+2\cdot 90+3(k-9-90),$

with the solution $k=108.$ Assuming $k$ has four digits leads to the equation $2k=9+2\cdot 90+3\cdot 900+4(k-999),$ which simplifies to $2k=1107$ - unsolvable in integers. Assuming $k$ has five digits gives an equation $2k=9+2\cdot 90+3\cdot 900+4\cdot 9000+5(k-9999),$ which simplifies to $3k=10006,$ also unsolvable.

With this experience, let first show that there is always $k=k(n)$ that answers the problem, and later prove its uniqueness.

Existence of $k$

We'll seek $k$ among the integers with $n+1$ digits. This leads to the equation:

$\displaystyle nk=\sum_{i=1}^{n}i\cdot 9\cdot 10^{i-1}+(n+1)(k-\sum_{i=1}^{n}9\cdot 10^{i-1}),$

with an immediate solution

$\begin{align}\displaystyle k&=(n+1)\sum_{i=1}^{n}9\cdot 10^{i-1}-\sum_{i=1}^{n}i\cdot 9\cdot 10^{i-1}\\ &=9\sum_{i=1}^{n}(n+1-i)10^{i-1}. \end{align}$

Uniqueness of $k$

An assumption that $k$ may have more than $n+1$ digits leads to the equation

$\displaystyle nk=\sum_{i=1}^{n+s}i\cdot 9\cdot 10^{i-1}+(n+1+s)(k-\sum_{i=1}^{n+s}9\cdot 10^{i-1}),$

where $s$ is a positive integer. This equation simplifies to

$\begin{align}\displaystyle (s+1)k&=9(n+1+s)\sum_{i=1}^{n+s}10^{i-1}-9\sum_{i=1}^{n+s}i10^{i-1}\\ &=(n+1+s)(10^{n+s}-1)-9\sum_{i=1}^{n+s}i10^{i-1}. \end{align} $

It can be verified that

$\displaystyle\sum_{i=1}^{t}i10^{i-1}=\frac{1}{9}\left(t10^{t}-\frac{1}{9}(10^{t}-1)\right)$

such that the equation for $k$ becomes

$\displaystyle (s+1)k=10^{n+s}-(n+1+s)+\frac{1}{9}(10^{n+s}-1).$

The expression on the right is an $n+s+1$-digit number with the first digit equal to $1.$ Dividing this by $s+1,$ with $s\gt 0,$ (even assuming this is possible) gives a number with the number of digits at most $n+s,$ which is something we were not looking for for $k.$

Note the sequence $k(n)$ appears in the Online Encyclopedia of Integer Sequences as sequence A099676.

|Front page| |Contents| |Arithmetic|

  Copyright © 1996-2018 Alexander Bogomolny

71470981