# Complex math problem

#### cuber786

##### Member
Theres this math problem that I am trying to solve but am having no luck, and I decided to post it just in case one of you guys can solve it:

What is the smallest number that is evenly divisible by all the numbers from 1 to 20? You may want to use your knowledge of least common multiple to find the answer.
The work must be shown.

60 is the smallest number that can be divided by each of the numbers from 1 to 5 without any remainders.
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainders.
Hint: write each number as the product of prime factors.

forty-two

232792560?

#### fanwuq

##### Member
2*2*2*2 * 3*3 *5 *7 *11 *13 *17 *19

This problem is too easy, it's less than 1min of work.

#### cuber786

##### Member
how did you do that? can you show your work

#### hawkmp4

##### Member
Well, I haven't worked it all out yet, but just start with 20. If a number is divisible by 20, then it is also divisible by all the factors of 20. Just continue working down the line until you have all the numbers 1-20 accounted for.

#### ExoCorsair

##### Member
You really shouldn't be discussing Project Euler problems...

#### fanwuq

##### Member
You really shouldn't be discussing Project Euler problems...
What is this Project Euler?

#### irinaatcolumbia

##### Member
Hi Cuber786 -

If you say that the smallest number that is evenly divisible by two numbers is the least common multiple (which is ok to say, because it's true), you can get a solution with two lines of code in ruby.

numbers=(1..20).to_a
puts numbers.inject{ |x,n| x.lcm(n) }

How about that? Ruby has a built-in least common multiple function!

Edit: Eh, looks like there are other solutions out there that are probably more mathematical. Good luck with the problems.

Last edited:

#### Lucas Garron

##### Member
1) Yeah, no posting Project Euler stuff directly; that's just silly.
2) For most of us, this isn't even a "problem" that requires "solving." I came to this thread in hope of something actually complicated (or just involving i), rather than just finding out that you don't happen to know some certain basic math number theory.
So, I really object to the title: I'm spending hours on introductory multivariable calc homework, and it's not even complex at all. (Oh my, complex analysis is gonna be fun someday...) Seriously, is it impossible for people to title their threads properly? Do we need a sticky about that, too?
3) Mathematica is the best:
Code:
[email protected]@Range[20]
4) Don't be discouraged about trying to understand this problem, though. Don't just "have no luck;" use Google, try stuff on your own, or just leave it alone and solve it later. Math is lovely, but you just have to get used to solving problems. And if you really want to understand a math problem, you can post it here -but ask for help understanding it, not for someone to do it for you.

#### Ellis

##### Member
For most of us, this isn't even a "problem" that requires "solving." I came to this thread in hope of something actually complicated (or just involving i), rather than just finding out that you don't happen to know some certain basic math number theory.
So, I really object to the title
Complexity is relative lucas. It's complex to the person who posted it, and therefore it is a fitting title.

#### cuber786

##### Member
And if you really want to understand a math problem, you can post it here -but ask for help understanding it, not for someone to do it for you.

and it's not even complex at all...
well, im not really good with math so to me this problem is kind of hard.

#### fanwuq

##### Member
For most of us, this isn't even a "problem" that requires "solving." I came to this thread in hope of something actually complicated (or just involving i), rather than just finding out that you don't happen to know some certain basic math number theory.
So, I really object to the title
Complexity is relative lucas. It's complex to the person who posted it, and therefore it is a fitting title.
That might be true, but compared to other problems that had been posted, this is not difficult. Perhaps just title it "math problem?"

I, like Lucas, really expected something with i.

#### cmhardw

Find the first number divisible by all of the following numbers: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Least common multiple is based on the prime factorization of each of the numbers you want it to be divisible by. Find the prime factorization of each number above.

2, 3, 2^2, 5, 2*3, 7, 2^3, 3^2, 2*5

Now find all the prime numbers represented in the list. These are: 2, 3, 5, 7

If you want your final number to be divisible by all of the numbers in your list, then it must be divisible by 2. Furthermore it must be divisible by the highest power of 2 represented. So 2^3.

Use the same argument for 3, 5, 7. This gives you 2^3 * 3^2 * 5 * 7 = 2520

This is just using the example you gave us in the original problem, using the same hint you gave us too. I leave you to do the 1,2,3,...,20 problem. You only need pencil and paper for this problem to be honest, but a computer is much faster of course.

Chris

Last edited:

#### Cyber

##### Member
This was an interesting question
It just takes too long to findtis thread

20 = 2^2*5
19 = 19
18 = 2*3^2
17 = 17
16 = 2^4
15 = 3*5
14 = 2*7
13 = 13
12 = 2^2*3
11 = 11
10 = 2*5
9 = 3^2
8 = 2^3
7 = 7
6 = 2*3
5 = 5
4 = 2^2
3 = 3
2 = 2
1 = 1

Look where is most 2 it is 16 -> so 2^4
Look where is most 3 it is 18 and 9 -> so 3^2
Look where is most 5 it is 5, 10, 15 -> so 5
Look where is most 7 it is 7 and 14 -> so 7
Look where is most 11 it is 11 -> so 11
Look where is most 13 it is 13 -> so 13
Look where is most 17 it is 17 -> so 17
Look where is most 19 it is 19 -> so 19

So the answer is again... 2^4*3^2*5*7*11*13*17*19 = 232792560

#### Lucas Garron

##### Member
Since we're discussing LCM methods, I thought I'd try to solve this with something that easily follows from the Mangoldt lambda function we discussed in Analytic Number Theory.

Count through 20, and if you encounter a power of a prime, multiply LCM by that prime (not the power, the prime that it's a power of):

01: 1
02: *2
03: *3
04: *2
05: *5
06:
07: *7
08: *2
09: *3
10:
11: *11
12:
13: *13
14:
15:
16: *2
17: *17
18:
19: *19
20:

1*2*3*2*5*7*2*3*11*13*2*17*19 = 232792560

#### Cyber

##### Member
' !?
How this thing works?:confused: