Generalized Project Euler 1: A sledgehammer to crack a nut

The problem

Project Euler 1 is one of the most asked questions on site. However I wanted to solve the more general problem of division.


Multiples of a list


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 in a list from start to stop, where
start and stop are natural numbers.

In the classical problem, this list would be [3, 5]. However I wanted to create a code that could solve [3, 2], [3, 2, 7] and really any combination of numbers. The naive solution is shown below

def sum_divisible_naive(divisors=[3, 5], start=0, stop=100):
    count = 0
    for num in xrange(start, stop):
        for d in divisors:
            if num % d == 0:
                count += num
                break
    return count

I do not want comment on this code, but include it as a way to test the correctness of my implementation. The above code is correct, but has a linear \$\mathcal{O}(n)\$ running time. I wanted to create something faster.
I did however run into some problems which made my code longer than wanted.

Improved algorithm

To find the number of numbers divisible by some number k between start and stop, I use

def divisible_by_k(k, start=0, limit=100):
    stop = int((limit-1)/float(k))
    return k*(stop+start)*(stop-start+1)/2

This is just a slightly modified version of the sum of the first n natural numbers. Take [2, 3] as an example. If I were to do

total = divisible_by_k(3) + divisible_by_k(5)

I would count too many numbers since there are some numbers which occur in both of the lists: [3, 6, 9, 12, 15] and [5, 10, 15]. To correct this we have to subtract all the multiples of \$15\$.

Another problem is with [6, 9], if we did it like above we would remove all multiples of \$6*9 = 54\$, however \$18\$ is the first number that occurs in both lists. A solution to this is to divide the product by

Your maths is much better than mine, and so I can't comment on it.

However your function remove_multiples can be simplified if you come at the problem in a different way.
It's normally easier to add to a new list, than to remove from an old one.

The way this works is rather than checking if all the numbers after the number you are adding are ok, you instead check if the number is ok, by looking at the numbers before it.
Then you can achieve a simpler function:

def remove_multiples(divisors):
    new_divisors = []
    divisors = sorted(set(divisors))
    for divisor in divisors:
        if not any(divisor % d == 0 for d in new_divisors):
            new_divisors.append(divisor)
    return new_divisors

The sorted(set(divisors)) from your old code allows us to say that any new_divisors is smaller than any divisors.
Unless you pass negatives to it.
From this we can go through the divisors, and if it's divisible by any of the new_divisors, then it's to be removed.

StackExchange Code Review Q#133612, answer score: 12