My code is inefficent, multiples of 3 and 5 from Project Euler but with a 10 second timeout conditon

Question

Problem Statement

This problem is a programming version of Problem 1 from projecteuler.net

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 N.

Input Format

First line contains T that denotes the number of test cases. This is followed by T lines, each containing an integer, N.

Output Format

For each test case, print an integer that denotes the sum of all the multiples of 3 or 5 below N.

Constraints

1≤T≤105 
1≤N≤109

Sample Input

2
10
100

Sample Output

23
2318

---

I'm doing the very first Project Euler question but with a time constraint for an extra challenge. If the process takes more than 10s it will autofail.

Here is a sample input:

2   # number of test cases
10  # first test case
100 # second test case

Here is my code:

test_case = int(input())
for x in range(0, test_case):       # Loops after every test case
    stop_value = int(input())

    answer = 0

    threes = 0
    while threes < stop_value:      # Checks 3s
        answer += threes
        threes += 3

    fives = 0
    while fives < stop_value:       # Checks 5s
        answer += fives
        fives += 5

    commons = 0
    while commons < stop_value:     # Check 15s
        answer -= commons
        commons += 15

    print(answer)

The problem will not show me the inputs when it is grading my solution but I am going to assume that one of the test cases is checking up until 10^9 which will take a lot more than 10 seconds to run.

---

Previous attempt note: Originally I had a simpler code which ran a for loop from 0 to stop_value which failed once the stop_value got too big so I attempted to make while loops (which I showed above) skipping in between everything.

---

Next attempt:

I tried to find the maximum multiple of each number and multiples that term by their own factorials but I get the wrong output.

To explain my thought process on why, I considered 10 as an example, 10//3 = 3. If I did 3!*3 it would be [1*3,2*3,3*3] = [3,6,9] which is all the multiples of 3 to the stop_value Edit: I noticed this is implemented incorrectly, I am currently considering for-loops for the factorials.

import math

test_case = int(input())
for x in range(0, test_case):       # Loops after every test case
    stop_value = int(input())

    threes = stop_value // 3
    fives = stop_value // 5
    commons = stop_value // 15

    answer = math.factorial(threes)*3 + math.factorial(fives)*5 - math.factorial(commons)*15

    print(answer)

Your Output (stdout)

13
26049952856435659498719093244723189200

Expected Output

23
2318

Answer 1

This is a generalization of the sum of natural numbers. The general formula for a step size of k and a maximum number n (with n divisible by k) is: n / k / 2 * (n + k).

def euler1 (n):
    max3 = range(0, n, 3)[-1]
    max5 = range(0, n, 5)[-1]
    max15 = range(0, n, 15)[-1]

    sum3 = (max3 + 3) * max3 // 3 // 2
    sum5 = (max5 + 5) * max5 // 5 // 2
    sum15 = (max15 + 15) * max15 // 15 // 2

    return sum3 + sum5 - sum15

>>> euler1(10)
23
>>> euler1(100)
2318
>>> euler1(10**100)
23333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333331666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666668

Answer 2

Although I completely agree that you should use the formula for the sum of natural numbers as poke stated, this can still be done generating all the numbers. For more information on solving your problem analytically, have a look at this question from mathematics.SE

As for generating and summing all numbers, this was the fastest method I could quickly come up with:

n=10**9; sum(xrange(0,n,3)) + sum(xrange(0,n,5)) - sum(xrange(0,n,15))

This line takes about 5 seconds to execute on my i5, but it consumes a considerable amount of memory