Counting problem based on digital sum divisibility

Question

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.

Answer 1

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)$$