• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 35,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Complex math problem

cuber786

Member
Joined
Oct 24, 2008
Messages
4
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.
 

hawkmp4

Member
Joined
May 17, 2008
Messages
1,396
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.
 
Joined
Oct 22, 2008
Messages
0
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
Joined
Jul 6, 2007
Messages
3,559
Location
California
WCA
2006GARR01
YouTube
Visit Channel
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?:rolleyes:
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
Joined
Sep 23, 2008
Messages
1,212
WCA
2008HALL02
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
Joined
Oct 24, 2008
Messages
4
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

Member
Joined
Dec 5, 2007
Messages
2,833
WCA
2008FANW01
YouTube
Visit Channel
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

Premium Member
Joined
Apr 5, 2006
Messages
4,106
Location
Atlanta, Georgia
WCA
2003HARD01
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
 
Last edited:

Cyber

Member
Joined
Sep 21, 2008
Messages
187
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
Joined
Jul 6, 2007
Messages
3,559
Location
California
WCA
2006GARR01
YouTube
Visit Channel
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
 
Top