Problem 5 - Smallest Multiple

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?

Well, this is awkward . . .

solution = 0
for x in range(180,1000000000,10):
    if solution != 0:
        break
    for y in range(2,21):
        if x % y != 0:
            break
        if x % y == 0:
            if y == 20:
                solution = x
            continue
print solution
# 40.1628811359 Execution time

In defense of my former self, there is one optimization in here that is helpful. Notice how the step in the for loop is 10. As our target number must have 10 as a factor, we only need search multiples of 10. However, this thinking doesn't immediately take the next logical step and double the step to 20, as this is the largest factor of our target. Amendment:

solution = 0
for x in range(180,1000000000,20):
    for y in range(2,20):
        if x % y != 0:
            break
        if x % y == 0:
            if y == 19:
                solution = x
            continue
    if solution != 0:
        break
print solution
# 22.1047170162 Execution time

And this halves our running time; Lovely. Now to actually address the big O.

To actually have a decent time scale, we need to do better. Stepping back from 20 and checking to see what factors we have to check at a minimum seems like a good starting point. First conclusion: we definitely check the larger numbers that have smaller numbers as a factor, thus checking several numbers at once by proxy. This reduces our search space from [2 ... 20] to [11, 13, 14, 16, 17, 18, 19] if we step by twenty. Let's try this

solution = 0
for x in range(2520,1000000000,20):
    for y in []:
        if x % y != 0:
            break
        if x % y == 0:
            if y == 19:
                solution = x
            continue
    if solution != 0:
        break
print solution
# 8.65195894241 Execution time

That's better, let's keep going. Realizing that a step of 20 doesn't have a factor of 3 in it, we can up our step to 60 to account. However, 60 doesn't have a factor of 7 in it, so we set it to 420.

solution = 0
for x in range(2520,1000000000,420):
    for y in [11, 13, 14, 16, 17, 18, 19]:
        if x % y != 0:
            break
        if x % y == 0:
            if y == 19:
                solution = x
            continue
    if solution != 0:
        break
print solution
# 0.421896934509 Execution time

Now that's respectable for a search approach. Now, let's attack the problem from the other direction. Rather than find our answer among thousands of possibilities, let's just make our answer using some maths.

Since we know that our answer is a product of all of the numbers from 2 to 20 (1 eliminated as tautoligical), we immediately know that we need to multiply all of the primes in here together immediately. What are these?

[2,3,5,7,11,13,17,19]

What's the product so far?

9699690

And well below our answer. Why? Because these are just the primes under twenty. We still don't have factors of 4, 8, 9, 12, 16, 18, or 20, which are all necessary. We have some of the factors of these numbers, so let's just put in some more prime factors so we know we can construct these higher factors.

Adding another factor of 2 to the list allows us to construct 4 as well as 12 and 20 when multiplied with 3 and 5 respectively. Another 2 allows us to make 8, another 16. That's all of the factors of two that we need. Including another 3 allows us to make 9 and 18 with one of the 2's, so that's all of our factors from 2 to 20. Our final list of factors is:

[2,2,2,2,3,3,5,7,11,13,17,19]

So how can we generate this list of prime factors? Well, we did some work on that idea in problem 3, but we can't really use that approach since we don't have a target number to work from. Well, let's just recap what our steps to generate the list long hand were:

1 - Include all primes below factor run ceiling
2 - Add more copies of small primes to account for larger non-primes

The only question needed to answer is "How many times do I need to include a copy of a small prime?" Well, the largest number that one can generate under a given target (20, in this case) using just the number 2 is 2^4, which is 16. To include another factor of 2 beyond this would be mandating that our answer be divisible by 32, which is unnecessary for our solution and therefore redundant.

A hypothesis: Include X copies of factor n, so that n^X is as large as possible without passing our ceiling.

Let's try it. We'll need a prime number generator, which we already do from problem 3.

solution = 1
ceiling = 20
plist = primes()
plist.populate_until(ceiling)
factors = []
for x in [z for z in plist.primelist if z <= ceiling]:
    power = 1
    while (x ** power) <= ceiling:
        factors.append(x)
        power += 1
for x in factors:
    solution *= x

This algorithm will generate a smallest multiple of consecutive integers up to the variable ceiling. The populate member method of the primes class is one that I added to prepopulate the list of primes up to a target number (the ceiling, in this case). To generate the correct answer for ceiling = 20, this took:

# 2.59876251221e-05 seconds

Much less awkward . . . phew . . .

P.S. For ceiling = 1000, it took:

# 0.0191540718079 seconds