PyPE solution to PE problem 1
PyPE solution to PE problem 1
Blueprint information
- Status:
- Complete
- Approver:
- None
- Priority:
- Undefined
- Drafter:
- None
- Direction:
- Needs approval
- Assignee:
- None
- Definition:
- Approved
- Series goal:
- None
- Implementation:
- Implemented
- Milestone target:
- None
- Started by
- Scott Armitage
- Completed by
- Scott Armitage
Whiteboard
ProjectEule
===
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.
Solution
--------
We split this problem up into three parts. First, we find the sum of all
multiples of 3 that are below the limit. Next, we find the sum of all
multiples of 5 that are below the limit. Adding these two values, we have
double-counted all multiples of 15 that are below the limit. So, lastly,
we find the sum of these and subtract it.
These series correspond to:
We notice that the limit of each of the sums on the right-hand side is
equal to the value of the limit on the left-hand side divided by the
multiplier and rounded down to the nearest integer (i.e. integer division).
We can summarize the right-hand sum in the above equations as
1+2+...+p = 1/2*p*(p+1)
Combining these all together, we get that
ans = sum_div(3) + sum_div(5) - sum_div(15),
where
sum_div(n) = n*p*(p+1) // 2
and
p = limit // n.
Answer
------
233168