Sum of an arithmetic series: all the numbers < 1000, not multiples of 3 or 5

apple2357

Full Member
Joined
Mar 9, 2018
Messages
520
I am trying to get my head around the finding the sum of all the numbers under 1000 that are not multiples of 3 or 5 ?

I can find the sum of the first 1000 numbers easily enough by doing 1001x500
And i can pull out the multiples of 3 and then multiples of 5 but getting confused around the ones which are both?
Or is there a more interesting way to think about it. Any hints /prompts ?
 
I am trying to get my head around the finding the sum of all the numbers under 1000 that are not multiples of 3 or 5 ?

I can find the sum of the first 1000 numbers easily enough by doing 1001x500
And i can pull out the multiples of 3 and then multiples of 5 but getting confused around the ones which are both?
Or is there a more interesting way to think about it. Any hints /prompts ?
Well, you are definitely thinking along the right track although if you are looking for the sum of numbers through 999, why you use 1000 * 1001 / 2 is a mystery. What are the exact words of the problem?

Suppose s = the sum of all numbers under n, a the sum of all multiples of 3 that are under n, b = the sum of all multiples of 5 under n, and c = the sum of all mutiples of 15 that are under n.

So n - (a + b) subtracts c twice. Instead,

\(\displaystyle n - ( a + b - c).\)
 
I am trying to get my head around the finding the sum of all the numbers under 1000 that are not multiples of 3 or 5 ?

I can find the sum of the first 1000 numbers easily enough by doing 1001x500
And i can pull out the multiples of 3 and then multiples of 5 but getting confused around the ones which are both?
Or is there a more interesting way to think about it. Any hints /prompts ?

It can help to first look at some specific numbers. Consider just numbers from 1 to 20:

Code:
[FONT=courier new]All           : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Mult of 3     :       3,       6,       9,         12,         15,         18,       
Mult of 5     :             5,             10,                 15,                 20
Mult of 3 or 5:[FONT=courier new]       3,    5, 6,       9, 10,     12,         15,         18,     20[/FONT]
[/FONT][FONT=courier new][FONT=courier new]Mult of both  :                                                15                    [/FONT]
Not mult      : 1, 2,    4,       7, 8,        11,     13, 14,     16, 17,     19,   [/FONT]

To count the numbers that are multiples of either 3 or 5, you can count those that are multiples of 3, and those that are multiples of 5; but when you add those together, you will have counted those that are multiples of both 3 and 5 (that is, multiples of 15) twice.

How can you combine these counts to get just the non-multiples?
 
The 1000 breaks down this way:
066: divisible by 3 and 5
267: divisible by 3, not by 5
134: divisible by 5, not by 3
533: leftover

Look for "tricks", like all the numbers divisible by 15 = those divisible by 3 and 5
 
I have tried this ...

1)Sum of the numbers 1 to 1000 is 1001x500
2)sum of the multiples of 3 ( 3+6+9+....+ 999) = 3x(1+2+3+....+333) = 3 x (334x333)/2
3)sum of the multiples of 5 ( 5+10+15+...+1000) = 5x(1+2+3+....+200) = 5x(201x200)/2


so if i do 1)- 2) - 3) it will take out multiples of 15 twice so i need to add multiples of 15 back on?
Does that make sense?

Got to be an easier way?

( I think there might be an issue here to do with 'under 1000' which is the original question, but i am less concerned about that right now, just exploring a method)
 
Last edited:
Can anyone tell me if i use excel whether there is a function that will isolate multiples of 3 or 5 somehow in a new column?
 
I have tried this ...

1)Sum of the numbers 1 to 1000 is 1001x500
2)sum of the multiples of 3 ( 3+6+9+....+ 999) = 3x(1+2+3+....+333) = 3 x (334x333)/2
3)sum of the multiples of 5 ( 5+10+15+...+1000) = 5x(1+2+3+....+200) = 5x(201x200)/2


so if i do 1)- 2) - 3) it will take out multiples of 15 twice so i need to add multiples of 15 back on?
Does that make sense?

Got to be an easier way?

( I think there might be an issue here to do with 'under 1000' which is the original question, but i am less concerned about that right now, just exploring a method)

