1Jan/0821

## A fun little counting puzzle to start 2008

To start out the new year I came up with this little puzzle, in two parts. This puzzle makes a nice little Math exploration.

What is the sum of the digits in all of the integers between 1 and 2008 inclusive?

The second part of the problem is harder than the first part or not, depending on how you solved the first part.

What is the sumof the squaresof the digits in all of the integers between 1 and 2008 inclusive?

Have fun and show your work.

JackieJanuary 1st, 2008 - 13:24

Just to clarify, “between” being non-inclusive?

SolJanuary 1st, 2008 - 13:28

Hi Jackie,

Nice to see you here. I guess you’ve got a break today from your students!

I think of “between” as being inclusive but I guess not everyone does. Like, when someone asks me to think of a number between 1 and 10 I consider 1 and 10 to be fair game!

Please suggest how I can reword this problem to be clear.

Thanks.

JackieJanuary 1st, 2008 - 14:18

Ah – I consider between to be non-inclusive unless otherwise stated. I would say, “…integers between 1 and 2008 inclusive”.

Thanks for the clarification!

MathMomJanuary 1st, 2008 - 14:25

Generally I think of “from” as being inclusive, and “between” as being exclusive. You could always just add “inclusive” at the end of that phrase, to be clear.

I haven’t had time to think about the actual problem yet…

SolJanuary 1st, 2008 - 14:34

Ok ladies, I’ve added “inclusive” to the problem wording. Now get to work on solving it

MathMomJanuary 1st, 2008 - 14:46

From 000 – 999, each digit occurs 100 times in the hundreds place, 100 times in the tens place and 100 times in the ones place, for a total of 300 instances of each digit. Note that we are adding in extra leading zeros here, which is generally not ok, but since they contribute nothing to the sum of the digits, is ok and nice for symmetry.

From 1000 – 1999 we again have 100 of each digit in each of the hundreds, tens and ones places. We also have 1000 extra ones, in the thousands place.

from 2000 – 2008 we have an extra 9 twos, as well as a bunch of extra zeros, and an extra of each of 1 – 8, inclusive.

The sum of the digits from 1-999 is 300(0+1+2+3+4+5+6+7+8+9) = 300*45 = 13,500

The sum of the digits from 1000 – 1999 is 13,500 + 1,000 = 14,500

The sum of the digits from 2000-2008 is 2*9+(1+2+3+4+5+6+7+8) = 18+36 = 54

So the sum of the digits from 1-2008 (inclusive) is 13,500 + 14,500 + 54 = 28,054

——————

The sum of the squares of the digits from 1-999 = 300(1+4+9+16+25+36+49+64+81) = 300*285 = 85,500 (Is there a trick to adding up the squares? I just did it by hand.)

The sum of the squares of the digits from 1000 – 1999 = 85,500 + 1000 = 95,500

The sum of the squares of the digits from 2000 – 2008 = 9*4 + (1+4+9+16+25+36+49+64) = 36 + 204 = 240

So the sum of the squares of the digits of all the numbers from 1 – 2008 inclusive is

85,000 + 95,000 + 240 = 181,240

So, am I right? And I guess I didn’t do the first part the way you expected, since the second part wasn’t any harder my way.

SolJanuary 1st, 2008 - 15:52

You and I got the same answer to the first part so we might both have gotten it right!

We got a different answer to the second part and I see an arithmetic mistake in your work on that part. If you correct your error we’ll both have the same answer and maybe they’ll both be right!

For adding sums of squares there is a formula that says 1^2 + 2^2 + 3^2 + … + n^2 = n(n+1)(2n+1)/6. It’s painful to derive but you can prove it by induction or look for the visual approach referenced in my article on counting presents for the 12 days of Christmas. I just memorize the formula because I run into needing to add sums of squares very often.

My different way of doing part 1 was to find patterns and use the sum of the digits from 1 to 9 (INCLUSIVE) in a recursive way to compute the sum of the digits without counting how many of each digit there is. I can elaborate if you like.

Your way is how I did part 2. It wasn’t until I thought about adding part 2 to the problem that I realized that solving part 2 first made part 1 much easier.

SolJanuary 1st, 2008 - 15:58

Actually, I see two more mistakes that are different from arithmetic errors. The non-arithmetic errors are very similar to one another.

MathMomJanuary 1st, 2008 - 16:27

I actually noticed the two non-arithmetic errors (where I wrote 85,000 instead of 85,500 and same for 95K) when I was writing the post, but forgot to go back and fix them. The sum is correct for 85,500 + 95,500 although that isn’t what I wrote, and also isn’t what I needed to write, due to the arithmetic error:

I see now the arithmetic error where I added 10K instead of 1K. So the sum of the squares of the digits from 1000 – 1999 = 85,500 + 1000 = 86,500

And then the final total of the sums of the squares is 85,500 + 86,500 + 240 = 172,240. Do we match now?

MathMomJanuary 1st, 2008 - 16:28

Sol, I would certainly like to see the other way you did the first part of the problem.

SolJanuary 1st, 2008 - 17:03

We match now. I got 172,240 also.

Here’s a different way of doing part 1.

To save me some writing I’m going to define 2 functions:

sn(a,b) = the sum of the numbers between a and b, inclusive.

