If k divides 25! what is prob(k odd)?

  • #1
Let n=1×2×3×...×25
If a positive factor of n is chosen at random, what is the probability that the chosen factor is an odd number?


At first I thought of listing out the factors like you would for 1×2×3×4×5 for example. Which is in this case {1,2,3,6,8,10,12,15,20,40,60,120} but it is way too many factors for n=25! as the number is huge.


Then maybe I thought of using modular concept but I'm really not familiar with it at all. I can't really spot any pattern either. So I really need someone to help me. Thanks!!
 

Answers and Replies

  • #2
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
16,287
8,288
What about looking at the prime factorisation?

Also you perhaps need to be more specific about how you choose a factor at random.
 
Last edited:
  • #3
What about looking at the prime factorisation?

Also you perhaps need to be more specific about how you choose a factor at random.
Yes but I can't wrap my head around the question because the number is huge. It's litterally 25!
How can I use prime factorization....?
 
  • #4
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
26,449
9,969
First, this is not a hard problem.
Second, this is not a very descriptive thread title.
Third, is this homework?
Fourth, is the only possible way to solve this to write out every factor?
 
  • #5
jbriggs444
Science Advisor
Homework Helper
9,612
4,261
the number is huge. It's litterally 25!
Are you sure about this? How many factors in 3 factorial?
 
  • #6
First, this is not a hard problem.
Second, this is not a very descriptive thread title.
Third, is this homework?
Fourth, is the only possible way to solve this to write out every factor?
It's not homework. It's from a local mathematics competition for high school students. How can your write every factor of 25 factorial. Even if you write for 5 hours you still won't get close. I suspects using combinations though I'm not smart enough to work that out myself.
Screenshot_20180629-183257-1.jpg
 

Attachments

  • #7
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
26,449
9,969
PeroK is right in that it is useful to look at the prime factorization. He is not right that it is necessary. He is not right in that it matters how you choose a factor at random. Jbriggs has a good hint. And since you have rejected writing down all the factors as a sensible way forward, why are you still fixated on it?

To show you this is doable, for 1000! the answer is, provided I did the arithmetic right, 995.
 
  • #8
jbriggs444
Science Advisor
Homework Helper
9,612
4,261
To show you this is doable, for 1000! the answer is, provided I did the arithmetic right, 995.
There must be an arithmetic error somewhere. It is clear that every integer between 1 and 1000 inclusive is a factor of 1000 factorial.

Edit: OOPS. It seems that you intended 995 as the answer to the problem (i.e. 1/p) rather than as the number of unique factors of 1000 factorial as I had understood. And indeed, once one has the right strategy in hand, it becomes clear that 995 is the final answer for the 1000 factorial case (or awfully darned close).
 
Last edited:
  • Like
Likes PeroK
  • #9
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
16,287
8,288
Yes but I can't wrap my head around the question because the number is huge. It's litterally 25!
How can I use prime factorization....?
Instead of wrapping your head round the problem, try wrapping the problem round your head.

Seriously, if this is a competition question a hint about prime factorisation is about as much as we should give you.

Expressing 25! As a product of primes shouldn't be too hard.
 
  • #10
35,269
11,543
To show you this is doable, for 1000! the answer is, provided I did the arithmetic right, 995.
The question asks about a probability, the answer has to be between 0 and 1.
He is not right in that it matters how you choose a factor at random.
It absolutely matters. If you choose factor n with relative probability 1/n you'll get a different answer. The same probability for every factor is a reasonable guess but the problem statement should specify that.
 
  • #11
