DEV Community

Discussion on: Project Euler #5 - Finding the Smallest Multiple

Collapse
 
therealkhitty profile image
Mary Thompson

I wish I could understand this answer. It looks simple. I love software development, but I am horrible with math. Simple addition gives me anxiety.

Collapse
 
dwayne profile image
Dwayne Crooks

Hey Mary, let me help you understand this answer.

But first.

This problem as do most problems on Project Euler requires domain knowledge in Mathematics. In particular, Prealgebra. You can become a good software developer without knowing lots of Math. Furthermore, the types of problems you'd encounter on Project Euler won't prepare you for developing reliable, maintainable, user-friendly software. In short, don't get discouraged. Learn the domain knowledge on an as needed basis as the requirements of your software demands. And my last bit of advice is to read A Mind for Numbers - How to Excel at Math and Science if you want help getting over that math anxiety.

Here goes.

Start with a smaller problem. In this case, the example given is small enough and we can use it to check our answer.

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

Let's ignore 1 because every positive number is divisible by 1.

A positive number that's divisible by 2,3,...,10 is 2*3*...*10 because 2,3,...,10 are all factors of that number.

But is it the smallest? No and here's a simple reason why we might think so by looking at the powers of 2.

2, 4 and 8 are all factors of 2*3*...*10. But since 2 and 4 are factors of 8 it follows that 2, 4 and 8 will also be factors of 3*5*6*7*8*9*10. So we found a smaller number that works.

Similar reasoning leads us to smaller and smaller numbers in the following way.

Since 3 is a factor of 9 it follows that 3 and 9 will still be factors of 5*6*7*8*9*10.

Look at this. 5 is a factor of 10. So should we get rid of the 5 and leave the 10? 5 is a factor but so is 2. But 2 is already accounted for by the 8. Because of this we leave the 5 and remove the 10.

We're now left with 5*6*7*8*9.

8 accounts for 2, 4 and 8.
9 accounts for 3 and 9.
5 accounts for 5.

And the number is divisible by 10 because it is divisible by 2 and 5.

What about 6 and 7?

6 divides 5*7*8*9 so we can leave it out. However, 7 must remain since 7 does not divide 5*8*9. Therefore, we are left with: 5*7*8*9=(2*2*2)*(3*3)*5*7.

If you follow similar reasoning for the larger case you'd get the answer that I got.

What you'd notice is that all you're doing is finding the least common multiple of all the numbers and that's why you see the coded solutions are calculating LCM.

Thread Thread
 
therealkhitty profile image
Mary Thompson

I dont know how to do the quote format.. this is my first issue though: "A positive number that's divisible by 2,3,...,10 is 2*3*...*10 because 2,3,...,10 are all factors of that number." I don't understand how one came up with that conclusion and by divisible you mean without a remainder? Is it because you multiplied them all together that dividing by one of the numbers puts you in the same place you started before multiplying?

"But since 2 and 4 are factors of 8 it follows that 2, 4 and 8 will also be factors of 3*5*6*7*8*9*10." I have no idea how this "follows"; same with 3 and 5... esp. 5 because you remove 10 instead. Why didn't you remove 9 instead of 3? This is not confusing at all.

And why does "6 divide 5*7*8*9" but "7 does not divide 5*8*9"? Did you do the math to determine this or can this be explained without trial and error?

There are still assumptions in this solution, but thanks for trying to explain, though.

And I've already ordered that Math and Science book. Thank you.

Thread Thread
 
dwayne profile image
Dwayne Crooks

Is it because you multiplied them all together that dividing by one of the numbers puts you in the same place you started before multiplying?

Yes.

I have no idea how this "follows".

3*5*6*7*8*9*10 = 3*5*6*7*(2*4)*9*10 => 2, 4 and 8 are factors.

If 10 = 2*5 then 2 and 5 are factors. So that's what I'm doing above.

Why didn't you remove 9 instead of 3?

If I removed 9 then 9 would no longer be a factor of what remains. There's no way to make a 9 with what remains.

And why does "6 divide 5*7*8*9"

Because we can take a 2 from 8 and a 3 from 9 to show that 6 is a factor, i.e. 5*7*8*9 = 5*7*4*(2*3)*3 = 5*7*4*6*3.

but "7 does not divide 5*8*9"

5*8*9 = 5*2*2*2*3*3, see no 7's :).

Thread Thread
 
therealkhitty profile image
Mary Thompson

I see. This makes more sense. Thank you.

Thread Thread
 
dwayne profile image
Dwayne Crooks

You're welcome.