sd(a,b) = the sume of the digits of the numbers between a and b, inclusive.

We want to determine sd(1,2008).

sd(1,9)=sn(1,9)=1+2+3…+8+9=45

sd(10,19)=10×1 + sd(1,9)

sd(20,29)=10×2 + sd(1,9)

sd(30,39)=10×3 + sd(1,9)

…

sd(90,99)=10×9 + sd(1,9)

So, sd(10,99)=10xsn(1,9) + 9xsd(1,9)

=10×45 + 9×45 = 19×45 =855

So, sd(1,99)=sd(1,9)+sd(10,99)= 45+855 = 900

sd(100,199)=100×1 + sd(1,99)

sd(200,299)=100×2 + sd(1,99)

…

sd(900,999)=100×9 + sd(1,99)

So, sd(100,999) = 100xsn(1,9)+9xsd(1,99)

=100×45 + 9×900 = 4500+8100 = 12600

So, sd(1,999)=sd(1,99)+sd(100,999)

=900+12600=13500

sd(1000,1999) = 1000×1 + sd(1,999) = 1000+13500 = 14500

sd(1,1999) = sd(1,999) + sd(1000,1999) = 13500+14500 = 28000

sd(2000,2008) = 2×9+sd(1,8) = 18 + 36 = 54

So, sd(1,2008) = sd(1,1999)+sd(2000,2008) = 28000+54 = 28054

It’s tedious to do it this way but if I wanted to illustrate a recursive algorithm for students in an introductory computer programming course I could do it this way.

MathMomJanuary 2nd, 2008 - 11:14

Sol, I actually started thinking about the problem this way, but then realized that by thinking about zero as well, I could take advantage of the symmetry in 000-999 and do it faster. (I first noticed that 1-9 was a “special case” of 10-19, 20-29 etc…)

If you want to demonstrate recursion for intro CS students, use Fibonacci.

MathMomJanuary 2nd, 2008 - 11:18

Actually, for CS students, a nice example is the “sn” function itself. It can be computed iteratively or recursively, but it’s much more efficient if the “human in the loop” derives the formula n(n+1)/2 and just has the program apply the formula, because then it can be computed in O(1) time instead of O(n) for recursion or iteration.

The Mad HatterJanuary 3rd, 2008 - 19:11

Your fun little counting puzzle intrigued me in that was it possible to find an expression where you could input the digits of the number and then find the sum of the digits from 1 to that number. Now going from 1 to numbers like 100, 1000, 10000 is reasonably simple due to the repetitive nature of the summing, but to something like 1367 might be more fun.

Well what I found is if your four digit number is written as abcd, then a valid expression can be found (depends how much time you have I suppose).

S(abcd) = f(a,b,c,d)= 500a^2 + 100ab + 10ac + ad + 13001a + 50b^2 + 10bc + bd + 851b + 5c^2 + cd + 41c + d^2/2 + d/2

giving S(1367) = f(1,3,6,7) = 17568

and S(2008) = 28054

Now it looks rather daunting in its expanded form, but some really nice patterns emerge when collecting terms.

1000 a(a-1)/2 + (100b+10c+d+1)a + 45(100a) +

100 b(b-1)/2 + (10c+d+1)b + 45(100a+10b) +

10 c(c-1)/2 + (d+1)c + 45(100a+10b+c) +

d(d+1)/2

I’m wondering if the sum of the digits from 1 to abcde might be given by:

10000 a(a-1)/2 + (1000b+100c+10d+e+1)a + 45(1000a) +

1000 b(b-1)/2 + (100c+10d+e+1)b + 45(1000a+100b) +

100 c(c-1)/2 + (10d+e+1)c + 45(1000a+100b+10c) +

10 d(d-1)/2 + (e+1)d + 45(1000a+100b+10c+d) +

e(e+1)/2

Maybe someone could verify these results for me, maybe I lost it somewhere. But hey … it was fun just to play around with it a bit. In case you’re wondering … no, I didn’t worry about the second part – not that much time

SolJanuary 3rd, 2008 - 21:53

@Mathmom: I don’t disagree about the efficiency of some forms of computation over others. Sometimes, though, I like to do a problem recursively for its elegance or intuitive nature even if it takes longer to compute.

@Mad Hatter – Wow! I’m going to have to spend some time and see if I can derive the formula you derived. That looks quite cool! I didn’t think there would be a closed form formula.

MathMomJanuary 3rd, 2008 - 21:57

Sol, it all depends why you’re writing the program. Sometimes efficiency counts, other times it matters little.

Mad Hatter,if I get a chance, I’ll see what I can do with your idea as well.

DerekMay 15th, 2008 - 17:13

The first part of the question is on the gausse grade 7 contest.

angus beef burgersMay 20th, 2008 - 06:26

The answer issssssssss 57085. Don’t ask how I know I just know!!

Chicken burgersMay 20th, 2008 - 06:27

Got to KFC. THE TASTE LIVES HERE!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!11

Pork chop Rice FOR ONLI 9.99$!May 20th, 2008 - 06:29

MY NAME SAYS IT ALL!! GO TO MUCHA WOK FOR A FREE SAMPL( WELL FREE IF YOUR GONNA PAY FOR IT…)

mike and ikeMay 20th, 2008 - 06:30

CandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandyCandy