## Sum of digits of small powers of nine.

In a previous post I wondered how to prove that for integer $$d \in [1,N]$$

\label{eqn:numberGame:20}
((N-1) d) \text{mod} N + ((N-1) d) \text{div} N = N-1.

Here’s a proof in two steps. First for $$N = 10$$, and then by search and replace for arbitrary $$N$$.

## $$N = 10$$

Let

\label{eqn:numberGame:40}
x = 9 d = 10 a + b,

where $$1 \le a, b < 9$$, and let $$\label{eqn:numberGame:180} y = a + b,$$ the sum of the digits in a base $$10$$ numeral system. We wish to solve the following integer system of equations \label{eqn:numberGame:60} \begin{aligned} 9 d &= 10 a + b \\ y &= a + b \\ \end{aligned}. Scaling and subtracting we have $$\label{eqn:numberGame:80} 10 y - 9 d = 9 b,$$ or $$\label{eqn:numberGame:100} y = \frac{9}{10} \lr{ b + d }.$$ Because $$y$$ is an integer, we have to conclude that $$b + d$$ is a power of $$10$$, and $$b + d \ge 10$$. Because we have a constraint on the maximum value of this sum $$\label{eqn:numberGame:120} b + d \le 2 ( 9 ),$$ we can only conclude that $$\label{eqn:numberGame:140} b + d = 10.$$ or $$\label{eqn:numberGame:160} \boxed{ b = 10 - d. }$$ Back substitution into \ref{eqn:numberGame:40} we have \label{eqn:numberGame:200} \begin{aligned} 10 a &= 9 d - b \\ &= 9 d - 10 + d \\ &= 10 d - 10 \\ &= 10 \lr{ d - 1 }, \end{aligned} or $$\label{eqn:numberGame:220} \boxed{ a = d - 1. }$$ Summing \ref{eqn:numberGame:220} and \ref{eqn:numberGame:160}, the sum of digits is $$\label{eqn:numberGame:240} a + b = d - 1 + 10 - d = 9.$$

## For arbitrary $$N$$

There was really nothing special about $$9, 10$$ in the above proof, so generalizing requires nothing more than some search and replace. I used the following vim commands for this “proof generalization”

:,/For arb/-1 y
:+/For arb/+1
:p
:,$s/\<9\>/(N-1)/cg :,$ s/\<10\>/N/cg
:,\$ s/numberGame:/&2:/g


Let

\label{eqn:numberGame:2:40}
x = (N-1) d = N a + b,

where $$1 \le a, b < N-1$$, and let $$\label{eqn:numberGame:2:180} y = a + b,$$ the sum of the digits in a base $$N$$ numeral system. We wish to solve the following integer system of equations \label{eqn:numberGame:2:60} \begin{aligned} (N-1) d &= N a + b \\ y &= a + b \\ \end{aligned}. Scaling and subtracting we have $$\label{eqn:numberGame:2:80} N y - (N-1) d = (N-1) b,$$ or $$\label{eqn:numberGame:2:100} y = \frac{N-1}{N} \lr{ b + d }.$$ Because $$y$$ is an integer, we have to conclude that $$b + d$$ is a power of $$N$$, and $$b + d \ge N$$. Because we have a constraint on the maximum value of this sum $$\label{eqn:numberGame:2:120} b + d \le 2 ( N-1 ),$$ we can only conclude that $$\label{eqn:numberGame:2:140} b + d = N.$$ or $$\label{eqn:numberGame:2:160} \boxed{ b = N - d. }$$ Back substitution into \ref{eqn:numberGame:2:40} we have \label{eqn:numberGame:2:200} \begin{aligned} N a &= (N-1) d - b \\ &= (N-1) d - N + d \\ &= N d - N \\ &= N \lr{ d - 1 }, \end{aligned} or $$\label{eqn:numberGame:2:220} \boxed{ a = d - 1. }$$ Summing \ref{eqn:numberGame:2:220} and \ref{eqn:numberGame:2:160}, the sum of digits is $$\label{eqn:numberGame:2:260} a + b = d - 1 + N - d = N-1.$$ This completes the proof of \ref{eqn:numberGame:20}.

## Pick a number between 1 and 10

It also appears to be true that, for integer a in $$[1, N+1]$$
$(N a) \text{div} (N+1) + (N a) \text{mod} (N + 1) = N.$