# Counting problem based on digital sum divisibility

A five digit number $$\overline{a_1 a_2 a_3 a_4 a_5}$$ is said to satisfy property P if $$a_i \in \{1,2,3,4,5,6,7 \} \quad \forall 1\leq i \leq 5$$. How many five digit numbers satisfy P such that $$k=a_1+a_2+a_3+a_4+a_5$$ is divisible by:
(a) $$3$$
(b) $$2$$
(c) $$4$$
(Separate sub questions).

The first method(which is really lengthy but worked) is separating each $$a_i$$ into remainders when divided by $$3,2,4$$ respectively and doing all lot of case work for the digital sum divisibility condition.

The final answer is of a very nice form:

(a)$$\frac{7^5-1}{3}$$ (b)$$\frac{7^5-1}{2}$$ (c)$$\frac{7^5-3}{4}$$

So I thought there should be a better approach. Although the number of five digits numbers leaving a particular remainder when divided by $$3$$ or $$2$$ or $$4$$ won't be equal, as the groups which each $$a_i$$ is divided into based on remainder(this isn't needed for the question though), are of unequal sizes(for all three cases). But given the answer form, I wondered if it is true that when the digital sum k is divided by a number, then they are equally distributed among all the possible remainders.

For example for case (a), we can divide $$k \in [5,35]$$ into groups of $$3$$ based on remainder when divided by $$3$$, then the groups are of sizes $$10$$ ($$0 \mod 3$$), $$10$$ ($$1 \mod 3$$), $$11$$ ($$2 \mod 3$$). The extra number in the last group ($$2 \mod 3$$) is $$5$$, and only one five number has $$k=5$$.

So is it correct to say that the from the total $$7^5$$ possible numbers, if we subtract this extra number to give a total $$7^5-1$$ numbers, these are equally divided into the three groups to give a total number of $$\frac{7^5-1}{3}$$ numbers(the answer)? Similar reasoning for case (b),(c).

Is there any other way to solve this question? I briefly also tried using multinational theorem and got that the required answer for case(a) is the sum of coefficients of $$x^{3n}, n=0,1,2,3,\ldots$$ in the expansion of $$(x+x^2+\ldots+x^7)^5$$ but I could make little to no progress in evaluating this.

## 1 Answer

You should consider these to be strings of digits as we do not use the properties of the number, just the sum of the digits. You can write a set of coupled recurrences for the number of strings that sum to the number with each remainder. For $$n$$ digits there is a total of $$7^n$$ strings. For the $$\bmod 4$$ case, let $$a(n)$$ be the number of strings with a remainder of $$0$$, $$b(n)$$ with remainder $$1$$, c(n) with remainder $$2$$ and $$d(n)$$ with remainder $$3$$. We have $$a(n)=a(n-1)+2b(n-1)+2c(n-1)+2d(n-1)=2\cdot 7^{n-1}-a(n-1)\\ a(1)=1$$ and similarly for the others except that the sequence starts with $$2$$ as there are $$2$$ digits of each remainder except $$0$$ The strings will be close to equally distributed so if you compute it in a spreadsheet and subtract $$a(n)-\frac 14\cdot7^n$$ you see it alternates $$\pm \frac 34$$ and we get $$a(n)=\frac 14\cdot \left(7^n+(-1)^n\cdot 3\right)$$ The rest will be $$b,c,d(n)=\frac 14\cdot \left(7^n-(-1)^n\right)$$