Project Euler Problem 5

Question

I wrote up a small script to calculate the answer to Project Euler Problem 5:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

I'm wondering if this algorithm can be improved or made more efficient:

def divisible_by(num, den_set):
 if not den_set: return True
 elif not num % den_set.pop():
 return divisible_by(num, den_set)
 else: return False
def smallest(den_count):
 i = 1
 den_set = list(range(1, den_count))
 while not divisible_by(i, den_set):
 den_set = list(range(1, den_count))
 i += 1
 return i
print smallest(20)

• alexwlchan: In Python 2.7, range() already returns a list, so there’s no need to recast it.
• motoku: @alexwlchan Thanks! I was thinking of Python 3, but then I managed to write Python 2 print statements...

Answer 1

The smallest number that can be divided by a set of numbers without any remainder is also known as the least common multiple, which can be calculated directly using the greatest common divisor (gcd).

The least common multiple of a, b:

lcm(a, b) = a * b / gcd(a, b)

The least common multiple of a, b, c:

lcm(a, b, c) = lcm(a, lcm(b, c))

You could generalize this to more numbers.

Answer 2

Use den_count += 1 before creating den_set. Because range(1, den_count) will create list of numbers from 1 to (den_count -1).
This is not a problem for 20, but for 25, your code will give an answer 5 times smaller than it should be (since you are skipping 25 itself).
Instead of checking whether each number satisfies the conditions, why not create the number. We know that the number has to divisible by every number from 1 to den_count.
If x is a number in the list then, let $$ den\_count = \alpha_1^{p_1} \times \alpha_2^{p_2}\times \alpha_3^{p_3}\times... $$ and $$ x = \alpha_1^{q_1} \times \alpha_2^{q_2} \times \alpha_3^{q_3} \times... $$ where, $$\alpha_1, \alpha_2, \alpha_3 ...$$ are prime numbers. Then it follows that,
$$ p_1 \geq q_1, p_2 \geq q_2, p_3 \geq q_3 ...$$ So we can factorize every number from 1 to den_count and take the largest values of $$q_1, q_2, q_3...$$ and construct the number easily.

• Green monster: In fact, [codereview.stackexchange.com/questions/35499/… uses same approach. Basically you want to find lcm of the numbers.
• miracle173: factoring isn't fast for large numbers. Algorithms based on gcd are much faster.