# How many numbers below N have equal digit sum?

I'm trying to index $M$ squares that can each have $N$ colours. The order the colours appear in does not matter, it just matters how many of each colour there are.

So say $N=2$ and $M=2$ and the colours are red(R) and blue(B). This results in the following possible states for our squares: $RR, RB, BR, BB$. If we want to map those to how much of each colour there are this results in $02, 11, 11, 20$, so the first digit represents the amount of blue's and the second the reds.

It's easy to see that the digit sum of this representation is always equal to $M$. Now say $N$ and $M$ are very large. We can represent each colour state as an $N$ length number of base $M$. However, I want to store some information about each possible colour state. Therefore we should introduce an ordering in the colour states so a mapping is possible. We can simply order by size: $[02,11,20]$.

Now the actual question is as follows: given the number $20$, how many numbers below $20$ are there that have the same digit sum? Because that equals $2$, which is the exact position I need to look in my information array. A possible strategy is building a lookup table by just enumeration all possibilities, but I want to know if there is a "smarter" way. How many numbers with equal digit sum are there below N? Of course, if someone knows a smarter way to label my colour states, that would also be accepted, but the other question remains interesting as well.

• in the last paragraph shouldn't "how many digits below 20" be how many numbers below 20... now below 20, the only numbers with the same sum of digits are 2 and 11. So, I may be wrong here, but it looks like any number below or above 20 with the same sum of digits as 20 is 20+9k or 20-9k with k=0,1... – user25406 Oct 8 '16 at 14:29
• You are correct, changed it now. – Thijs Miedema Oct 8 '16 at 15:27
• keep in mind that adding 9 to a number does not change its sum of digits. – user25406 Oct 8 '16 at 18:36
• That does depend on the base your working in, in this case $M$. Also, that does not always work (for example 70 and 79 do not share digit sum). – Thijs Miedema Oct 9 '16 at 13:46
• yes they do because 79 sum of digits is 7+9 = 16 = 1+6 = 7 and 7+0=7. To calculate the sum of digits of a number, you need to add all the digits together until you get a single digit. – user25406 Oct 9 '16 at 16:02

## 1 Answer

Given $N$ squares and $M$ colors, I denote one specific coloring by:

$$(N_M,N_{M-1},\ldots,N_1)=:\vec{N},$$

where $N_i$ denotes the number of squares with color $i$ ($i=1,\ldots,M$) and we require:

$$\sum_{i=1}^M N_i = N.$$

If we map such an $M$-tuple to a number $K$ in the following way:

$$\vec{N} \rightarrow K = [N_M.N_{M-1}._\ldots.N_1]_{N+1} = \sum_{i=1}^M N_i (N+1)^{i-1},$$

then all well-defined colorings $\vec{N}$ (where $\sum_{i=1}^M N_i = N$) map onto numbers $K$, which satisfy:

$$\nu_{N+1}(K)=N,$$

where $\nu_{n}(a)$ is the digit-sum of the number $a$ in base $n$.

Example: For $N=6$ squares, $M=3$ colors (R=red, G=green, B=blue) and the specific coloring $\vec{N}= (2,1,3) =RRGBBB$ (2 red squares, 1 green squares and 3 blue squares):

$$K=[2.1.3]_{6}=2\cdot 6^2 + 1\cdot 6^1 + 3 \cdot 6^0=81=8\cdot 10^1 + 1 \cdot 10^0=[8.1]_{10},$$

and

$$\nu_6(81)=\nu_6([2.1.3]_6)=6=N.$$

Note that the dots $.$ in the $[]$-notation only serve the purpose of separating individual digits. The largest number, that satisfies these constraints, is clearly:

$$K_{max}=[\underbrace{N.0._\ldots.0}_{M \text{ digits}}]_{N+1}=N\cdot(N+1)^{M-1},$$

and the smallest:

$$K_{min}=[0._\ldots.N]_{N+1}=N.$$

The number $N_s$ of all numbers $K_{min}\leq K\leq K_{max}$, which satisfy the constraint $\nu_{N+1}(K)=N$, is:

$$N_s=\binom{N+M-1}{N}.$$

If you come from a physics background, you may recognize $N_s$ as the number of distinct configurations of $N$ (otherwise indistinguishable) bosons in $M$ available states. For an intuitive derivation, see: Counting Boson states (just substitute "boson" with "square" and "state" with "color"). Other than that, you can try for example to find all 3-digit decimal numbers $0<n\leq 900$, whose digit sum is 9 and then see that there are exactly $\binom{9+3-1}{9}=55$ such numbers. Or for 2 digits (which is easier), there are $\binom{9+2-1}{9}=10$ such numbers $\leq 90$. You would of course have to interpret "9" implicitly as the two-digit number "09".

Even though this mapping is very intuitive, for large $N$ and $M$ it is very inefficient, since $K_{max}$ grows much faster than $N_s$, meaning that your data-array will mostly consist of "unused" entries (indices whose digit sum in base $N+1$ is not equal to $N$). Also $K(\vec{N})$ can become very large and you might encounter overflow problems.

For your example, $N=2=M$, we have $K_{min}=N=2$, $K_{max}=2\cdot(2+1)^{2-1}=6$ and $N_s=\binom{2+2-1}{2}=3$, meaning there are the 3 numbers: $[2.0]_3=2\cdot 3^1+0\cdot 3^0=6$, $[1.1]_3=1\cdot 3+1=4$ and $[0.2]_3=0\cdot 3 + 2=2$ which map unto the 3 possible colorings RR,RB=BR,BB. The numbers $1=[0.1]_3$,$3=[1.0]_3$ and $5=[1.2]_3$ however don't map onto a valid coloring of the squares.

• Thank you for answering my old question! I'm a bit embarrassed because I do come from a physics background but did not see the direct correlation. – Thijs Miedema Aug 22 '17 at 6:17