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

[Mathysics29]

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!

 

[PeroK]

What about looking at the prime factorisation?

Also you perhaps need to be more specific about how you choose a factor at random.

 

[Mathysics29]

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

 

[Vanadium 50]

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?

 

[jbriggs444]

the number is huge. It's litterally 25!

Are you sure about this? How many factors in 3 factorial?

 

[Mathysics29]

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.

 

[Vanadium 50]

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.

 

[jbriggs444]

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

 

[PeroK]

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.

 

[mfb]

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.

 

[jbriggs444]

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.

 

[Vanadium 50]

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.

 

[ddddd28]

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.

 

[jbriggs444]

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.

 

[ddddd28]

You are right It doesn't hold... I don't understand how I missed it.

 

[jbriggs444]

You are right 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".

 

[mfb]

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.

 

[Mathysics29]

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.

 

[PeroK]

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.

 

[mfb]

The prime factorization has been suggested many times now. Did you do that? This is not listing every factor!

 

[Mathysics29]

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

 

[jbriggs444]

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?

 

[Vanadium 50]

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.

 

[ddddd28]

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.

 

[Chris Miller]

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.

 

[jbriggs444]

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.

So your claim is that there are exactly nine factors of 25 factorial and that half of them (i.e. four and a half) are even?

 

[mfb]

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.

Try to use the same logic for the factors of 12, for example. How many of them are odd, how many are even? You can count to check the answer.
The prime factorization should give some idea how to find this number without counting all factors.

 

[Chris Miller]

Yeah, thanks. Guesswork doesn't serve well in math. Thought about it some more since. 25! can be expressed as
2 * 3 * (2*2) * 5 * (2*3) * 7 * (2*2*2) * (3*3) * (2*5) * 11 * (2*6) * 13 * (2*7) * (3*5) * (2*2*2*2) * 17 * (2*3*3) * 19 * (2*2*5) * (3*7) * (2*11) * 23 * (2*2*2*3) * (5*5)

or 2^21 * 3^7 * 5^6 *7^3 * 11^2 * 13 * 17 * 19 * 23

So 21 of its factors is 2.

So for every odd factor there are 21 ways of making it even.
So P= 1/21

More simply and generally,
For any n!, the probability of of a random factor being odd is 1/#of 2s in its factorization.

I might be wrong, but no longer guessing.

EDIT
Am wrong. Dang. Fails for 3!

Neglected to include all the possible multiples of 2.

So for 25! P=1/(21*2) =1/42

For any n!,
Let t=the number of 2s in its factorization.

The probability of of a random factor of n being odd is 1/(t*2)

Talk about showing your "work."

 

[jbriggs444]

That is a sound strategy. I see one problem with the prime factorization and a different off by one error in computing the probability.

 

[Chris Miller]

Hmm... let me re-calc
n , twos
[2] 2, 1
[3] 3,
[4] (2*2), 3
[5] 5,
[6] (2*3), 4
[7] 7,
[8] (2*2*2), 7
[9] (3*3) ,
[10] (2*5), 8
[11] 11,
[12] (2*6), 9
[13] 13,
[14] (2*7), 10
[15] (3*5) ,
[16] (2*2*2*2), 14
[17] 17,
[18] (2*3*3), 15
[19] 19,
[20] (2*2*5), 17
[21] (3*7),
[22] (2*11), 18
[23] 23,
[24] (2*2*2*3), 21
[25] (5*5)

still get 21
and still get P=1/(21+21) = 1/42
?
Is it my equation P=1/(t*2) where t=# of 2s in factorization? Or am I just miscounting somewhere? Or both?
Let's see. I guess 1 is an odd factor too, but it's covered by the t powers of 2.

 

[jbriggs444]

[12] (2*6) * 9

Six is not a prime number.

I am not at all sure what that nine is doing there.

 

[Chris Miller]

Right. Thanks! Should be 2*2*3, raising the number of 2s to 22 (9 was the 2 count at that step, and should be 10) making P=1/(22*2) = 1/44. Really appreciate your help.

 

[Chris Miller]

Went to bed. Thought about it. Got back up. For every odd factor (including 1) there are t even factors. So the odds (not probability) of picking an odd one at random are 1 to t. So the probability is 1/(t+1). So for 25! it's 1/(22+1) or 1/23. Now going back to bed, and hopefully not having to get back up again. Tonight.

 

[ddddd28]

The number of factors can be simply described as the product:
(q1+1)(q2+1) ... (qn+1). q1, q2 ... qn are the number of times a prime appears in the factorization.
To find the required probability is to calculate the product of 25! and the product of 25! divided by 2^q.

 

[jbriggs444]

The number of factors can be simply described as the product:
(q1+1)(q2+1) ... (qn+1). q1, q2 ... qn are the number of times a prime appears in the factorization.
To find the required probability is to calculate the product of 25! and the product of 25! divided by 2^q.

You may wish to read the whole thread and refine that answer a bit. What you have written seems to claim that the probability is $\frac{25!\ 25!}{2^{22}}$. In addition to being incorrect, that number is larger than one while probabilities are always less than or equal to one.