Smallest Multiple

Question

I just recently learned about Project Euler and have started doing the problems on there. I cleared problem 1 and 2, had no idea how to do 3 and 4, and started to do 5. I've seen the post regarding the quick mathematic solution, but I'd like to know if there are better ways to do it programmatically.

For those that don't know, question #5 is as follows:

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?

The logic behind my algorithm is simple:

The number in question must be divisible by all of the numbers between 1 and 20 (assume inclusive for the ranges). As a result, it must be divisible by all of the numbers between 1 and 10. The smallest number that is divisible by all the numbers between 1 and 10 (given by Project Euler) is 2520. Thus, the number in question must be a multiple of 2520. (As I'm writing this, I'm starting to question whether or not this is a necessary truth, but the program does work. Don't really want to go about proving it right now. I'm fairly certain however.) Thus, I can start at 2520 + 2520 and simply add 2520 every iteration.

It is guaranteed that these multiples will be divisible by all the numbers between 1 and 10, so there is no need to check those numbers. So I start from 11 and go to 20.

public static long problem5() {
    long i = 2520;
    boolean found = false;
    while (!found) {
        i += 2520;
        boolean divis = true;
        for (int j = 11; j <= 20; j++) {
            if (i % j != 0) {
                divis = false;
                //System.out.println(i + " is not divisible by " + j);
                break;
            }
            else {
                //System.out.println(i + " is divisible by " + j);
            }
        }
        if (divis) {
            found = true;
        }
    }
    return i;
}

I made this quick program to check my math regarding my statement "Thus, the number in question must be a multiple of 2520." It returns true if it finds a number not divisible by 2520 but divisible by all of the numbers between 1 and 10, and false if it does not find such a number. I feel that I set the limit to a reasonable limit. It indeed returns false.

public static boolean checkMath() {
    int start = 2520;
    int end = start * (232792560/2520);
    boolean result = true;
    for (int i = start + 1; i < end; i++) {
        result = true;
        for (int j = 1; j <= 10; j++) {
            if (i % j != 0) {
                result = false;
                break;
            }
        }
        if (result) {
            if (i % 2520 != 0) {
                break;
            }
        }
    }
    return (result);
}

Answer 1

The basic idea of all Project Euler problems is to find an efficient solution to the problem, by knowing enough math to simplify the computation your program must do. You can brute-force all of these with enough computing power, but there is a way to reduce the complexity such that a program that solves the problem will give you an answer in under one minute with a 5-year-old computer.

