Re (tilly) 1: Finding sum of all digits from 1 to 1 million.

[tilly]

Fencepost error. The spec says inclusive, and your C-style for loop does not include 1e6. Use a Perl-style foreach loop and you would be unlikely to make the same mistake.

But still this one is faster to do with pen and paper. Convince yourself of the following:

1. The total contributions from the 7'th (and higher) digits is the 1 in 1_000_000.
2. For each given digit from the first through the sixth, there are 100_000 times that it is 0, 100_000 times it is 1, and so on up to 100_000 times it is 9.
3. The answer is therefore 1 + 6*(0+1+2+3+4+5+6+7+8+9)*100_000.
4. Therefore the answer is 27_000_001.

Now with this insight, a good exercise would be to write Perl code that efficiently calculates the sum of all of the digits in a range of integers. (Hint: Break things up by digit, and try to count how many you are going to have of each kind first.)

[PrakashK]

a good exercise would be to write Perl code that efficiently calculates the sum of all of the digits in a range of integers.

Assuming sum(n) is the sum of all digits from 1 to n, sum_range(m, n) is the sum of all digits from m to n, and m < n, isn't the following true?

sum_range(m,n) = sum(n) - sum(m)

Or, did I totally get you wrong? /prakash

[tilly]

Off by one error again, your formula drops m from the answer. (And the obvious fix will need more cases if your range potentially includes negative integers.)

But still, you are essentially correct. After some wrapper logic, the problem really does boil down to being able to efficiently calculate the sum of the digits from 1 to n for any positive integer n.