Project Euler Problem #5:

Project Euler Problem #5 is another question that is feasibly do-able by hand but can also be generalized. The problem reads:

Project Euler 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?

Clearly we will generalize this problem to find the least common multiple of the integers from 1 to n. One difficulty with finding the least common multiple of 2 numbers is that any factors that they share will be counted twice in the product of the two numbers. In fact, this observation leads to the useful fact that for two integers p and q, pq = lcm(p,q)*gcd(p,q) (here lcm(p,q) is the least common multiple of p and q while gcd(p,q) is the greatest common divisor of p and q). This fact does not generalize nicely for more than 2 integers, but it can be used to solve this problem as shown below:

Solution #1: Iterative Prime Power Approach

One fact that can help us solve this problem is that if we let F(n) be the least common multiple of the first n natural numbers, then F(n+1) = F(n) whenever n+1 has more than 1 distinct prime factor. This is clearly true, as if the prime factorization of n+1 has more than one prime power, than all of those prime powers are less than n+1 itself and therefore they should already be divisors of F(n). In the event that n+1 is a prime power of the form n+1 = p^e, then we have that F(n+1) = F(p^e) = pF(n). This is because the largest power of p that divides F(n) has to be p^(e-1), and because no other new factors are added, the least common multiple must be multiplied by the prime p.

With these facts in mind, we can iterate through all numbers i from 1 to n while storing a running least common multiple. Whenever i is a prime power, we multiply the running total by its prime factor, otherwise we do nothing. Here is an implementation of this method in Python 2.7:

'''
Author: Walker Kroubalkian
Iterative Approach to Project Euler Problem #5
'''

import time
from math import sqrt

def ifPowerGetPrime(n):
    c = 2
    while(c<=sqrt(n)):
        if(n%c==0):
            while(n%c==0):
                n/=c
            if(n>1):
                return -1
            else:
                return c
        c+=1
    return n

def projectEulerProblemFive(n):
    total = 1
    c = 2
    while(c<=n):
        a = ifPowerGetPrime(c)
        if(a>0):
            total*=a
        c+=1
    return total

start = time.time()
print projectEulerProblemFive(20)
print ("--- %s seconds ---" % (time.time()-start))

'''
Prints

232792560
--- 2.09808349609e-05 seconds ---

for input of n = 20
'''

This method appears to be quite efficient in general, as even extraordinary inputs such as finding the least common multiple of the first 1,000,000 natural numbers can be processed in under 10 seconds.

However, for small inputs such as n = 20, the question is quite do-able by hand. This post marks the 5th question of Project Euler, amounting to less than 1% of all the problems. Thanks for reading!