Why is my project Euler problem 1 code returning an answer of 232169 instead of 233169 (when I input a 1000)?

Question

It's all in python, I understand it's not great or very efficient but I'm still learning. Any help on the subject title and on any efficiency gains would be much appreciated!

# Problem 1 - find all the multiples of 5 and 3 between 0 and a number (including the number).
import math

print("This programme finds all the multiples of 5 and 3 between 0 and a number (including the number) and also finds "
      "the sum.")

number = int(input("Input a natural number: "))
amount_of_threes = math.floor(number / 3) + 1
# The +1 is due to the 'stop' value not being included in a for loop (for i in range(start, stop))
multiples = []


for i in range(1, amount_of_threes):
    multiples.append(i * 3)

amount_of_fives = math.floor(number/5) + 1

for i in range(1, amount_of_fives):
    multiples.append(i*5)

# must get rid of duplicates such as 15 which is a common multiple
unique_multiples = []
for item in multiples:
    if item not in unique_multiples:
        unique_multiples.append(item)

unique_multiples.sort()

print(f"These are all the multiples of 5 and 3 below {number}: {unique_multiples}")

total = 0
for item in unique_multiples:
    total += item

print(f"{total} is the total of the multiples.")

I tried 1000 which was assigned to the variable 'number', got 232169, should have got 233169. a difference of a 1000.

Answer 1

Sayed, Welcome to stack overflow.

I want to answer to your question considering that you said "I'm still learning" python. I hope my answer is useful to you.

In your algorithm, you basically take these steps:

• calculate how many multiples of 3 there are in the range (hint).
• create a list with these multiples.
• calculate how many multiples of 5 there are.
• append these multiples to the list.
• create a list of unique multiples.
• iterate this list of multiples to verify it is not in the unique multiples list.
• sort the unique multiples list.
• get the total of the unique multiples in the list.

Some comments:

1. When you have a list of numbers, you don't need to sort it to get the total.

2. You can use the function sum to get the total of a list of numbers. It also iterates on the list, but it is a more elegant code.

3. In any given problem, try to iterate the least amount of times: only once if possible.

4. This algorithm has a complexity of N^2

Consider this code (iterating only once, checking the condition at the same time):

N = 1000

total = 0
for n in range(1, N):
    if n%3==0 or n%5==0:
        total += n

print(total)

Or taking advantage of python's rich expressiveness, in a one liner:

print(sum(n for n in range(1, N) if not (n%3 and n%5)))

This code has a complexity of N, that still could be prohibitive in some instances (try to solve it for N = 1e12).

Another solution, not using brute force could be this:

• calculate how many multiples of 3, 5 and 3*5 there are in the range (you had this hint in your first step)
• calculate the sum of numbers from 1 to n for each of the previous multiples
• multiply each sum by the multiple in question

The following code solves it with constant complexity:

N = 1000

sumto = lambda    n:  n*(n+1) // 2 # 1+2+3+4+...+n
mults = lambda m, n: (n-1) // m    # number of multiples of m below n

print(3*sumto(mults(3,N)) + 5*sumto(mults(5,N)) - 15*sumto(mults(15,N)))