# Proving sum of product forms a pattern in n * nnnnnn…

I am consider a problem regarding numbers which are, in decimal, one digit repeated - for instance, $88888888$ is such a number. In particular, I am looking at the following problem:

The sum of the digits of the number $$8\cdot \underbrace{88\ldots 88}_{n\text{ times}}$$ is $1000$. How many $8$'s are there? (i.e. what is $n$?)

I know that the correct answer is $991$ and I can observe a pattern that lets me solve it; in particular, the sum of digits of $8\cdot 8=64$ is $10$ and the sum of digits of $8\cdot 88=704$ is $11$ and the sum of digits of $8\cdot 888=7104$ is $12$ - so it appears that the sum of the digits is exactly $n+9$. One can note that if one replaces all the eights with other digits, similar patterns exist - for instance, with sevens, the sum increases by $4$ for each digit.

How can this pattern be proven?

• Please include your thoughts and efforts in this and future posts. Formatting tips here. – Em. Jan 14 '16 at 1:50
• @probablyme Thanks for your advice! Just getting used to stackexchange. I am very new to proof and I don't know where to start in trying to prove this. That is why I posted it here. – London Holmes Jan 14 '16 at 1:52
• I made a substantial edit since I think this is an interesting observation and I hope it will be well received here with better formatting; feel free to change/undo whatever I might have done if it conflicts with what you intended. – Milo Brandt Jan 14 '16 at 1:58
• @MiloBrandt Can't accept your edits yet because I don't have enough rep but I think they greatly helped. Thanks! – London Holmes Jan 14 '16 at 2:01
• Refering the the number as 8 when clearly it is an unknown digit is REALLY confusing. Why don't you refer to it as "a" or some other variable? – fleablood Jan 14 '16 at 2:20

One can note a more general pattern - let us, for convenience, define $$R_n=\underbrace{11\ldots 11}_{n\text{ times}}=\frac{10^n-1}9.$$ Then, we can note that, for fixed $k$, after a point, the sum of the digits of $k\cdot R_n$ increases linearly. Note that, if the digits were $8$'s, then we can express the desired product as $8^2\cdot R_n$ since multiplying by $8$ once gives $88\ldots 88$ and doing it again gives $8\cdot 88\ldots 88$. One will see the pattern if they go far enough: $$64\cdot 1 = 64$$ $$64\cdot 11 = 704$$ $$64\cdot 111 = 7104$$ $$64\cdot 1111 = 71104$$ $$64\cdot 11111 = 711104$$ $$64\cdot 111111 = 7111104$$ $$64\cdot 1111111 = 71111104$$ $$64\cdot 11111111 = 711111104$$ So, obviously, there's a pattern here - which is that we get a new $1$ inserted after the $7$ each time we add another $1$ on the left.

There are a few productive ways to prove this. The one I think is most elegant would be simply to write this as long multiplication: $$\begin{array} & & & 1 & 1 & 1 & \ldots & 1 & 1 & 1 \\ \times & & & & & & & 6 & 4 \\ \hline && 4 & 4 & 4 &\ldots & 4 & 4 & 4 \\ +&6 & 6 & 6 & 6 &\ldots & 6 & 6 & 0\\\hline \end{array}$$ and now we can carry out this addition by hand too, writing out carries in the small text above: $$\begin{array} & &\scriptstyle{1} & \scriptstyle{1} & \scriptstyle{1} & \scriptstyle{1} &\ldots & \scriptstyle{1} & & \\ & & 4 & 4 & 4 &\ldots & 4 & 4 & 4 \\ +&6 & 6 & 6 & 6 &\ldots & 6 & 6 & 0\\\hline & 7 & 1 & 1 & 1 &\ldots & 1 & 0 & 4 \end{array}$$ One may notice that every column elided looks exactly like this: $$\begin{array}{c} &\scriptstyle{1} \\ &4 \\ (+)&6\\ \hline & 1\end{array}$$ and, obviously, caused a $1$ to be carried to the column to the right of it. This suffices to prove that, once these columns begin, they will not end until we reach the end of the $4$'s in the top column - this is proved inductively, if we wish to be formal. Then, once we have this, we know that the beginning (here $7$) will always be the same, as it always looks like: $$\begin{array}{c} &\scriptstyle{1} \\ & \\ (+)&6\\ \hline & 7\end{array}$$ and the ending will always look like: $$\begin{array}{c} & \\ &4&4 \\ (+)&6&0\\ \hline (1) & 0& 1\end{array}$$ where the $1$ in parenthesis is carried, causing the inner columns to begin. This proof can be redone in whole to show the property for any sequence of the form $k\cdot 11\ldots 11$. With a bit more care, we can note that a sequence of identical columns begin after at most $2\lceil\log_10(k)\rceil$ digits (for a rough bound) since the carry to each such column is an increasing function of the carry to the previous column. Since the carry does not exceed the number of digits of $k$, it must hit a fixed point after at most $\lceil\log_{10}(k)\rceil$ steps and this follows the "irregular" portion of the sum (when zeros are still being added from some terms), which has length at most $\lceil\log_{10}(k)\rceil$ as well.