jbriggs444
Science Advisor
Homework Helper
9,612
4,261
The question asks about a probability, the answer has to be between 0 and 1.
The question (as re-cast in #6) asks about a probability. It does not ask for that probability.
 
  • Like
Likes Vanadium 50
  • #12
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
26,449
9,969
Perhaps you intended 995 as the answer to the problem (i.e. 1/p) rather than as the number of unique factors of 1000 factorial as I had understood.
That is correct. And I have not calculated the number of unique factors of 1000!. Or 25! Or any number. That's all I am going to say; any more is too much of a hint.
 
  • #13
74
4
I think that the problem's composer used n=25! not in vain. In other words, counting the factors of a factorial is very easy. Just look at it in a recursive perspecive:
n factors
1! 1
2! 1 2
3! 1 2 3 6
4! 1 2 3 6 4 8 12 24
5! 1 2 3 6 4 8 12 24 5 10 15 30 20 40 60 120
I am sure you can easily find and explain the pattern when represented like this.
 
  • #14
jbriggs444
Science Advisor
Homework Helper
9,612
4,261
I think that the problem's composer used n=25! not in vain. In other words, counting the factors of a factorial is very easy. Just look at it in a recursive perspecive:
n factors
1! 1
2! 1 2
3! 1 2 3 6
4! 1 2 3 6 4 8 12 24
5! 1 2 3 6 4 8 12 24 5 10 15 30 20 40 60 120
I am sure you can easily find and explain the pattern when represented like this.
Extend that pattern one more line, please, to see if it still holds. Hint: what is 1 times 6 and is it already in the list?

As @Vanadium 50 suggests, it is not necessary to enumerate the factors or even figure out how many there are in order to solve the problem.
 
Last edited:
  • #15
74
4
You are right:sorry: It doesn't hold... I don't understand how I missed it.
 
  • Like
Likes jbriggs444
  • #16
jbriggs444
Science Advisor
Homework Helper
9,612
4,261
You are right:sorry: It doesn't hold... I don't understand how I missed it.
None of 2, 3, 4 or 5 can be expressed as a product of any subset of the prior terms. 6 is the first that can be expressed as a product of a subset of the prior integers (2 times 3).

You actually had me believing the progression for a moment. Until I went "wait... you cannot have a probability of 1 in 995 if all probabilities have to be a multiple of an inverse power of two".
 
  • #17
35,269
11,543
The question (as re-cast in #6) asks about a probability. It does not ask for that probability.
Ah, I didn't see the picture in post 5.
To show you this is doable, for 1000! the answer is, provided I did the arithmetic right, 995.
I get the same answer.
 
  • #18
Ah, I didn't see the picture in post 5.I get the same answer.
How did you do the arithmetic for 1000!
I sorry I really have no clue.
 
  • #19
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
16,287
8,288
How did you do the arithmetic for 1000!
I sorry I really have no clue.
Although there's a shortcut, the key to this is prime factorisation. Try the problem for smaller numbers. Perhaps 2-10. Post your work.
 
  • #20
35,269
11,543
The prime factorization has been suggested many times now. Did you do that? This is not listing every factor!
 
  • #21
Although there's a shortcut, the key to this is prime factorisation. Try the problem for smaller numbers. Perhaps 2-10. Post your work.
This is what I got for 25!
2^22 × 3^10 × 5^6 × 7^3 × 11^2 × 13 × 17 × 19 × 23
 
  • #22
jbriggs444
Science Advisor
Homework Helper
9,612
4,261
This is what I got for 25!
2^22 × 3^10 × 5^6 × 7^3 × 11^2 × 13 × 17 × 19 × 23
Suppose that you wanted to use this information to figure out how many factors of 25! there are. How would you proceed?
 
  • Like
Likes PeroK
  • #23
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
26,449
9,969
Perhaps 2-10. Post your work.
This is what I got for 25!
Please don't turn this to one of those threads where the questioner gets lots of good advice, and then picks and chooses which tiny piece he will take.
 
  • #24
74
4
Just wanted to share a nice method for visualizing the number of factors.
All the factors are, of course, solutions of the equation xy=d ,d is a natural number.
Notice that the function cos(2πk) equals 1 only and only if k is an integer.
Since x and y have to be integers, it is possible to substitute x and y in the function and to sum up them, to obtain:
cos(2πd/x)+cos(2πx).
And all what you have to do is to count the upper global maxima, that is to say, when the new function equals 2.
Unfortunately, I wasn't able to develop further my idea, so that looking at the graph wouldn't be necessary.
 

Attachments

  • #25
365
34
The number of unique factors of 25! would be the number of primes < 25. I.e., 2, 3, 5, 7, 11, 13, 17, 19 , 23. I'm thinking the answer though, is .5 since the number of odds is equal to the number of evens, i.e., for every factor > 2 there will be a 2.
 

Related Threads on If k divides 25! what is prob(k odd)?

  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
2K
Replies
2
Views
2K
  • Last Post
Replies
17
Views
1K
Replies
3
Views
2K
Replies
2
Views
546
Replies
2
Views
2K
Replies
5
Views
734
Top