Problem 5

Problem 5#

from functools import reduce
from typing import Iterable

from project_euler import get_problem_description

get_problem_description(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 divisibledivisible with no remainder by all of the numbers from $1$ to $20$?

So, I’m not sure how to solve this… but here goes nothing.

Hypothesis 1 - Find the prime numbers#

My first attempt will be to analyze the role that prime numbers have in this question. I am guessing that, if you find all the prime numbers between 1 and 10, and multiple them together, then you might get 2520. Here goes nothing.

def is_prime(number: int) -> bool:
    """Simple (and inefficient) check to see if number is prime."""
    if number == 1:
        return False

    for i in range(2, number):
        if number % i == 0:
            return False
    else:
        return True


assert not is_prime(1)
assert is_prime(2)
assert is_prime(3)
assert not is_prime(4)

list(filter(is_prime, range(1, 11)))

[2, 3, 5, 7]

Okay, I think we can assume our is_prime function works. Now let’s see if our hypothesis is correct?

def multiply(num1, num2):
    return num1 * num2


reduce(multiply, filter(is_prime, range(1, 11)))

210

Okay, obviously there is something else going on…

Let’s do a brute force solution to get a better idea of what’s going on.

def brute_force_solution(number_range):
    n = 1
    while True:
        if not all(n % i == 0 for i in number_range):
            n += 1
        else:
            break
    return n


brute_force_solution(range(1, 11))

2520

That was easy, but as we know, brute force solutions don’t scale well… We’re going to need a different approach!

Hypothesis 2 - Start big, then simplify!#

Here’s the gist of our strategy:

  1. Start by multiplying all of our divisors together

  • In the example, that would be numbers 1 - 10

  1. Take this very large product, and try to simplify it

  2. For every divisor, divide the large-product by the divisor

  3. If the smaller-product is still divisible by all the divisors, then this simplified-product replaces the large-product

  4. If none of the smaller-products are divisible by all divisors, then the large-product cannot be simplified

  5. Repeat until product cannot be simplified

def is_divisible(num: int, divisor: int) -> bool:
    return num % divisor == 0


def are_all_divisible(num: int, divisors: Iterable[int]) -> bool:
    return all(is_divisible(num, d) for d in divisors)


def simplify(num: int, divisors: Iterable[int]) -> int:
    assert are_all_divisible(num, divisors)
    divisors_not_one = [d for d in divisors if d != 1]
    for d in divisors_not_one:
        new_num = num / d
        if are_all_divisible(new_num, divisors):
            print(f"{num} / {d} = {int(new_num)}")
            return simplify(int(new_num), divisors)
    else:
        return num


def solve(divisors):
    print("Divisors: ", divisors)
    # start by multiplying all divisors together
    # to get a large product
    large_product = reduce(multiply, divisors)
    print("Large product: ", large_product)

    return simplify(large_product, divisors)

Okay, let’s try it…

solve(range(1, 11))

Divisors:  range(1, 11)
Large product:  3628800
3628800 / 2 = 1814400
1814400 / 2 = 907200
907200 / 2 = 453600
453600 / 2 = 226800
226800 / 2 = 113400
113400 / 3 = 37800
37800 / 3 = 12600
12600 / 5 = 2520

2520

WOW, it worked! Now, let’s try it with numbers 1 - 20.

solve(range(1, 21))

Divisors:  range(1, 21)
Large product:  2432902008176640000
2432902008176640000 / 2 = 1216451004088320000
1216451004088320000 / 2 = 608225502044160000
608225502044160000 / 2 = 304112751022080000
304112751022080000 / 2 = 152056375511040000
152056375511040000 / 2 = 76028187755520000
76028187755520000 / 2 = 38014093877760000
38014093877760000 / 2 = 19007046938880000
19007046938880000 / 2 = 9503523469440000
9503523469440000 / 2 = 4751761734720000
4751761734720000 / 2 = 2375880867360000
2375880867360000 / 2 = 1187940433680000
1187940433680000 / 2 = 593970216840000
593970216840000 / 2 = 296985108420000
296985108420000 / 2 = 148492554210000
148492554210000 / 3 = 49497518070000
49497518070000 / 3 = 16499172690000
16499172690000 / 3 = 5499724230000
5499724230000 / 3 = 1833241410000
1833241410000 / 3 = 611080470000
611080470000 / 3 = 203693490000
203693490000 / 5 = 40738698000
40738698000 / 5 = 8147739600
8147739600 / 5 = 1629547920
1629547920 / 7 = 232792560

232792560
Contents