If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
Its the simplest problem in this site (over 8 years old, and more than 55k people have solved it so far) and anyone who can implement an iteration in a program can solve this problem.
Some problems that my arise while doing this problem if youre a beginner -
The datatype you use maybe too small if you are using some old compiler as the answer is in 200-thousands.
1000 is not included in the sum.
Here's my code in C#:
namespace Euler_1
{
class Program
{
static void Main(string[] args)
{
int i, sum = 0;
for (i = 1; i < 1000; i++)
if (i % 3 == 0 || i % 5 == 0)
sum += i;
Console.Write(sum);
Console.Read();
}
}
}
Here's a single line solution in Python -
>>>sum([x for x in range(1000) if x % 3== 0 or x % 5== 0])
233168
This problem can be solved without programming using Arithmetic Progressions(AP).
Sum to n terms in an AP is given by S(n) = n/2 * (a + (n-1)d)
where 'a' is the first term and (n-1)d (we'll call this 'k' from now) is the last term.
Multiples of 3 below 1000 are 3,6, 9,12.....999.
This forms an AP.
Sum of this series can be given by S(x) = 333/2 * (3 + 999) [n = 333 because 333/3 = 333. So k = 333 * 3 = 999]
S(x) = 166,833
Similarly, multiples of 5 form an AP - 5,10,15,20.....995.
Sum is S(y) = 199/2 * (5 + 995) [n = (999/5) = 199.8 ==> n = 199. So k = 5 * 199 = 995]
S(y) = 99500.
S(x) + S(y) will contain multiples of LCM(3,5)=15 twice.
So we have to eliminate one set of multiples of 15 from the sum.
Sum of multiples of 15 = S(z) = 66/5 * (15 + 990) [n = 999/15 = 66. So k = 15 * 66 = 990]
S(z) = 33165.
The final answer will be S = S(x)+S(y)-S(z) = 233168 which is the correct answer!
Goto www.projecteuler.net loads of problems like this.
