# Complex math problem



## cuber786 (Oct 24, 2008)

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.


----------



## Ellis (Oct 24, 2008)

forty-two


----------



## MistArts (Oct 24, 2008)

232792560?


----------



## fanwuq (Oct 24, 2008)

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 (Oct 24, 2008)

how did you do that? can you show your work


----------



## hawkmp4 (Oct 24, 2008)

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.


----------



## Tox|k (Oct 24, 2008)

Ellis said:


> forty-two


Damn, you beat me to it 

-----

http://en.wikipedia.org/wiki/Least_...least_common_multiples_by_prime_factorization


----------



## ExoCorsair (Oct 24, 2008)

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


----------



## fanwuq (Oct 24, 2008)

ExoCorsair said:


> You really shouldn't be discussing Project Euler problems...



What is this Project Euler?


----------



## ExoCorsair (Oct 24, 2008)

http://projecteuler.net


----------



## brunson (Oct 24, 2008)

Even easier:
http://www.google.com/search?q=project+euler

fanwuq, I'm a little disappointed. ;-)


----------



## irinaatcolumbia (Oct 24, 2008)

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.


----------



## Lucas Garron (Oct 24, 2008)

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:

```
[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 (Oct 24, 2008)

Lucas Garron said:


> 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 (Oct 24, 2008)

Lucas Garron said:


> 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.



ok. How about this then: can you help me understand how to do it?



> 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 (Oct 24, 2008)

Ellis said:


> Lucas Garron said:
> 
> 
> > 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.
> ...



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 (Oct 24, 2008)

cuber786 said:


> ok. How about this then: can you help me understand how to do it?



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


----------



## Cyber (Oct 24, 2008)

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 (Oct 24, 2008)

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. 

Start with LCM = 1.
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 (Oct 24, 2008)

' !?
How this thing works?:confused:


----------



## Lucas Garron (Oct 24, 2008)

Cyber said:


> ' !?
> How this thing works?:confused:


All your confusion are belong to math!


----------



## nitrocan (Oct 24, 2008)

This was so easy:

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


----------