Yes, add the number of multiples of 15 back on. What do you get?

Yes, you should make sure you know whether 1000 is meant to be included; but since that is a multiple of 5, it won't make any difference.

This IS the easier way! (Using Excel or something could be easier, but that's cheating; if you do this right, you can sum far larger lists of numbers than Excel could hold, and with far fewer calculations.)
 
Can anyone tell me if i use excel whether there is a function that will isolate multiples of 3 or 5 somehow in a new column?

On way is =IF(A1=INT(A1/3)*3,A1,""). This divides A1 by 3, rounds down, and multiplies by 3 to get the number back, then displays it if it matches (that is, if the rounding didn't change the number).

An equivalent is =IF(MOD(A1,3)=0,A1,""). This finds the remainder and checks if it is zero.

You'll want to check for both 3 and 5, and combine them with "or" or something.

Of course, this is something I would do just to check my result.
 
So i have worked out the answer

as 500500 ( sum 1 to 1000) - 166833 ( sum of multiples of 3)-100500 ( sum of multiples of 5) +33165 ( sum of multiples of 15) = 266 332

And I have managed to verify it using excel!

Looking at the column in excel of 1 to 1000 with multiples of 5 and 3 removed, i do wonder if there is another approach:

The sum is : 1+2+4+7+8+11+13+14+16+17+19+22+23+26 + 28+29 + 31+32+ 34+ 37+38+ 41+ 43+ 44+ 46+47+ 49

The pattern of the pairs above makes we wonder !
 
I have tried this ...

1)Sum of the numbers 1 to 1000 is 1001x500
2)sum of the multiples of 3 ( 3+6+9+....+ 999) = 3x(1+2+3+....+333) = 3 x (334x333)/2
3)sum of the multiples of 5 ( 5+10+15+...+1000) = 5x(1+2+3+....+200) = 5x(201x200)/2


so if i do 1)- 2) - 3) it will take out multiples of 15 twice so i need to add multiples of 15 back on?
Does that make sense?

Got to be an easier way?

( I think there might be an issue here to do with 'under 1000' which is the original question, but i am less concerned about that right now, just exploring a method)
Assuming the problem is find the sum of all positive numbers \(\displaystyle \le \) 1000 after excluding any number that is a multiple of 3 or 5, it is easy.

\(\displaystyle n = \text { number desired.}\)

\(\displaystyle s = \text { sum of positive integers } \le 1000.\)

\(\displaystyle a = \text { sum of positive multiples of 3 } \le 1000.\)

\(\displaystyle b = \text { sum of positive multiples of 5 } \le 1000.\)

\(\displaystyle c = \text { sum of positive multiples of 15 } \le 1000.\)

\(\displaystyle n = s - (\{a + b\} - c) = n - (a + b) + c = n - a - b + c.\)

That takes no time at all.

\(\displaystyle \displaystyle s = \sum_{j=1}^{1000} j = \dfrac{1000 * 1001}{2} = 500500.\)

\(\displaystyle \displaystyle a = 3 * \sum_{j=1}^{333} j = 3 * \dfrac{333 * 334}{2} = 166833.\)

\(\displaystyle \displaystyle b = 5 * \sum_{j=1}^{200} j = 5 * \dfrac{200 * 201}{2} = 100500.\)

\(\displaystyle \displaystyle c = 15 * \sum_{j=1}^{66} j = 15 * \dfrac{66 * 67}{2} = 33165.\)

Use the sum of integers up to p four times on a calculator.

\(\displaystyle n = 500500 - 166833 - 100500 + 33165 = 266332.\)

I am not sure why you think there is an easier way. That seems rather easy to me.
 
So i have worked out the answer

as 500500 ( sum 1 to 1000) - 166833 ( sum of multiples of 3)-100500 ( sum of multiples of 5) +33165 ( sum of multiples of 15) = 266 332

And I have managed to verify it using excel!

Looking at the column in excel of 1 to 1000 with multiples of 5 and 3 removed, i do wonder if there is another approach:

The sum is : 1+2+4+7+8+11+13+14+16+17+19+22+23+26 + 28+29 + 31+32+ 34+ 37+38+ 41+ 43+ 44+ 46+47+ 49

