A "Good Number" is a number whose difference between the sum of its digits at even places and the sum of digits at odd places is $1.$

For example, $234563$ is a good number.

Digits at odd location are $3,5,3$ (unit place is location 1).
Digits at even location are $2,4,6$.
Diff $=(2+4+6)-(3+5+3)=12-11 = 1$.

And 123456 is not a good number, because diff=$(5+3+1)-(2+4+6)=9-12 = -3$.

Good Numbers from 1 to 100 are $$10,21,32,43,54,65,76,87,98$$ So my question is, in a given range, like 1 to 100 or 1 to 1000 for instance is there a way to find out how many numbers in the range are good numbers without actually having to test each number?

I figured out that all good numbers when divided by 11 would yield a remainder 10. But the converse is not true (if 109 is divided by 11 would yield a remainder 10, but it is not a good number).

I also came across a similar question where given a range we need to find the numbers that on finding the difference between Sum of digits at even location and Sum of digits at odd location would yield a prime number. Since finding difference between the sum of even and odd positioned digits is the base for both the problems it would be of great help if someone could help me with this...

Thanks in advance.....


Several simplifications are possible. First, consider numbers with the same number of digits at a given time, so the range should be 100-999 instead of 1-1000. You have already established the result from 1-99, and if you really want 1-1000 you could just notice that 1000 needs to be counted.

It looks like when you say difference, you mean signed difference: 23 doesn't count because the sum of the evens is one less than the sum of the odds.

Consider the case of $n$ digits with $n$ even ($n$ odd will be similar). Let $m=\frac n2$. You are interested in how many ways there are to get $m$ numbers in the range $0$ to $9$ to make a given sum. So you can define $N(m,p$) as the number of ways to have $m$ numbers in this range add up to $p$ for the odd places. There is some perturbation for the odd places as you don't allow a leading zero. In this case, $N(2,1)=1, N(2,2)=2, \ldots N(2,9)=9, N(2,10)=9 , \ldots N(2,18)=1$ Then define $M(m,p)$ similarly for the even places, $M(2,0)=1, M(2,1)=2, \ldots M(2,9)=10, M(2,10)=9 , \ldots M(2,18)=1$. Now you can find $\sum N(m,i)M(m,i-1)$ to get the total.

  • $\begingroup$ :Sir,thanks for ur reply...but i still couldnt clearly understand your explanation...can you please trace it with an example???...atleast for the minimum value,n=2.... $\endgroup$ – Jayanth Sep 19 '12 at 16:28
  • $\begingroup$ @Jayanth: The example N and M I gave are for a four digit number. $N(2,9)=9$ says there are $9$ different combinations of numbers that can go in the first and third positions that sum to $9$. These are $18, 27, 36, \ldots$. If the odd positions sum to $9$, the even positions need to sum to $8$. Since $M(2,8)=9$ there are $9\cdot 9=81$ four digit numbers where the odd positions sum to $9$ and the even ones sum to $8$. You need to sum over all the possibilities for the sum of the odds. $\endgroup$ – Ross Millikan Sep 19 '12 at 16:51
  • $\begingroup$ :Sir,thanks a lot..i got ur logic..but then if n=8 then there are 4 odd positions and 4 even positions and so we have to check for ∑N(m,i)M(m,i-1)..but here i ranges from 1 to 36.ie)the maximum sum that could be obtained can be 36..so we need to check for a lot of possibilities..is there any another efficient method other than this that could be possibly used to solve the problem??and also this calculates the number of elements in between the same number of digits.ie)either from 100-999 or 1000-9999....what if i need to find the numbers between 5000-8500 or 7800-9100...??? $\endgroup$ – Jayanth Sep 19 '12 at 18:02
  • $\begingroup$ @Jayanth: You are right that you have 36 possibilities to check for 8 digits, but that doesn't seem a lot to me. Certainly many less than 10^8. It would be nice to have a closed form for N and M, but I don't know one. If an approximate answer is good enough, you could use the normal approximation to the binomial distribution. A computer with a big number package will deal with numbers of a few thousand digits easily. $\endgroup$ – Ross Millikan Sep 20 '12 at 13:04
  • $\begingroup$ @Jayanth: other ranges than a decade are possible. If you start at 5000 you can feed that into the calculation of N and M pretty easily-the first digit only has 5 possibilities, not 9. If you want to start at 7800 it is more work-I would do the first two digits of N and M together then, so the first two digits could sum to 8 in 1 way, 9 in 2 ways, and take a jump at 15 as 78 comes in. Certainly it is not as clean, but the problem isn't as clean either. $\endgroup$ – Ross Millikan Sep 20 '12 at 13:08

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.