1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – user25406 Oct 8 '16 at 14:29
  • $\begingroup$ You are correct, changed it now. $\endgroup$ – Thijs Miedema Oct 8 '16 at 15:27
  • $\begingroup$ keep in mind that adding 9 to a number does not change its sum of digits. $\endgroup$ – user25406 Oct 8 '16 at 18:36
  • $\begingroup$ 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). $\endgroup$ – Thijs Miedema Oct 9 '16 at 13:46
  • $\begingroup$ 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. $\endgroup$ – user25406 Oct 9 '16 at 16:02
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Thijs Miedema Aug 22 '17 at 6:17

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.