PyPE solution to PE problem 1

Registered by Scott Armitage

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

Sprints

Whiteboard

    ProjectEuler.net problem 1
    ==========================

    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:
        3+6+9+...+999 = 3*(1+2+3+...+333)
        5+10+15+...+995 = 5*(1+2+3+...+199)
        15+30+45+...+990 = 15*(1+2+3+...+66)

    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

(?)

Work Items

This blueprint contains Public information 
Everyone can see this information.

Subscribers

No subscribers.