The pattern of the pairs above makes we wonder !

Well, your observation of a repeating pattern does suggest an alternative method, though to my mind it isn't easier (and I made several mistakes before getting it right).

The pattern of numbers not divisible by 3 or 5 repeats every 15, since that is the LCM. In each set of 15, there are 8 numbers we want to include.

In 0 to 1000, we have 1000/15 = 66 2/3, so there are 66 sets of 15, with 10 extra at the end.

The kth set of 15 starts at 15k (the first having k=0) and consists of 15k+1, 15k+2, 15k+4, ..., 15k+14. Its sum is 8*15k + (1+2+4+7+8+11+13+14) = 120k + 60.

We want to add up 66 of these: 120(0+1+2+...+ 65) + 66*60 = 120*65*66/2 + 66*60 = 261,360.

The last 10 are 991+992+994+997+998 = 5*990 + (1+2+4+7+8) = 4972.

Add these together, and the total is 266,332.

We could instead have added up 67 sets and subtracted the three extra numbers at the end.

But the other method is the standard way to solve this kind of problem, and is worth knowing.
 
Assuming the problem is find the sum of all positive numbers \(\displaystyle \le \) 1000 after excluding any number that is a multiple of 3 or 5, it is easy.

\(\displaystyle n = \text { number desired.}\)

\(\displaystyle s = \text { sum of positive integers } \le 1000.\)

\(\displaystyle a = \text { sum of positive multiples of 3 } \le 1000.\)

\(\displaystyle b = \text { sum of positive multiples of 5 } \le 1000.\)

\(\displaystyle c = \text { sum of positive multiples of 15 } \le 1000.\)

\(\displaystyle n = s - (\{a + b\} - c) = n - (a + b) + c = n - a - b + c.\)

That takes no time at all.

\(\displaystyle \displaystyle s = \sum_{j=1}^{1000} j = \dfrac{1000 * 1001}{2} = 500500.\)

\(\displaystyle \displaystyle a = 3 * \sum_{j=1}^{333} j = 3 * \dfrac{333 * 334}{2} = 166833.\)

\(\displaystyle \displaystyle b = 5 * \sum_{j=1}^{200} j = 5 * \dfrac{200 * 201}{2} = 100500.\)

\(\displaystyle \displaystyle c = 15 * \sum_{j=1}^{66} j = 15 * \dfrac{66 * 67}{2} = 33165.\)

Use the sum of integers up to p four times on a calculator.

\(\displaystyle n = 500500 - 166833 - 100500 + 33165 = 266332.\)

I am not sure why you think there is an easier way. That seems rather easy to me.


Yes not necessarily easier but just interesting or different from a mathematical point of view! Once i was shown a visual way of seeing why (1/4) + (1/4)^2 +(1/4)^3 +... was finite and it blew my mind. I know this is different, but was just curious!
 
Well, your observation of a repeating pattern does suggest an alternative method, though to my mind it isn't easier (and I made several mistakes before getting it right).

The pattern of numbers not divisible by 3 or 5 repeats every 15, since that is the LCM. In each set of 15, there are 8 numbers we want to include.

In 0 to 1000, we have 1000/15 = 66 2/3, so there are 66 sets of 15, with 10 extra at the end.

The kth set of 15 starts at 15k (the first having k=0) and consists of 15k+1, 15k+2, 15k+4, ..., 15k+14. Its sum is 8*15k + (1+2+4+7+8+11+13+14) = 120k + 60.

We want to add up 66 of these: 120(0+1+2+...+ 65) + 66*60 = 120*65*66/2 + 66*60 = 261,360.

The last 10 are 991+992+994+997+998 = 5*990 + (1+2+4+7+8) = 4972.

Add these together, and the total is 266,332.

We could instead have added up 67 sets and subtracted the three extra numbers at the end.

But the other method is the standard way to solve this kind of problem, and is worth knowing.


Thanks for this. Your idea above has made me think in columns, rather than rows:



1 2 4 etc...
16 17 19
31 32 34
46 47 49
61 62 64

etc...


I am going to work on this next!
 
Top