2
$\begingroup$

How do I find all of the numbers in a given range whose sum of digits equal to a given value?

For example:

Range : 100 - 9000

Value : 4

Result : 103, 112, 121, 130, 202, 211, 220, 301, 310, ..., 4000, ...

$\endgroup$
  • $\begingroup$ Hint: The digit sum is the same as the remainder on division by $9$ (well, almost...if $n>0$ is divisible by $9$ you get $9$, not $0$. en.wikipedia.org/wiki/Digital_root $\endgroup$ – lulu Feb 1 '16 at 12:30
  • $\begingroup$ Thank you. I just edit my question to not have sum of digits reduced to single digit. So, given a value (it can have more than one digit) need to find all of the number in a given range whose digit sum equal the given value. $\endgroup$ – sunilkumarba Feb 1 '16 at 12:33
  • $\begingroup$ Possible duplicate of Counting the numbers with certain sum of digits. $\endgroup$ – lulu Feb 1 '16 at 12:56
1
$\begingroup$

Observe that any four digit number larger than $4000$ will have a digit sum greater than $4$. Thus, the problem reduces to finding the number of three or four digit numbers with digit sum $4$.

For three digit numbers, let $x_2$ denote the hundreds digit, $x_1$ denote the tens digit, and $x_0$ denote the units digit. Then the number of three digit numbers whose digit sum is $4$ is the number of solutions of the equation $$x_2 + x_1 + x_0 = 4 \tag{1}$$ in the non-negative integers subject to the constraint that $x_2 \geq 1$. Let $x_2' = x_2 - 1$. Then $x_2'$ is a non-negative integer. Substituting $x_2' + 1$ for $x_2$ in equation 1 yields \begin{align*} x_2' + 1 + x_1 + x_0 & = 4\\ x_2' + x_1 + x_0 & = 3 \tag{2} \end{align*} which is an equation in the non-negative integers. A particular solution of equation 2 corresponds to placing two addition signs in a row of three ones. For instance, $$1 + 1 1 +$$ corresponds to the solution $x_2' = 1$, $x_1 = 2$, $x_3 = 0$, while $$1 + 1 + 1$$ corresponds to the solution $x_2' = x_1 = x_0 = 1$. Thus, the number of solutions of equation 2 is the number of ways two addition signs can be inserted into a row of three ones, which is $$\binom{3 + 2}{2} = \binom{5}{2}$$ since we must choose which two of the five symbols (three ones and two addition signs) will be addition signs.

For four digit numbers, let $x_2$, $x_1$, and $x_0$ be defined as above. Let $x_3$ denote the thousands digit. Then the number of four digit numbers whose digit sum is $4$ is the number of solutions of the equation $$x_3 + x_2 + x_1 + x_0 = 4 \tag{3}$$ in the non-negative integers subject to the constraint that $x_3 \geq 1$. Let $x_3' = x_3 - 1$. Then $x_3$ is a non-negative integer. Substituting $x_3' + 1$ for $x_3$ in equation 3, then simplifying yields $$x_3' + x_2 + x_1 + x_0 = 3 \tag{4}$$ Equation 4 is an equation in the non-negative integers. The number of solutions of equation 4 is the number of ways of inserting three addition signs in a row of three ones, which is $$\binom{3 + 3}{3} = \binom{6}{3}$$ since we must choose which three of the six symbols (three ones and three additions signs) will be addition signs.

In total, there are $$\binom{5}{2} + \binom{6}{3}$$ numbers between $100$ and $9000$ with digit sum $4$.

$\endgroup$

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.