Member Avatar for brett.warren.1612

Hey, I tryed the first problem of the Euler project, but for some reason the code bellow is not give me the correct answer:

def multiple_sum(multiple=3):
    x = 0
    for n in range(0, 1000):
        if not (n % multiple):
            x += n
    return x

print multiple_sum(5) + multiple_sum(3)

It is giving me 266333, where it should be giving me 266168
The problem discription is here:

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.

Edit: GOD DAMN THAT RANGE FUNCTION, SHOULD HAVE ADDED ONE TO INCLUDE 1000.

However, this doesn't fix my problem. I'm still hopelessly confused on that front.

Edited by brett.warren.1612
  • 2 Contributors
  • 2 Replies
  • 141 Views
  • 33 Minutes Discussion Span
  • Latest Post Latest Post by brett.warren.1612

Dani AI

Generated

The incorrect total came from double-counting numbers divisible by both 3 and 5 (multiples of 15) — called this out. Also note the problem asks for numbers "below 1000", so range(1000) (numbers 0..999) is correct; adding 1 would include 1000 and change the problem.

A simple, readable fix is to iterate once and include numbers divisible by 3 or 5:

limit = 1000
answer = sum(n for n in range(limit) if n % 3 == 0 or n % 5 == 0)
print(answer)  # 233168

A constant-time approach uses arithmetic series and inclusion–exclusion. Sum of multiples of k below limit equals k * m * (m + 1) // 2 where m = (limit - 1) // k. Use that to subtract the overlap (LCM 15):

def sum_multiples(k, limit):
    m = (limit - 1) // k
    return k * m * (m + 1) // 2

limit = 1000
ans = sum_multiples(3, limit) + sum_multiples(5, limit) - sum_multiples(15, limit)
print(ans)  # 233168

Notes and pitfalls: use integer division (//) to avoid floats (important in Python 3); be careful with off-by-one when the problem wording is "below N" vs "up to and including N"; for more divisors inclusion–exclusion requires computing LCMs of combinations, which gets complex — in those cases a single-pass test (if n%a==0 or n%b==0 or ...) or a set-based union of ranges is simpler. This resolves the discrepancy observed by and gives the Project Euler answer 233168.

Recommended Answers

All 2 Replies

Member Avatar for sepp2k

You're counting all multiples of 15 twice (once as multiples of 3 and once as multiples of 5).

Edited by sepp2k
Member Avatar for brett.warren.1612

Oh, of coruse. Thanks again, I think I've got it from here.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.