Python algorithm doesn't yields correct results only sometimes

Question

So I tried writing an algorithm that would compute the smallest multiple of the numbers from 1-20. Here's my code:

multiples = range(2,11)
check = False
start = 1
while check is False:
    n = [start%i for i in multiples]
    if sum(n) == 0:
        check = True
        print(start)
        
    else:
        start = start+1

As it is, it works at range(2,11) and gives the right answer (2520). However, when I try to scale the code to range(2,21), it doesn't seem to generate an answer (it loops infinitely). Can anyone tell me what's wrong with it?

This is a very inefficient algorithm, when in fact it could probably be solved through judicious use of GCD or something similar. In any case, the very _smallest_ possible answer would be greater than or equal to the product of all the primes in that range, which for [2, 21] would be 9699690 -- almost 10 million. So you would need to compute about 200 million modulo operations before you even arrived at the smallest theoretically possible answer. — paddy, Nov 18 '20 at 07:05
A faster method is to iteratively calculate the smallest multiple, with the help of the gcd between the current multiple and the new element. Even faster methods could exist — Damien, Nov 18 '20 at 07:10
"Faster" is a massive understatement. The current algorithm is approaching factorial time complexity, whereas your suggestion is essentially linear, along with say Euclid's algorithm which is logarithmic. So we're talking `O(N.logN)` instead of `O(N!)`. — paddy, Nov 18 '20 at 07:18

score 0 · Answer 1 · answered Nov 18 '20 at 07:26

The problem is that this is a horrendously inefficient algorithm. A much better approach would be (using OP's variable names):

def lowest_common_multiple(a, b):
    # This would be replaced by the real code;
    # OP can search for an algorithm or implementation
    return a * b

multiples = range(2,21)
start = 1
for i in multiples:
    start = lowest_common_multiple(start, i)
print(start)

Here's a StackOverflow post on the LCM algorithm to get you started.

Note, both Python 3.9 and NumPy provide LCM functions.

Python algorithm doesn't yields correct results only sometimes

1 Answers1