Solving Project Euler Problem no.1 (Python)

Question

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.

mult3 = [] #multiples of 3
mult5 = [] #multiples of 5
for i in range(1000):  
    if i % 3 == 0 and i % 5 != 0: #make sure its numbers are divisible by 3 but not 5
        mult3.append(i)
    if i % 5 == 0 and i % 3 != 0: #make sure its numbers are divisible by 5 but not 3
        mult5.append(i)

total3 = sum(mult3) #sum of all elements in mult3
total5 = sum(mult5) #sum of all elements in mult5
print(total3 + total5)

I was wrong with the answer of 200003. Had I misunderstood the question or are there any bugs in my code?
Link to the original question

What about numbers that are multiples of 15? The or is not exclusive here. — bereal
– bereal, Commented Sep 10, 2021 at 5:23
Programming looks ok, but logic fails. I think you should leave out another check of divisible of both number (eg. number 15, like bereal just told). — Antti A
– Antti A, Commented Sep 10, 2021 at 5:24
You are missing the numbers that are divisible by both 3 and 5 (or 15) — Diogenis Siganos
– Diogenis Siganos, Commented Sep 10, 2021 at 5:24
The mistake is obvious, you miss numbers that are multiples of both 3 and 5, like 15,30 and so on. Read the question. It says you have to sum numbers that are multiples of 3 OR 5, not exactly one of them. Change your condition to fit that. — Ron B.
– Ron B., Commented Sep 10, 2021 at 5:26
it's not obvious to the OP. no need to be condescending. just explain the issue and move on, like the previous commenters. — tdy
– tdy, Commented Sep 10, 2021 at 5:30

ShadowRanger · Accepted Answer · 2021-09-10 05:25:07Z

3

Your test explicitly retains numbers divisible by 3 but not 5, and divisible by 5 but not 3. Which means numbers divisible by both 3 and 5 aren't being retained. When it says "3 or 5", it's using the plain English meaning of inclusive-or (aka and/or), not an exclusive-or ("one or the other but not both").

answered Sep 10, 2021 at 5:25

ShadowRanger

158k12 gold badges221 silver badges315 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Alain T. · Accepted Answer · 2021-09-18 12:21:08Z

1

You can take the iterative approach: O(n)

s35 = sum(n for n in range(1000) if n%3 == 0 or n%5 == 0)

Or you can compute it mathematically: O(1)

n3  = (1000-1)//3    # number of multiples of 3  (includes multiples of 15)
n5  = (1000-1)//5    # number of multiples of 5  (includes multiples of 15)
n15 = (1000-1)//15   # number of multiples of 15 (counted twice)

s35 =  n3*(n3+1)//2*3 + n5*(n5+1)//2*5 - n15*(n15+1)//2*15

edited Sep 18, 2021 at 12:21

answered Sep 18, 2021 at 0:35

Alain T.

42.2k4 gold badges36 silver badges57 bronze badges

Collectives™ on Stack Overflow

Solving Project Euler Problem no.1 (Python)

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related