5 digits numbers such that when the sum of digits divided by 4 leaves remainder 2.

Question

How many 5 digits numbers such that when the sum of digit divided by 4 leaves remainder 2.

Example:- Consider a 5 digit number- $(x1,x2,x3,x4,x5)$ Then $(x1+x2+x3+x4+x5)$ must be of form $(4n+2)$

I tried this (x+x²+x³...+x^9)(1+x+x²+x³....+x^9)⁴

In this sum of coefficient of x^(2,6,10,14....42)

But this involve lot of calculation.!

Please some one provide me something different and smarter solution.

Answer 1

Call digits $0$ and $1$ small, and digits $2-9$ large.

Given $n\ge 1$, we divide the $n$-digit numbers into two sets: $S$, which contains all numbers consisting entirely of the small digits $0$ and $1$; and $L$, which contains all other numbers. Note that:

• $|S|=2^{n-1}$, because each digit apart from the initial $1$ is either $0$ or $1$;
• $|L|=9\cdot 10^{n-1}-|S|$, because there are $9\cdot 10^{n-1}$ $n$-digit numbers in total.

Now, if $c$ and $d$ are large digits, then the number of numbers whose first large digit is $c$ is equal to the number of numbers whose first large digit is $d$. And because the large digits are evenly distributed modulo $4$, this means that the digit sums of the numbers in $L$ are also evenly distributed modulo $4$. So the number of numbers in $L$ with a given digit sum modulo $4$ is $|L|/4$.

This just leaves $S$. But this is easy: the number of numbers in $S$ with digit sum $k$ is the number of ways of choosing $k-1$ positions for the $1$'s (given that the first digit has to be $1$). This is the binomial coefficient $\binom{n-1}{k-1}$.

Thus we see that the number of $n$-digit numbers with a digit sum equal to $m$ mod $4$ is equal to $|L|/4+\sum_k\binom{n-1}{k-1}$, where the sum is taken over all $k$ with $1\le k\le n$ and $k\equiv m$ mod $4$.

Here is a table of the number of $n$-digit numbers with a given digit sum modulo $4$, for $n=1$ to $6$: $$ \begin{array}{c|lcr} n & |L|/4 & 0\bmod 4 & 1\bmod 4 & 2\bmod 4 & 3\bmod 4 \\ \hline 1 & 2 & 2 & 3 & 2 & 2\\ 2 & 22 & 22 & 23 & 23 & 22\\ 3 & 224 & 224 & 225 &226 &225\\ 4 & 2248 & 2249 & 2249 & 2251 & 2251\\ 5 & 22496 & 22500 & 22498 & \color{red}{22500} & 22502\\ 6 & 224992 & 225002 & 224998 & 224998 & 225002\\ \end{array} $$

Answer 2

Continuing your thought of line (using generating functions): for $n\in \{0,1,...,10\}$:

$$[x^{4n+2}](x+x^2+x^3...+x^9)(1+x+x^2+x^3....+x^9)^4=\\ [x^{4n+1}]\left(\frac{1-x^{9}}{1-x}\right)\left(\frac{1-x^{10}}{1-x}\right)^4=\\ [x^{4n+1}](1-x^{9})(1-x^{10})^4(1-x)^{-5}=\\ [x^{4n+1}]\sum_{i=0}^{1}{1\choose i}(-x^9)^i\sum_{j=0}^4{4\choose j}(-x^{10})^j\cdot \sum_{k=0}^{\infty}{4+k\choose k}x^k.$$ Cases for $n=0,1,....,10$ and $(i,j,k)$: $$\begin{array}{c|l|r} 4n+1&(i,j,k)&\text{Total}\\ \hline 1&(0,0,1)&5\\ 5&(0,0,5)& 126\\ 9&(0,0,9)-(1,0,0)&714\\ 13&(0,0,13)-(0,1,3)-(1,0,4)&2,170\\ 17&(0,0,17)-(0,1,7)-(1,0,8)&4,170\\ 21&(0,0,21)-(0,1,11)+(0,2,1)-(1,0,12)+(1,1,2)&5,460\\ 25&(0,0,25)-(0,1,15)+(0,2,5)-(1,0,16)+(1,1,6)&4,998\\ 29&(0,0,29)-(0,1,19)+(0,2,9)-(1,0,20)+(1,1,10)-\\ &(1,2,0)&3,162\\ 33&(0,0,33)-(0,1,23)+(0,2,13)-(0,3,3)-(1,0,24)+\\ &(1,1,14)-(1,2,4)&1,330\\ 37&(0,0,37)-(0,1,27)+(0,2,17)-(0,3,7)-(1,0,28)+\\ &(1,1,18)-(1,2,8)&330\\ 41&(0,0,41)-(0,1,31)+(0,2,21)-(0,3,11)+(0,4,1)-\\ &(1,0,32)+(1,1,22)-(1,2,12)+(1,3,2)&35\\ \hline \text{Total}&&22,500\\ \end{array}$$ Likewise, all four options ($0,1,2,3 \mod 4$): $$\begin{array}{c|c|c|c} n&4n-1&4n&4n+1&4n+2\\ \hline 0&-&1&5&15\\ 1&35&70&126&210\\ 2&330&495&714&992\\ 3&1330&1725&2170&2654\\ 4&3162&3675&4170&4620\\ 5&4998&5283&5460&5520\\ 6&5460&5283&4998&4620\\ 7&4170&3575&3162&2654\\ 8&2170&1725&1330&992\\ 9&714&495&330&210\\ 10&126&70&35&15\\ 11&5&1&-&-\\ \hline \text{Total}&22500&22498&22500&22502\end{array}$$ Note: Although I used a calculator for binomials, it was like digging a well with a needle. I wonder if this method can be simplified in any way?!

Answer 3

Let us first see the required numbers in

$10000-10010$

One or two digit number in front of five digit number represent the sum of digits of the five digit number

$10000-1

10001-2

10002-3

10003-4

10004-5

10005-6

10006-7

10007-8

10008-9

10009-10$

Number of required number in the above series are 3. If we see the next series(2) of next 10 numbers. The required numbers are 3. And same for the series(3) (From 10020-10029) number of requires numbers are 2. And for fourth series no. Of required numbers are 2.

And the sequence of required numbers per ten first ten digits is-

$3 3 2 2 3 3 2 2 3 3 2 2......3 3 2 2$

Total number between $10000-99999$ are $90000$.

No.s of 2's and 3's are =$\frac{90000}{10}=9000$

No.s of 2's or 3's are $\frac{9000}2=4500$

Therefore the required no.s are $$4500*(2+3)=22500$$