More directly, however, would be an algebraic approach to prove some identity of the form: $$k\cdot R_n = \alpha \cdot 10^n + \beta \cdot R_{n-m} \cdot 10^m + \kappa$$ for positive integers $\alpha$, $\beta$, $m$, and $\kappa$ with $\kappa < 10^m$ and $0\leq \beta < 10$. Knowing the form of $R_n=\frac{10^n-1}{9}$ makes it easy to verify such an identity - for instance: $$64\cdot R_n = 7\cdot 10^n + 1\cdot R_{n-2} \cdot 10^2 + 4$$ $$64\cdot \underbrace{11\ldots 11}_{n\text{ times}}=7\underbrace{11\ldots 11}_{n-2\text{ times}}04$$ holds, as can be checked purely algebraically. Note that this expresses that the last few digits are the digits of $\alpha$ (which is $7$ in the example) followed by a number of repetition of $\beta$ (which is $1$ in the example) followed by the digits of $\kappa$ (which is $04$ in the example). Obviously, the sum of the digits will increase by $\beta$ at each step, since the only change in the expression is the insertion of another one of that digit.

To find such an expression, one extracts things in parts. For instance, for $64\cdot R_n=\frac{64\cdot 10^n-64}9$, we first take out the largest multiple of $10^n$ that we can which is $\lfloor\frac{64}9\rfloor=7$. Subtracting this out gives $$\frac{64\cdot 10^n-64}{9}-7\cdot 10^n=\frac{1\cdot 10^n-64}9$$ From here, we want the numerator to be of the form $\beta(10^n - 10^m) + 9\kappa$ which is easy to do. Here, for instance, we just need to choose $m$ such that $10^m$ is bigger than $64$ - so $m=2$ is the smallest that suffices. This gives $$\frac{64\cdot 10^n-64}{9}-7\cdot 10^n=\frac{1\cdot (10^n-10^2)+36}9=1\cdot R_{n-2}\cdot 10^2+4$$ which yields the expression when we add the $7\cdot 10^n$ back to both sides.

• Well, that was fun. – Milo Brandt Jan 14 '16 at 2:49

$a*aaaa....aaa = a^2*1111111....111$ (m a's and m 1's)

Three cases to consider:

$a^2$ has one digit. (i.e. $a = 1,2,3$)

$a^2$ has two digits and the sum of the digits is less than 10. (i.e. $a = 4,5,6, 9$)

$a^2$ has two digits and the sum of the digits is 10 or more. (i.e. $a = 7,8$)

====

If $a^2 = b$ has one digit,$b$, then $a*aaa... = a^2*111... = bbbbb$ and the sum of the digits is $m*b$. That was easy.

===

If $a^2 = 10b + c$ has two digits, $b$ and $c$, and $b + c < 10$ then: $a*aaa... = a^2*1,1,1... = (10b+c),(10b + c),...,(10b + c) = b,(b+c),(b+c),...,(b + c), c$.

[Here I use notation x,x,x ... as shorthand for $\sum x*10^i$. In the $b,(b+c),...,(b+c), c$ each term is a single digit although it wasn't for the $(10b+c),(10b+c)...$ representation. But from that one we "carried the b's" to get the final representation.]

The sum of the digits $b,(b+c),(b+c),...,(b + c), c$ is $b + (m-1)(b+c) + c= m(b+c)$.

===

If $a^2 = 10b + c$ is two digits ($b$ and $c$) and $b + c = 10 + d$ for some digit d...

First note that $d < 9$ so $d + 1 < 10$.

So $a*a*1111... = a^2*1111.... = (10b +c),(10b + c), .... (10b + c),(10b + c) = b,(b + c),....(b+c),c = b,(10 + d),(10 + d), .....(10 + d),c = (b+1),(d+1),(d+1),....(d+1),d,c$.

And the sum of the digits is $b + 1 + (m-2)(d+1) + d + c = b + c + d+ (m-2)(d+1) = 11 + 2d + (m-2)(d +1) = m(d+1) + 9$.

====

In summary: Sum of digits = $m*e \{+ 9 \}$ where $m$ is the number of digits and $e$ is the $a^2$, sum of digits of $a^2$, or sum of sum of digits of $a^2$ and $" + 9"$ applies only if sum of digits of $a^2 \ge 10$.

And hence, each increase in $m$ the sums increase by $e$.

===

And, BTW, back to the original problem: Su of digits of $a*aaaa....$ = 1000- how many digits are there:

Sum of digits is $m*e \{+9\} = 1000$. $e$ can be: $a=1 \implies e =1;a=2 \implies e =4;a=3 \implies e =9;a=4 \implies e =7;a=5 \implies e =7;a=6 \implies e =9;a=7 \implies e =4;a=8 \implies e =1; a=9 \implies e =9;$

$m*e = \{1000, 991\}$. $991$ is primes so if $m*e = 991$ then $e = 1; a=8; m=991$. If $m*e = 1000$ then $e$ is 1 or a multiple of 2 or 5 only, so possibilities:

$e = 1;a = 1; m = 1000;$

$e = 4; a = 2; m = 250;$

$e = 4; a =7$ is not possible as that would imply $m = 991$.