Calculating heavy numbers in a given range? I had an interview question a couple days ago involving the calculation of the amount of heavy numbers between in a given range. I came up with a basic solution, which was to iterate over the entire range and test for the heaviness of each number. I realized right away that its a terribly inefficient method of solving the problem. In the interest of educating myself I have been tackling the problem today to try and learn more about this type of problem. Its tough for me, because I don't have a super strong mathematics background but I'm trying to learn.
Basically, the problem goes like this:
Take any 2 numbers from 0 to 200,000,000. In that range, calculate the number of "heavy numbers". This is calculated by adding together all of the component digits and then dividing by the number of components. If the average is greater than 7, the number is considered heavy.
Example:
1234: 1+2+3+4/4 = 2.5 (not heavy)
8996: 8+9+9+6/4 = 8 (heavy)

So given the range 1002 - 12089, my naive approach is to iterate over each number between and calculate its weight. This approach quickly falls apart when dealing with very large number ranges.
I've done quite a bit of searching via Google and Bing and beyond a couple of posts where people have copy/pasted verbatim the question, I find almost no information about this kind of problem. I suspect that this type of problem is called something other than "heavy numbers" but I'm at a loss as to what that the terminology is. 
Here is a link to one such discussion: http://groups.google.com/group/algogeeks/browse_thread/thread/a1b824107afe3801
I'm hoping that someone who is familiar with type of scenario can explain alternative ways to solve the problem in a simple manner, and that I might ask follow up questions until I understand.
Thanks for reading. 
 A: If you want to calculate the answer exactly, one way to go is using generating functions (which is the same as dynamic programming).
Let's restrict ourselves first to some particular length, say $5$. We are going to calculate how many numbers with exactly $5$ digits have digits that sum to more than $35$.
The generating function for the sum of digits is
$$ (x+\cdots+x^9)(1+\cdots+x^9)^4. $$
You want to sum the coefficients of $x^k$ for all $k \geq 36$.
As mentioned above, this approach reduces to a dynamic programming algorithm. The algorithm computes inductively how many number of length exactly $l \leq 5$ have a certain digit sum. I'll leave you the details.
In case your range is more complicated, you break it up. First, we can handle something like "all numbers of length 5 starting with 1,2,3" by adjusting the first factor. Second, you can break up an arbitrary range $[0,n]$ into ranges of that form (plus extra "constant" digits that affect only the choice of the threshold). Finally, use $[l,h] = [0,h] - [0,l-1]$ to handle an arbitrary range.
If you only want to estimate the number, the way to go is the Central Limit Theorem, or rather Large Deviation Theory. The sum of digits of an $n$-digit number is approximated by a normal variable - but not far from the mean, which is what you're looking for. Still, there are estimates on the error of the normal approximation which can be useful. Methods from Large Deviation Theory may give more accurate results.
A: I have investigated this issue a bit more depth and implemented two solutions. Please refer to
http://cpluspluslearning-petert.blogspot.co.uk/2014/07/dynamic-programming-heavy-numbers.html
http://cpluspluslearning-petert.blogspot.co.uk/2014/07/dynamic-programming-heavy-numbers-part.html