The brute-force answer would be to start at 21 and try every number in order until we found our answer. That's not a great idea, as the answer is quite large, and while, with a powerful computer, you might arrive at the answer in good time, brute force simply won't work in other Project Euler problems (you'll exceed hardware/firmware limitations, or end up with an exponential algorithm taking longer than the estimated heat-death of the universe to compute). In this case, with a few smarts, we can break down the problem and work with smaller numbers, thus taking fewer steps.

You want to know the smallest number divisible by every number from 1 to 20. Well, for one number to be divisible by another, all of the prime factors of the divisor must be present in the prime factorization of the dividend. For instance, 20 is divisible by 10 because 10's factors, 5 and 2, are both present in 20's factorization of 2²*5. The quotient is the product of the remaining prime factors; in this case there's only one, 2.

Now, the solution of the problem becomes more apparent; the smallest number divisible by every number from 1 to 20 is the smallest number that contains all the prime factors of every number from 1 to 20. So, the solution is to find the prime factorization of every number from 1 to 20 and keep a count of how many of each prime factor is necessary. Prime factorization is technically an inefficient process (you have to start with the number and divide by every known prime number until you get a whole-number quotient, then repeat from the beginning with that quotient until you're left with 1) but the numbers are so small it doesn't matter.

The solution is the smallest number for which the prime factorization of every number from 1 to 20 is a subset of its own prime factorization. At the least, you'll need one of every prime number from 1 to 20. You will also discover that in order to be divisible by 16, the number must have 4 2s in its prime factorization, and to be divisible by 9 and 18, the number must have 2 3s. The smallest such number is the number that has ONLY the needed factors, so the answer is

2⁴*3²*5*7*11*13*17*19 = 232792560.

The program to find this number will start at 2, iterate to 20, and for each of those numbers it will divide by every known prime less than that number (technically any prime less than the square root of the number but you won't save much that way) to determine their factorization. You will find the numbers that are prime as you go (they won't be divisible by any lesser prime, by definition). Any number that requires more than one of a particular prime factor should be tracked, and the maximum number of each factor remembered (I'll tell you for this problem that only 2 and 3 will require multiples). Then, simply multiply the necessary number of the necessary factors to produce the answer.

If this sounds like a lot, meh; the computer can whip through it pretty quickly, and it will take far less time than counting multiples of 2520. As a point of reference, the correct answer, if you didn't peek, is 5 orders of magnitude greater than this number, requiring about 10,000 iterations * dividing by 20 numbers on each one = 200,000 steps, versus a worst-case of 20 (number of divisors) * 8 (primes less than 20) * 7 / 2 (naive worst case of every number <= 20 being divisible by every prime <=20; not possible but the result's still nowhere close) = 560 steps to find the prime factorizations of the first 20 numbers.

Answer 2

Maybe you can reason as follows:

Multiplying all the numbers together from 1->10 gives you 3628800 which is indeed divisible by the numbers 1->10, but it is not the minimum number. Ask yourself why? take the last number 10 for instance. Do we really need to multiply 10 into our answer 10, when we know that our number already has a factor of 2 and a factor of 5?

Consider the prime factors of the numbers 1->10

factors:

 1 - 1
 2 - 2
 3 - 3
 4 - 2*2   (2^2)
 5 - 5
 6 - 2*3
 7 - 7
 8 - 2*2*2 (2^3)
 9 - 3*3   (3^2)
10 - 2*5

What's the most number of 2's you need to create any of the values 1->10...? 3 (8=2^3)
What's the most number of 3's? 2 (9=3^2)
What's the most number of 5's? 1 (5)
What's the most number of 7's? 1 (7)
Thus, the answer for the minimum number that is a multiple of 1->10, is 2^3*3^2*5*7 = 2520.
You can extend this logic for 1->20 and you'll get a much quicker algorithm than what you've proposed.

Answer 3

As has been expressed in other answers to this problem, the critical insight is that

$$LCM(1..1) = 1$$ $$LCM(1..n) = \frac{LCM(1..n-1) * n}{gcd(LCM(1..n-1), n)}$$

From that, you can build up to an arbitrary \$n\$ by applying the second formula repeatedly.

static long leastCommonMultiple(long n) {
    long multiple = 1;

    for ( long i = 2; i <= n; i++ ) {
        multiple *= i / gcd(i, multiple);
    }

    return multiple;
}

The recursive greatest common denominator (gcd) function is

static long gcd(long a, long b) {
    return ( 0 == b ) ? a : gcd(b, a%b);
}

And you can get this iteratively with

static long gcd(long a, long b) {
    while ( 0 != b ) {
        long temp = a;
        a = b;
        b = temp % b;
    }

    return a;
}

On my computer, the iterative version runs in about ten microseconds. The recursive version is a few microseconds slower.

Answer 4

I thought of a quick way to solve this without having to use prime factorization or finding prime numbers. The code I am going to paste is in java.

    int[] answers = new int[20];
    for (int i = 0; i < 20; i++) {
        answers[i] = i + 1;
    }
    int answer = 1;
    for (int i = 0; i < answers.length; i++) {
            if (answers[i] != 1) {
                answer *= answers[i];
                j = 2
                while (answers[i] * j < answers[i].length) {
                    answers[answers[i] * j] /= answers[i]
                    j += 1
                }
            }
    }
    return answer;

What this does is first it creates an array of all numbers:

answers[]=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];

Then for each number that isn't one, I multiply that number to the answer and update the array (divide all elements in the array, divisible by that number, by that number) so:

answer = 2; answers[] = [1,1,3,2,5,3,7,4,9,5,11,6,13,7,15,8,17,9,19,10];
answer = 6; answers[] = [1,1,1,2,5,1,7,4,3,5,11,2,13,7,5,8,17,3,19,10];
answer = 12;answers[] = [1,1,1,1,5,1,7,2,3,5,11,1,13,7,5,4,17,3,19,5];

etc.

Go through the entire array once and you get the answer. This is much much faster and easier than prime factoring.

Answer 5

My solution arrives at the same and correct answer, but I think is easier to understand.

public class SmallestMultiple {

public static void main(String [] args){

    boolean notFound = true;
    int base = 20, current = base;

    while(notFound){
        for(int i = base; i>10; i--){
            if(current%i != 0){
                current=current+base;
                notFound = true;
                break;
            }else{
                notFound= false;
            }
        }           
    }
    System.out.println(current);    
}   

All you really are concerned with is 11 through the upper limit (in this case 20), as it is guaranteed that 2 through 10 are factors of some greater number (11 through 20), so there is no need to iterate over 2 through 10.

Also, the answer MUST be evenly divisible by the max (i.e. 20).. So, start iterating downward from there, AND the first iteration that fails, simply stop and increase the potential answer by adding the base value (i.e. 20) to it, as this is guaranteed to also be evenly divisible by the max (i.e. 20) and you can start the iteration process over again from there. Simply keep repeating this until all values 11 through 20 evenly divide into the current value, and that value will be your answer.